Performance Analysis of Beam Search with Look Ahead

Abstract

This paper presents a heuristic search strategy called beam search and investigates its effectiveness by applying it to classical job shop scheduling problems. A look-ahead feature is incorporated in the strategy to detect potential resource conflicts. Benchmark problems and existing test cases are used in a performance analysis of the search strategy. The search strategy is implemented in a SUN SPARC station using Common-LISP. Our computational experience using this enhanced version of beam search on job shop scheduling problems are reported.