Problem and Heuristic Space Search Strategies for Job Shop Scheduling

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.