List scheduling in a parallel machine environment with precedence constraints and setup times

Johann L. Hurink; Sigrid Knust

doi:10.1016/S0167-6377(01)00104-3

List scheduling in a parallel machine environment with precedence constraints and setup times

Johann L. Hurink, Sigrid Knust

Discrete Mathematics and Mathematical Programming

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

45 Citations (Scopus)

Abstract

We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additionally precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques.

Original language	Undefined
Pages (from-to)	231-239
Number of pages	9
Journal	Operations research letters
Volume	29
Issue number	5
DOIs	https://doi.org/10.1016/S0167-6377(01)00104-3
Publication status	Published - Dec 2001

Keywords

METIS-203189
IR-63578
EWI-7582
MSC-90B35

Access to Document

10.1016/S0167-6377(01)00104-3

http://eprints.eemcs.utwente.nl/secure2/7582/01/ORLetters.pdf

Cite this

@article{517639efddca471c93b6869cdf1853d1,

title = "List scheduling in a parallel machine environment with precedence constraints and setup times",

abstract = "We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additionally precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques.",

keywords = "METIS-203189, IR-63578, EWI-7582, MSC-90B35",

author = "Hurink, {Johann L.} and Sigrid Knust",

year = "2001",

month = dec,

doi = "10.1016/S0167-6377(01)00104-3",

language = "Undefined",

volume = "29",

pages = "231--239",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - List scheduling in a parallel machine environment with precedence constraints and setup times

AU - Hurink, Johann L.

AU - Knust, Sigrid

PY - 2001/12

Y1 - 2001/12

N2 - We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additionally precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques.

AB - We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additionally precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques.

KW - METIS-203189

KW - IR-63578

KW - EWI-7582

KW - MSC-90B35

U2 - 10.1016/S0167-6377(01)00104-3

DO - 10.1016/S0167-6377(01)00104-3

M3 - Article

VL - 29

SP - 231

EP - 239

JO - Operations research letters

JF - Operations research letters

SN - 0167-6377

IS - 5

ER -