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 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.
Supported by the Netherlands Organization for Scientific Research (NWO) grant 613.000.225 (Local Search with Exponential Neighborhoods) and by BSIK grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society).
|Title of host publication||Approximation and Online Algorithms (5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers)|
|Editors||C. Kaklamanis, M. Skutella|
|Place of Publication||Berlin|
|Publication status||Published - 2008|
|Name||Lecture Notes in Computer Science|