Research Talk: Modern Constraint Programming Methods for Solving Hard Scheduling Problems Alexander Tesch (BoolAI, Zuse-Institute Berlin)

Abstract

In recent years, Constraint Programming (CP) has manifested as an often superior alternative to MIP for solving combinatorially difficult scheduling problems. At the core of such hard scheduling problems stands the global “cumulative” constraint which guarantees that jobs are scheduled such that a maximum resource capacity is not exceeded. In this talk, we will give a comprehensive overview on current checking- and propagation algorithms for cumulative and how they are implemented within a modern CP solver. We will give evidence for the computational efficiency of the presented algorithms on a small selection of computationally hard scheduling problems.