Probe backtrack search for minimal perturbation in dynamic scheduling

This paper describes an algorithm designed to minimally reconfigure schedules in response to a changing environment. External factors have caused an existing schedule to become invalid, perhaps due to the withdrawal of resources, or because of changes to the set of scheduled activities. The total shift in the start and end times of already scheduled activities should be kept to a minimum. This optimization requirement may be captured using a linear optimization function over linear constraints. However, the disjunctive nature of the resource constraints impairs traditional mathematical programming approaches. The unimodular probing algorithm interleaves constraint programming and linear programming. The linear programming solver handles only a controlled subset of the problem constraints, to guarantee that the values returned are discrete. Using probe backtracking, a complete, repair-based method for search, these values are simply integrated into constraint programming. Unimodular probing is compared with alternatives on a set of dynamic scheduling benchmarks, demonstrating its effectiveness. In the final discussion, we conjecture that analogous probe backtracking strategies may obtain performance improvements over conventional backtrack algorithms for a broad range of constraint satisfaction and optimization problems.