One of the best theses on scheduling with CP is the one of Petr Vilim available here but this new one entitled: Cumulative scheduling with overloads : global constraints and decompositions by Alexis De Clercq is definitively a thesis I have to read soon (unfortunately thesis in France are written in French, but you can still read associated papers). Here is the abstract of the thesis:
Constraint programming is an interesting approach to solve scheduling problems. In cumulative scheduling, activities are defined by their starting date, their duration and the amount of resource necessary for their execution. The total available resource at each point in time (the capacity) is fixed. In constraint programming, the CUMULATIVE global constraint models this problem.
In several practical cases, the deadline of the project is fixed and can not be delayed. In this case, it is not always possible to find a schedule that does not lead to an overload of the resource capacity. It can be tolerated to relax the capacity constraint, in a reasonable limit, to obtain a solution.
We propose a new global constraint : the SOFTCUMULATIVE constraint that extends the CUMULATIVE constraint to handle these overloads. We illustrate its modeling power on several practical problems, and we present various filtering algorithms. In particular, we adapt the sweep and Edge-Finding algorithms to the SOTCUMULATIVE constraint. We also show that some practical problems require to impose overloads to satisfy business rules, modelled by additional constraints. We present an original filtering procedure to deal with these imposed overloads. We complete our study by an approach by decomposition. At last, we test and validate our different resolution techniques through a series of experiments.
