@inproceedings{d7f96c0001084c228bfe6e8e62f25284,
title = "Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines",
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 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).",
author = "T. Br{\"u}ggemann and J.L. Hurink and T. Vredeveld and G.J. Woeginger",
year = "2008",
doi = "10.1007/978-3-540-77918-6_4",
language = "English",
isbn = "978-3-540-77917-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "41--54",
editor = "C. Kaklamanis and M. Skutella",
booktitle = "Approximation and Online Algorithms (5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers)",
address = "Germany",
}