Quality of Move-optimal Schedules for Minimizing Total Weigted Completion Time

T. Brueggemann; Johann L. Hurink; Walter Kern

doi:10.1016/j.orl.2005.08.003

Quality of Move-optimal Schedules for Minimizing Total Weigted Completion Time

T. Brueggemann, Johann L. Hurink, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

6 Downloads (Pure)

Abstract

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 1.5. In a special case, the approximation ratio is Click to view the MathML source.

Original language	Undefined
Article number	10.1016/j.orl.2005.08.003
Pages (from-to)	583-590
Number of pages	8
Journal	Operations research letters
Volume	34
Issue number	2/5
DOIs	https://doi.org/10.1016/j.orl.2005.08.003
Publication status	Published - Sept 2006

Keywords

IR-63169
MSC-90B35
EWI-6069
METIS-238073

Access to Document

10.1016/j.orl.2005.08.003

http://eprints.eemcs.utwente.nl/secure2/6069/01/OR-Letters-article.pdf

Cite this

@article{1af39dfd6a2c4b0ba60e0d548a606e0a,

title = "Quality of Move-optimal Schedules for Minimizing Total Weigted Completion Time",

abstract = "We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 1.5. In a special case, the approximation ratio is Click to view the MathML source.",

keywords = "IR-63169, MSC-90B35, EWI-6069, METIS-238073",

author = "T. Brueggemann and Hurink, {Johann L.} and Walter Kern",

note = "10.1016/j.orl.2005.08.003 ",

year = "2006",

month = sep,

doi = "10.1016/j.orl.2005.08.003",

language = "Undefined",

volume = "34",

pages = "583--590",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2/5",

}

TY - JOUR

T1 - Quality of Move-optimal Schedules for Minimizing Total Weigted Completion Time

AU - Brueggemann, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - 10.1016/j.orl.2005.08.003

PY - 2006/9

Y1 - 2006/9

N2 - We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 1.5. In a special case, the approximation ratio is Click to view the MathML source.

AB - We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio 1.5. In a special case, the approximation ratio is Click to view the MathML source.

KW - IR-63169

KW - MSC-90B35

KW - EWI-6069

KW - METIS-238073

U2 - 10.1016/j.orl.2005.08.003

DO - 10.1016/j.orl.2005.08.003

M3 - Article

SN - 0167-6377

VL - 34

SP - 583

EP - 590

JO - Operations research letters

JF - Operations research letters

IS - 2/5

M1 - 10.1016/j.orl.2005.08.003

ER -