Stochastic procedures for generating feasible schedules

The use of stochastic variable and value ordering heuristics for solving job shop scheduling problems with non-relaxable deadlines and complex metric constraints is investigated. Stochastic counterparts are specified to previously developed search heuristics. Experimental results on job shop scheduling CSPs of increasing size demonstrate comparative advantage over chronological backtracking. Comparison is also made to heuristic-biased stochastic sampling (HBSS).