Template-type: ReDif-Paper 1.0
Author-Name: Brueggemann Tobias 
Author-Name: Hurink Johann L. 
Author-Name: Vredeveld Tjark 
Author-Name: Woeginger Gerhard J. 
Author-workplace-name: METEOR
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 the jobs assigned to the same machine into two sets. This partitioning is done for every machine with some chosen rule to receive 2m parts. A new assignment is received by putting to every machine exactly two parts. The neighborhood Nsplit consists of all possible rearrangements of the parts to the machines. The best assignment of Nsplit can be calculated in time O(mlogm) by determining the perfect matching having minimum maximal edge weight in an improvement graph, where the vertices correspond to parts and the weights on the edges correspond to the sum of the processing times of the jobs belonging to the parts. Additionally, we examine local optima in this neighborhood and in combinations with other neighborhoods. We derive performance guarantees for these local optima.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2006
Number: 052
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:4fc740cb-08cc-4875-baff-ba6edfd449b5/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 241549
Handle: RePEc:unm:umamet:2006052