Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

Edwin Tai Chiu Cheng; Mikhail Y. Kovalyov

doi:10.1016/S0377-2217(98)00111-8

Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

Edwin Tai Chiu Cheng
, Mikhail Y. Kovalyov

Research output: Journal article publication › Journal article › Academic research › peer-review

12 Citations (Scopus)

Abstract

We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait (PPW) due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(nlogn) time.

Original language	English
Pages (from-to)	403-410
Number of pages	8
Journal	European Journal of Operational Research
Volume	114
Issue number	2
DOIs	https://doi.org/10.1016/S0377-2217(98)00111-8
Publication status	Published - 16 Apr 1999

Keywords

Due date assignment
Parallel machine scheduling

ASJC Scopus subject areas

Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

More information

10.1016/S0377-2217(98)00111-8

Cite this

@article{f30910fd15334ed3a47074d7e464e2ec,

title = "Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness",

abstract = "We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait (PPW) due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(nlogn) time.",

keywords = "Due date assignment, Parallel machine scheduling",

author = "Cheng, \{Edwin Tai Chiu\} and Kovalyov, \{Mikhail Y.\}",

year = "1999",

month = apr,

day = "16",

doi = "10.1016/S0377-2217(98)00111-8",

language = "English",

volume = "114",

pages = "403--410",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

AU - Cheng, Edwin Tai Chiu

AU - Kovalyov, Mikhail Y.

PY - 1999/4/16

Y1 - 1999/4/16

N2 - We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait (PPW) due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(nlogn) time.

AB - We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait (PPW) due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(nlogn) time.

KW - Due date assignment

KW - Parallel machine scheduling

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

U2 - 10.1016/S0377-2217(98)00111-8

DO - 10.1016/S0377-2217(98)00111-8

M3 - Journal article

SN - 0377-2217

VL - 114

SP - 403

EP - 410

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this