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

T. Brueggemann, Johann L. Hurink, Walter Kern

Research output: Book/ReportReportProfessional

47 Downloads (Pure)


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
Number of pages13
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

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


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

Cite this