Job Shop Scheduling with Deadlines

Egon Balas, Giuseppe Lancia, Paolo Serafini, Alkiviadis Vazacopoulos

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

In this paper we deal with a variant of the Job Shop Scheduling Problem. We consider the addition of release dates and deadlines to be met by all jobs. The objective is makespan minimization if there are no tardy jobs, and tardiness minimization otherwise. The problem is approached by using a Shifting Bottleneck strategy. The presence of deadlines motivates an iterative use of a particular one machine problem which is solved optimally. The overall procedure is heuristic and exhibits a good trade-off between computing time and solution quality.

Original languageEnglish
Pages (from-to)329-353
Number of pages25
JournalJournal of Combinatorial Optimization
Volume1
Issue number4
DOIs
StatePublished - 1998

Keywords

  • Deadlines
  • Scheduling
  • Shifting bottleneck

Fingerprint

Dive into the research topics of 'Job Shop Scheduling with Deadlines'. Together they form a unique fingerprint.

Cite this