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

Johann L. Hurink; S. Knust

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

Johann L. Hurink, S. Knust

Discrete Mathematics and Mathematical Programming

Research output: Book/Report › Report › Other research output

89 Downloads (Pure)

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
Place of Publication	Enschede
Publisher	University of Twente, Department of Applied Mathematics
Publication status	Published - 2000

Publication series

Name
Publisher	Department of Applied Mathematics, University of Twente
No.	1525
ISSN (Print)	0169-2690

Keywords

MSC-90B35
IR-65713
EWI-3345

Access to Document

1525
open
1525
open

Cite this

@book{82a1c270218a4e3eabbcee7d21f77f68,

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 = "MSC-90B35, IR-65713, EWI-3345",

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

note = "Imported from MEMORANDA",

year = "2000",

language = "Undefined",

publisher = "University of Twente, Department of Applied Mathematics",

number = "1525",

}

TY - BOOK

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

AU - Hurink, Johann L.

AU - Knust, S.

N1 - Imported from MEMORANDA

PY - 2000

Y1 - 2000

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 - MSC-90B35

KW - IR-65713

KW - EWI-3345

M3 - Report

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -