Incremental Maintenance of Double Precedence Graphs: A Constraint-Based Approach

Reasoning on precedence relations is crucial for many planning and scheduling systems. In this paper we propose a double precedence graph where direct precedence relations are kept additionally to traditional precedence relations (A can directly precede B if no activity must be allocated between A and B). Such precedence relations are motivated by solving problems like modelling sequence-dependent setup times or describing state transitions. We describe a constraint-based model for double precedence graphs and present incremental propagation rules for maintaining the transitive closure of the graph