MDD Propagation for Disjunctive Scheduling

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.