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

Research output: Book/ReportReportOther 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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2000

Publication series

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

Keywords

  • MSC-90B35
  • IR-65713
  • EWI-3345

Cite this