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

T. Brueggemann; Johann L. Hurink; T. Vredeveld; Gerhard Woeginger

doi:10.1007/978-3-540-77918-6_4

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

T. Brueggemann, Johann L. Hurink, T. Vredeveld, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	Undefined
Title of host publication	5th International Workshop on Approximation and Online Algorithms
Editors	C. Kaklamanis, M. Skutella
Place of Publication	Berlin
Publisher	Springer
Pages	41-54
Number of pages	17
ISBN (Print)	978-3-540-77917-9
DOIs	https://doi.org/10.1007/978-3-540-77918-6_4
Publication status	Published - 9 Feb 2008
Event	6th International Workshop on Approximation and Online Algorithms 2008 - Karlsruhe, Germany Duration: 18 Sep 2008 → 19 Sep 2008 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	4927
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	6th International Workshop on Approximation and Online Algorithms 2008
Abbreviated title	WAOA 2008
Country/Territory	Germany
City	Karlsruhe
Period	18/09/08 → 19/09/08

Keywords

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

Access to Document

10.1007/978-3-540-77918-6_4

http://eprints.eemcs.utwente.nl/secure2/11999/01/LNCS-final.pdf

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). Springer. https://doi.org/10.1007/978-3-540-77918-6_4

@inproceedings{b37e0fcc3c194aa6abcc20495e918235,

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 ${\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.",

keywords = "EWI-11999, MSC-68W25, IR-62189, METIS-250882, MSC-90B35",

author = "T. Brueggemann and Hurink, {Johann L.} and T. Vredeveld and Gerhard Woeginger",

note = "10.1007/978-3-540-77918-6_4 ; null ; Conference date: 18-09-2008 Through 19-09-2008",

year = "2008",

month = feb,

day = "9",

doi = "10.1007/978-3-540-77918-6_4",

language = "Undefined",

isbn = "978-3-540-77917-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "41--54",

editor = "C. Kaklamanis and M. Skutella",

booktitle = "5th International Workshop on Approximation and Online Algorithms",

}

Brueggemann, T, Hurink, JL, 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., 10.1007/978-3-540-77918-6_4, Lecture Notes in Computer Science, vol. 4927, Springer, Berlin, pp. 41-54, 6th International Workshop on Approximation and Online Algorithms 2008, Karlsruhe, Germany, 18/09/08. https://doi.org/10.1007/978-3-540-77918-6_4

Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. / Brueggemann, T.; Hurink, Johann L.; Vredeveld, T. et al.

5th International Workshop on Approximation and Online Algorithms. ed. / C. Kaklamanis; M. Skutella. Berlin : Springer, 2008. p. 41-54 10.1007/978-3-540-77918-6_4 (Lecture Notes in Computer Science; Vol. 4927).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Brueggemann, T.

AU - Hurink, Johann L.

AU - Vredeveld, T.

AU - Woeginger, Gerhard

N1 - Conference code: 6

PY - 2008/2/9

Y1 - 2008/2/9

N2 - 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.

AB - 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.

KW - EWI-11999

KW - MSC-68W25

KW - IR-62189

KW - METIS-250882

KW - MSC-90B35

U2 - 10.1007/978-3-540-77918-6_4

DO - 10.1007/978-3-540-77918-6_4

M3 - Conference contribution

SN - 978-3-540-77917-9

T3 - Lecture Notes in Computer Science

SP - 41

EP - 54

BT - 5th International Workshop on Approximation and Online Algorithms

A2 - Kaklamanis, C.

A2 - Skutella, M.

PB - Springer

CY - Berlin

Y2 - 18 September 2008 through 19 September 2008

ER -

Brueggemann T, Hurink JL, Vredeveld T, Woeginger G. Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. In Kaklamanis C, Skutella M, editors, 5th International Workshop on Approximation and Online Algorithms. Berlin: Springer. 2008. p. 41-54. 10.1007/978-3-540-77918-6_4. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-77918-6_4