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.


  Payday Loans In Indiana. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.