Move-optimal schedules for parallel machines to minimize total weighted completion time

T. Brueggemann, Johann L. Hurink, Walter Kern

Research output: Book/ReportReportProfessional

18 Downloads (Pure)

Abstract

We study the minimum total weighted completion time problem on identical machines, which is known to be strongly $\mathcal{NP}$-hard. 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 case all jobs have equal Smith ratios, the approximation ratio is at most $1.092$.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages13
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1748
ISSN (Print)0169-2690

Keywords

  • MSC-90B35
  • METIS-225250
  • IR-65932
  • EWI-3568

Cite this

Brueggemann, T., Hurink, J. L., & Kern, W. (2005). Move-optimal schedules for parallel machines to minimize total weighted completion time. (Memorandum Afdeling TW; No. 1748). Enschede: University of Twente, Department of Applied Mathematics.