### 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 |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 13 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2005 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | Department 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.