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)
10 Downloads (Pure)


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 languageUndefined
Title of host publication5th International Workshop on Approximation and Online Algorithms
EditorsC. Kaklamanis, M. Skutella
Place of PublicationBerlin
Number of pages17
ISBN (Print)978-3-540-77917-9
Publication statusPublished - 9 Feb 2008
Event6th International Workshop on Approximation and Online Algorithms 2008 - Karlsruhe, Germany
Duration: 18 Sept 200819 Sept 2008
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Workshop6th International Workshop on Approximation and Online Algorithms 2008
Abbreviated titleWAOA 2008


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

Cite this