Exponential size neighborhoods for makespan minimization scheduling

Brueggemann, Tobias and Hurink, Johann and Vredeveld, Tjark and Woeginger, Gerhard J. (2011) Exponential size neighborhoods for makespan minimization scheduling. Naval Research Logistics, 58 (8). pp. 795-803. ISSN 0894-069X

PDF
Restricted to UT campus only: Request a copy
124Kb

Abstract:	We investigate the quality of local search heuristics for the scheduling problem of minimizing the makespan on identical parallel machines. We study exponential size neighborhoods (whose size grows exponentially with the input length) that can be searched in polynomial time, and we derive worst-case approximation guarantees for the local optima of such neighborhoods. The so-called split neighborhood splits a feasible schedule into two layers, and then recombines the two layers by finding a perfect matching. We show that the makespan of every local optimum for split is at most a factor of 2 away from the globally optimal makespan. We then combine the split neighborhood with two neighborhoods from the literature. The combination of split with the jump neighborhood only marginally improves the approximation guarantee, whereas the combination with the lexicographic-jump neighborhood decreases the approximation guarantee from 2 to 3/2.
Item Type:	Article
Copyright:	© 2011 Wiley
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/78405
Official URL:	http://dx.doi.org/10.1002/nav.20485
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 279686