Very LargeScale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines
Brueggemann, T. and Hurink, J.L. and Vredeveld, T. and Woeginger, G.J. (2006) Very LargeScale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines. [Report]

PDF
235kB 
Abstract:  We study the problem of minimizing the makespan on m parallel machines. We introduce a very largescale 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. 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/66526 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 238241