Hybrid Constraint Tightening for Solving Hybrid Scheduling Problems

James Boerkoel, Edmund Durfee

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 assignments to a subset of finite-domain variables result in different bounds on temporal constraints. The insight we examine in this paper is that some temporal constraint propagation 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 mar-gin in the kinds of HSPs we are studying.

Subjects: 15.2 Constraint Satisfaction; 1.12 Scheduling

Submitted: Apr 15, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.