Invited Session Mon.1.H 3003A

Monday, 10:30 - 12:00 h, Room: H 3003A

Cluster 5: Constraint programming [...]

Constraint-based scheduling


Chair: Petr Vilím



Monday, 10:30 - 10:55 h, Room: H 3003A, Talk 1

André Augusto Cire
MDD propagation for disjunctive scheduling

Coauthor: Willem van Hoeve


Disjunctive scheduling refers to a wide range of problems in which activities must be scheduled on a resource capable of processing only one operation at a 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 constraint propagation methods based on limited-width Multivalued Decision Diagrams (MDDs), which represent a relaxation of the feasible sequences of activities that must be scheduled on the resource. 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.



Monday, 11:00 - 11:25 h, Room: H 3003A, Talk 2

Philippe Laborie
Conditional interval variables: A powerful concept for modeling and solving complex scheduling problems


Scheduling is not only about deciding when to schedule a predefined set of activities. Most of real-world scheduling problems also involve selecting a subset of activities (oversubscribed problems) and a particular way to execute them (resource or mode allocation, alternative recipes, pre-emptive activity splitting, etc.). We introduce the notion of a conditional interval variable in the context of Constraint Programming (CP) and show how this concept can be leveraged to model and solve complex scheduling problems involving both temporal and non-temporal decisions. The presentation will be illustrated with IBM ILOG CPLEX CP Optimizer, a CP based optimization engine implementing this concept.


  Getting Payday Loans In California should be thought of many times. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.