Guided local search with shifting bottleneck for job shop scheduling

Egon Balas, Alkis Vazacopoulos

Research output: Contribution to journalArticlepeer-review

314 Scopus citations

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.

Original languageEnglish
Pages (from-to)262-275
Number of pages14
JournalManagement Science
Volume44
Issue number2
DOIs
StatePublished - Feb 1998

Keywords

  • Job Shop Scheduling
  • Local Search
  • Neighborhood Trees
  • Shifting Bottleneck

Fingerprint

Dive into the research topics of 'Guided local search with shifting bottleneck for job shop scheduling'. Together they form a unique fingerprint.

Cite this