List scheduling revisited

Research output: Contribution to journalArticleAcademicpeer-review

41 Citations (Scopus)
1199 Downloads (Pure)


We consider the problem of scheduling n jobs on m identical parallel machines to minimize a regular cost function. The standard list scheduling algorithm converts a list into a feasible schedule by focusing on the job start times. We prove that list schedules are dominant for this type of problem. Furthermore, we prove that an alternative list scheduling algorithm, focusing on the completion times rather than the start times, yields also dominant list schedules for problems with sequence dependent setup times.
Original languageUndefined
Pages (from-to)167-170
JournalOperations research letters
Issue number4
Publication statusPublished - 1996


  • IR-32185
  • METIS-144432

Cite this