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

T. Brueggemann, Johann L. Hurink, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

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 languageUndefined
Article number10.1016/j.orl.2005.08.003
Pages (from-to)583-590
Number of pages8
JournalOperations research letters
Volume34
Issue number2/5
DOIs
Publication statusPublished - Sep 2006

Keywords

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

Cite this