A computational study of constraint satisfaction for multiple capacitated job shop scheduling

W.P.M. Nuijten, E.H.L. Aarts

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.
Original languageEnglish
Pages (from-to)269-284
Number of pages16
JournalEuropean Journal of Operational Research
Volume90
Issue number2
DOIs
Publication statusPublished - 1996
Externally publishedYes

Fingerprint

Job Shop Scheduling
Job Shop Scheduling Problem
Constraint Satisfaction
Empirical Analysis
Performance Analysis
Constraint satisfaction
Job shop scheduling

Cite this

@article{dabf9744b6a24bd1a4a6e96445240e42,
title = "A computational study of constraint satisfaction for multiple capacitated job shop scheduling",
abstract = "We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.",
author = "W.P.M. Nuijten and E.H.L. Aarts",
year = "1996",
doi = "10.1016/0377-2217(95)00354-1",
language = "English",
volume = "90",
pages = "269--284",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science BV",
number = "2",

}

A computational study of constraint satisfaction for multiple capacitated job shop scheduling. / Nuijten, W.P.M.; Aarts, E.H.L.

In: European Journal of Operational Research, Vol. 90, No. 2, 1996, p. 269-284.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A computational study of constraint satisfaction for multiple capacitated job shop scheduling

AU - Nuijten, W.P.M.

AU - Aarts, E.H.L.

PY - 1996

Y1 - 1996

N2 - We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.

AB - We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.

U2 - 10.1016/0377-2217(95)00354-1

DO - 10.1016/0377-2217(95)00354-1

M3 - Article

VL - 90

SP - 269

EP - 284

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -