Problem and Heuristic Space Search Strategies for Job Shop Scheduling
Robert H. Storer, S. David Wu, Renzo Vaccari
ORSA Journal on Computing · 1995 · Volume 7 · Issue 4
Abstract
In a recent paper we discussed “problem” and “heuristic” spaces which serve as a basis for local search in job shop scheduling problems. By encoding schedules as heuristic, problem pairs (H,P) search spaces can be defined by perturbing problem data and/or heuristic parameters. In this paper we attempt to determined, through computational testing, how these spaces can be successfully searched. Well known local search strategies are applied in problem and heuristic space and compared to Shifting Bottleneck heuristics, and to probabilistic dispatching methods. An interesting result is the good performance of genetic algorithms in problem space. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
programming, integer, algorithms, heuristic, production/scheduling: sequencing, deterministic, multiple machine, heuristic search genetic algorithms, job shop scheduling
Enable JavaScript for citation tools and additional paper interactions.