List scheduling revisited

Research output: Contribution to journalArticleAcademicpeer-review

33 Citations (Scopus)
554 Downloads (Pure)

Abstract

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
Volume18
Issue number4
DOIs
Publication statusPublished - 1996

Keywords

  • IR-32185
  • METIS-144432

Cite this

@article{cacf930cccef4b0b95df6a5782500c0e,
title = "List scheduling revisited",
abstract = "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.",
keywords = "IR-32185, METIS-144432",
author = "Schutten, {Johannes M.J.}",
year = "1996",
doi = "10.1016/0167-6377(95)00057-7",
language = "Undefined",
volume = "18",
pages = "167--170",
journal = "Operations research letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "4",

}

List scheduling revisited. / Schutten, Johannes M.J.

In: Operations research letters, Vol. 18, No. 4, 1996, p. 167-170.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - List scheduling revisited

AU - Schutten, Johannes M.J.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - IR-32185

KW - METIS-144432

U2 - 10.1016/0167-6377(95)00057-7

DO - 10.1016/0167-6377(95)00057-7

M3 - Article

VL - 18

SP - 167

EP - 170

JO - Operations research letters

JF - Operations research letters

SN - 0167-6377

IS - 4

ER -