Job shop scheduling with setup times, deadlines and precedence constraints

Egon Balas, Neil Simonetti, Alkis Vazacopoulos

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

Abstract

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.

Original languageEnglish
Pages (from-to)253-262
Number of pages10
JournalJournal of Scheduling
Volume11
Issue number4
DOIs
StatePublished - Aug 2008

Keywords

  • Dynamic programming
  • Sequence-dependent setup times
  • Traveling salesman problem with time windows shifting bottleneck

Fingerprint

Dive into the research topics of 'Job shop scheduling with setup times, deadlines and precedence constraints'. Together they form a unique fingerprint.

Cite this