Problem and heuristic space search strategies for job shop scheduling

In an earlier 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 determine, 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.