Exponential size neighborhoods for makespan minimization scheduling

Tobias Brueggemann, Johann L. Hurink, Tjark Vredeveld and Gerhard J. Woeginger

Naval Research Logistics (NRL), 2011, vol. 58, issue 8, 795-803

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. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011

Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.20485

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:58:y:2011:i:8:p:795-803

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().