### Abstract

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

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

}

*Move-optimal schedules for parallel machines to minimize total weighted completion time*. Memorandum Afdeling TW, no. 1748, University of Twente, Department of Applied Mathematics, Enschede.

**Move-optimal schedules for parallel machines to minimize total weighted completion time.** / Brueggemann, T.; Hurink, Johann L.; Kern, Walter.

Research output: Book/Report › Report › Professional

TY - BOOK

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

AU - Brueggemann, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2005

Y1 - 2005

N2 - 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$.

AB - 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$.

KW - MSC-90B35

KW - METIS-225250

KW - IR-65932

KW - EWI-3568

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -