Guided Local Search with Shifting Bottleneck for Job Shop Scheduling

Egon Balas and Alkis Vazacopoulos
Additional contact information
Alkis Vazacopoulos: Fairleigh Dickinson University, Madison, New Jersey 07940

Management Science, 1998, vol. 44, issue 2, 262-275

Abstract: Many recently developed local search procedures for job shop scheduling use interchange of operations, embedded in a simulated annealing or tabu search framework. We develop a new variable depth search procedure, GLS (Guided Local Search), based on an interchange scheme and using the new concept of neighborhood trees. Structural properties of the neighborhood are used to guide the search in promising directions. While this procedure competes successfully with others even as a stand-alone, a hybrid procedure that embeds GLS into a Shifting Bottleneck framework and takes advantage of the differences between the two neighborhood structures proves to be particularly efficient. We report extensive computational testing on all the problems available from the literature.

Keywords: Job Shop Scheduling; Local Search; Shifting Bottleneck; Neighborhood Trees (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.2.262 (application/pdf)

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:inm:ormnsc:v:44:y:1998:i:2:p:262-275

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().