Constraint-Based Schedulers Do They Really Work? PDF
Document Details
Uploaded by GoodlySloth8585
2009
Philippe Baptiste
Tags
Summary
This paper examines constraint-based schedulers for scheduling systems, noting that while they are often efficient for a wide range of problems, some scheduling scenarios are challenging for constraint programming (CP) approaches. The author plans to discuss these challenging scenarios and potentially integrate mixed integer formulations to address them.
Full Transcript
Constraint-Based Schedulers, Do They Really Work? Philippe Baptiste CNRS LIX, Ecole Polytechnique, 91128 Palaiseau, France [email protected]...
Constraint-Based Schedulers, Do They Really Work? Philippe Baptiste CNRS LIX, Ecole Polytechnique, 91128 Palaiseau, France [email protected] Constraint programming has been widely applied in the area of scheduling, en- abling 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. I.P. Gent (Ed.): CP 2009, LNCS 5732, p. 1, 2009. c Springer-Verlag Berlin Heidelberg 2009
