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

T. Brueggemann, Johann L. Hurink, Walter Kern

Research output: Book/ReportReportProfessional

### 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 language Undefined Enschede University of Twente, Department of Applied Mathematics 13 0169-2690 Published - 2005

### Publication series

Name Memorandum Afdeling TW Department of Applied Mathematics, University of Twente 1748 0169-2690

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