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


Share/Save/Bookmark

Brueggemann, T. and Hurink, J.L. and Vredeveld, T. and Woeginger, G.J. (2008) Very large-scale neighborhoods with performance guarantees for minimizing makespan on parallel machines. In: 5th International Workshop on Approximation and Online Algorithms, October 11-12, 2007, Eilat, Israel (pp. pp. 41-54).

[img] PDF
Restricted to UT campus only
: Request a copy
521kB
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.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62189
Official URL:http://dx.doi.org/10.1007/978-3-540-77918-6_4
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 250882