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

T. Brüggemann, J.L. Hurink, T. Vredeveld, G.J. 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 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).
Original languageEnglish
Title of host publicationApproximation and Online Algorithms (5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers)
EditorsC. Kaklamanis, M. Skutella
Place of PublicationBerlin
PublisherSpringer
Pages41-54
ISBN (Print)978-3-540-77917-9
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
Volume4927
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines'. Together they form a unique fingerprint.

Cite this