Job Shop Scheduling with Deadlines

Egon Balas; Giuseppe Lancia; Paolo Serafini; Alkiviadis Vazacopoulos

doi:10.1023/A:1009750409895

Job Shop Scheduling with Deadlines

Egon Balas
, Giuseppe Lancia
, Paolo Serafini
, Alkiviadis Vazacopoulos

School of Business

Research output: Contribution to journal › Article › peer-review

21 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 language	English
Pages (from-to)	329-353
Number of pages	25
Journal	Journal of Combinatorial Optimization
Volume	1
Issue number	4
DOIs	https://doi.org/10.1023/A:1009750409895
State	Published - 1998

Keywords

Deadlines
Scheduling
Shifting bottleneck

Access to Document

10.1023/A:1009750409895

Cite this

@article{93956a5c30c14da4a701d591dc0dcca4,

title = "Job Shop Scheduling with Deadlines",

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.",

keywords = "Deadlines, Scheduling, Shifting bottleneck",

author = "Egon Balas and Giuseppe Lancia and Paolo Serafini and Alkiviadis Vazacopoulos",

year = "1998",

doi = "10.1023/A:1009750409895",

language = "English",

volume = "1",

pages = "329--353",

number = "4",

}

TY - JOUR

T1 - Job Shop Scheduling with Deadlines

AU - Balas, Egon

AU - Lancia, Giuseppe

AU - Serafini, Paolo

AU - Vazacopoulos, Alkiviadis

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - Deadlines

KW - Scheduling

KW - Shifting bottleneck

UR - https://www.scopus.com/pages/publications/0031704308

UR - https://www.scopus.com/pages/publications/0031704308#tab=citedBy

U2 - 10.1023/A:1009750409895

DO - 10.1023/A:1009750409895

M3 - Article

AN - SCOPUS:0031704308

SN - 1382-6905

VL - 1

SP - 329

EP - 353

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

Job Shop Scheduling with Deadlines

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this