Constraint Satisfaction for Planning and Scheduling

Abstract

As the current planning and scheduling technologies are coming together by assuming time and resource constraints in planning or by allowing introduction of new activities during scheduling, the role of constraint satisfaction as the bridging technology is increasing and so it is important for researchers in these areas to understand the underlying principles and techniques. The chapter introduces constraint satisfaction technology with emphasis on its applications in planning and scheduling. It gives a brief survey of constraint satisfaction in general, including a description of mainstream solving techniques, that is, constraint propagation combined with search. Then, it focuses on specific time and resource constraints and on search techniques and heuristics useful in planning and scheduling. Last but not least, the basic approaches to constraint modelling for planning and scheduling problems are presented.