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

Publication series

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

Workshop

Workshop6th International Workshop on Approximation and Online Algorithms 2008
Abbreviated titleWAOA 2008
CountryGermany
CityKarlsruhe
Period18/09/0819/09/08

Keywords

  • 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