3.6.14. Modelling exercises
Assigning and scheduling tasks that run in parallel:Β Β inspired by a modelling question on the Choco mailing list about an assignment and scheduling problem involving nurses and surgeons, use one constraint as well as inequalities for breaking symmetries with respect to groups of identical persons. The keyword relaxation dimension shows how to extend the previous model in order to take into account over-constrained assignment and scheduling problems.
Assignment to the same set of values:Β Β inspired by a presentation of F.Β Hermenier about a task assignment problem where subtasks have to be assigned a same group of machines, use several constraints and a single resource constraint that has an assignment dimension (e.g.,Β , , , ).
Degree of diversity of a set of solutions:Β Β inspired by a discussion with E.Β Hebrard, how to find out 9 completely different solutions for the 10-queens problem, use the , the and the constraints.
Logigraphe:Β Β inspired by an instance fromΒ [Pitrat08], use a conjunction of constraints.
Magic series:Β Β a special case of Autoref, use a single constraint.
Metro:Β Β a model from H.Β Simonis, use only constraints and propagation (i.e., no enumeration) for modelling the shortest path problem in a network.
Multi-site employee scheduling with calendar constraints:Β Β a timetabling problem, inspired by H.Β Simonis, where tasks have to be assigned groups of employes located in different countries subject to different calendars, use resource constraints as well as the constraint.
n-Amazons:Β Β an extension of the n-queens problem, use one constraint, two constraints and three constraints.
relaxation dimension:Β Β illustrate how to model over-constrained placement problems by introducing an extra dimension in the context of the and the constraints.
Scheduling with machine choice, calendars and preemption:Β Β a scheduling problem with crossable and non-crossable unavailability periods as well as resumable and non-resumable tasks, illustrate the use of two time coordinates systems within the same model, use precedence and resource constraints as well as the constraint.
Sequence dependent set-up:Β Β a classical scheduling problem, use the , and constraints.
Zebra puzzle:Β Β illustrate the duality of choice of what is a variable and what is a value in a constraint model as well as the difficulty of stating the constraints in one of the two models, use the , the β with variables in the table β and the constraints.
Denotes that a keyword describes a constraint modelling exercise.