# Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines

T. Brueggemann, Johann L. Hurink, T. Vredeveld, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

### Abstract

We study the problem of minimizing the makespan on $m$ parallel machines. We introduce a very large-scale neighborhood of exponential size (in the number of machines) that is based on a matching in a complete graph. The idea is to partition for every machine the set of assigned jobs into two sets by some fixed rule and then to reassign these $2m$ parts such that every machine gets exactly two parts. The split neighborhood consists of all possible reassignments of the parts and a best neighbor can be calculated in ${\cal O}(m \log m)$ by determining a perfect matching with minimum maximal edge weight. We examine local optima in the split neighborhood and in combined neighborhoods consisting of the split and other known neighborhoods and derive performance guarantees for these local optima.
Original language Undefined 5th International Workshop on Approximation and Online Algorithms C. Kaklamanis, M. Skutella Berlin Springer 41-54 17 978-3-540-77917-9 https://doi.org/10.1007/978-3-540-77918-6_4 Published - 9 Feb 2008 6th International Workshop on Approximation and Online Algorithms 2008 - Karlsruhe, GermanyDuration: 18 Sep 2008 → 19 Sep 2008Conference number: 6

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 4927 0302-9743 1611-3349

### Workshop

Workshop 6th International Workshop on Approximation and Online Algorithms 2008 WAOA 2008 Germany Karlsruhe 18/09/08 → 19/09/08

• EWI-11999
• MSC-68W25
• IR-62189
• METIS-250882
• MSC-90B35

### Cite this

Brueggemann, T., Hurink, J. L., Vredeveld, T., & Woeginger, G. (2008). Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. In C. Kaklamanis, & M. Skutella (Eds.), 5th International Workshop on Approximation and Online Algorithms (pp. 41-54). [10.1007/978-3-540-77918-6_4] (Lecture Notes in Computer Science; Vol. 4927). Berlin: Springer. https://doi.org/10.1007/978-3-540-77918-6_4