Stochastic Procedures for Generating Feasible Schedules

Abstract

In this paper, we investigate the use of stochastic variable and value ordering heuristics for solving job shop scheduling problems with non-relaxable deadlines and complex metric constraints. Previous research in constraint satisfaction scheduling has developed highly effective, deterministic heuristics for this class of problems based on simple measures of temporal sequencing flexibility. However, they are not infallible, and the possibility of search failure raises the issue of how to most productively enlarge the search. Backtracking is one alternative, but such systematicity generally implies high computational cost. We instead design an iterative sampling procedure, based on the intuition that it is more productive to deviate from heuristic advice in cases where the heuristic is less informed, and likewise better to follow the heuristic in cases where it is more knowledgeable. We specify stochastic counterparts to previously developed search heuristics, which are parameterized to calibrate degree of randomness to level of discriminatory power. Experimental results on job shop scheduling CSPs of increasing size demonstrate comparative advantage over chronological backtracking. Comparison is also made to another, recently proposed iterative sampling technique called heuristic-biased stochastic sampling (HBSS). Whereas HBSS assumes a statically specified heuristic bias that is utilized at every application of the heuristic, our approach defines bias dynamically according to how well the heuristic discriminates alternatives.