Proceedings:
Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling
Volume
Issue:
Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling
Track:
Full Technical Papers
Downloads:
Abstract:
Disjunctive scheduling is the problem of scheduling activities that must not overlap in time. Constraint-based techniques, such as edge finding and not first/not-last rules, have been a key element in successfully tackling large and complex disjunctive scheduling problems in recent years. In this work we investigate new propagation methods based on limited-width Multivalued Decision Diagrams (MDDs). We present theoretical properties of the MDD encoding and describe filtering and refinement operations that strengthen the relaxation it provides. Furthermore, we provide an efficient way to integrate the MDD-based reasoning with state-of-the-art propagation techniques for scheduling. Experimental results indicate that the MDD propagation can outperform existing domain filters especially when minimizing sequence dependent setup times, in certain cases by several orders of magnitude.
DOI:
10.1609/icaps.v22i1.13521
ICAPS
Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling