---
title: "A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling"
authors:
  - "Philippe Baptiste"
  - "Claude Le Pape"
doi: ""
url: "https://ijcai.org/proceedings/1995/79"
pdf: "https://ijcai.org/proceedings/1995/0079.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "600-605"
track: "Constraint Satisfaction"
keywords:
---

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

Philippe Baptiste, Claude Le Pape

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 600-605.

## 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 .