Constraint Programming in Practice: Scheduling a Rehearsal

The basic principles of constraint programming (constraint satisfaction problems, search, constraint propagation) are introduced by discussing how constraint programming can be used to solve a specific optimization problem. A set of orchestral pieces is to be rehearsed and the problem requires finding a sequence that will minimize the time that players are at the rehearsal but not playing, if they arrive for the first piece they are involved in and leave after the last. A constraint programming model of this problem is presented. A similar problem arises in ‘talent scheduling’ in shooting a film; improvements to the basic model are given that allow a larger instance of this kind to be solved.