cbs-tutorial

--*Constraint-based SchedulingMarkus P.J. FromherzXerox PARC, 3333 Coyote Hill Road, Palo Alto, CA 94304, USAwww.parc.com/fromherzAbstract resources, constraints, and objectives from thealgorithms that solve the problem. This allows oneConstraint-based scheduling has become the to deal with a wider variety of constraints, facili-dominant form of modeling and solving scheduling tates the changing of the model, even dynamically,problems. Recently, due to ever more powerful em- without changing the algorithms, and enables thebedded processors, it has become possible to embed re-use of the model for other tasks, such as simula-and run constraint-based schedulers on-line even tion, planning, and diagnosis. Constraint solvingfor fast processes such as product assembly se- methods such as domain reduction, constraintquencing. This makes constraint-based scheduling propagation, and backtracking search have provedinteresting to the control community as a new tool to be well suited for many industrial applicationsfor system control, distributed and reconfigurable [23,17]. Today, these methods are increasinglycontrol, and the integration of various planning, combined with classic solving techniques from Op-scheduling, and control tasks. This tutorial gives a erations Research (OR), such as linear, integer,brief introduction to constraint-based scheduling, and mixed integer programming [5,37], to yieldgeneric constraint programming techniques for powerful tools ...