Constraint programming algorithms and models for scheduling applications

Time-related optimization problems are very hard to solve. Scheduling covers a subcategory of such problems where the goal is to place events in time. The discretization of time triggers a rapid growth of possible placements, leading to large search spaces. While scheduling problems were already computationally solved two decades ago, large real-world sized instances seemed to be out of reach back then. The recent gain of computational power brought by modern computers is not large enough to counter the combinatorial explosion of scheduling problems. However, with the recent developments of these two last decades, new promising resolution techniques have emerged. One of these techniques that will be at the core of this thesis is Constraint Programming (CP). This paradigm allows to express declaratively discrete constrained optimization problems. This thesis achieves two main goals. First, we design new abstractions and techniques to enrich the set of tools CP can use to solve Scheduling problems. Second, we prove that CP is able to solve large instances of real-world scheduling problems in short amounts of time. Several new scheduling abstractions for CP are introduced in this thesis. The two most important ones are the conception of two new propagation procedures useful for time- related problems. Propagation is a mechanism of CP that allows to remove parts of the search space that are provably unfeasible, i.e., that do not contain any feasible solutions. The first propagation procedure introduced performs Forward-Checking propagation for the Nested Global Cardinality Constraint (Nested GCC). This constraint allows to bound the number of occurrences of values on nested ranges of variables. The second propagation procedure is designed for a new constraint: the unary resource with transition times. This constraint forbids a group of activities to overlap in time and imposes a minimal delay between each pair of activities from this group. We apply CP scheduling resolution techniques on four industrial problems. These four problems take place in two main sectors of activity: medical treatment centers and industrial production. The tree first problems attempt at scheduling the steps followed by patients in radiotherapy treatment centers. The last problem aims at reducing the energy costs of industrial sites by shifting their most energy-demanding production tasks when electricity prices are the lowest. These four problems have been solved on either realistic generated instances or on historical instances. By coupling CP with Large Neighborhood Search, a diversification strategy, we have been able to provide high quality solutions to these four problems.(FSA - Sciences de l'ingénieur) -- UCL, 201