Hybrid Constraint Tightening for Solving Hybrid Scheduling Problems

Abstract

Hybrid Scheduling Problems (HSPs) contain both temporal and finite-domain variables, as well as constraints between them. A hybrid constraint over temporal and finite-domain variables often models situations where different assign-ments to a subset of finite-domain variables result in differ-ent bounds on temporal constraints. The insight we ex-amine in this paper is that some temporal constraint propa-gation is possible even before finite-domain variables are assigned, by giving the temporal constraint the tightest bound consistent with all (remaining) feasible finite-domain variable values. We describe a hybrid constraint-tightening algorithm that can proactively prune the search space of HSPs and is run as a preprocessing step independently of the search algorithm used. We examine the efficiency of this algorithm analytically, and give preliminary results showing that it reduces the expected runtime of search by a significant margin in the kinds of HSPs we are studying.