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

Research output: Book/ReportReportOther research output

219 Downloads (Pure)


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
Publication statusPublished - 2000

Publication series

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


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

Cite this