Constraint programming has been widely applied in the area of scheduling, enabling the implementation of flexible scheduling systems. Over the last ten years, the flexibility offered by CP has been combined with the efficiency of specialized Operations Research algorithms. As a result, CP tools dedicated to scheduling are now claimed to be fast, efficient and easy to use.
In this talk, I will show that this claim is partially true and that, indeed, constraint-based schedulers behave very well on a rather large class of problems. However, there are several scheduling situations in which CP does not work. I will try to indentify the key ingredients that make scheduling problems hard for CP. I will also introduce new mixed integer formulations that could compete/cooperate with CP for such problems.