A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling

Abstract

Di sjun ct ive cons tr aints are widely used to ensure that th e tim e int ervals ov er which two activit ies require th e sam e resource c annot overlap: if a resource is required by two activities A and B , th e disjun ctive constraint st ates that eith er A precedes B or B precedes A . Th e "propagat ion" of disjunctive constraints consists in dete rmining cas es where only one of the two orderings is feasibl e. It results in updating the tim e -bounds of the two activities. The standard algorithm for propagating disjunctive const raints achieves arc-H -consistency. Two types of m e th ods that provide mor e precise tim ebounds are studi ed and compar ed . The first typ e of me thod consists in determining whether an activity A must , can , or cannot be the first or th e last to exe cut e among a set of activities that require th e same resource. The second consists in comparing the amount of "resource energy" required ov er a time int erval [t1 t2) to th e a mount of energy that is available over the same int erval. Th e main result of the study is an impleme ntation of th e first me thod in ILOG Sc HEDULE , a generic tool for constraint-based sc heduling whi ch exhibits performan ce in the sam e range of e ffici ency as specific operations research algorithms .