Constraint-based scheduling and planning

This chapter describes constraint-based scheduling as the discipline that studies how to solve scheduling problems by using constraint programming (CP). Constraint-based planning in turn is the discipline that studies how to solve planning problems by CP. The chapter discusses that constraint-based scheduling is one of the most successful application areas of CP. One of the key factors of this success lies in the fact that a combination was found of the best of two fields of research that pay attention to scheduling—namely, operations research (OR) and artificial intelligence (AI). The chapter reviews that OR approach aims at achieving a high level of efficiency in its algorithms whereas AI research tends to investigate more general scheduling models and tries to solve the problems by using general problem-solving paradigms. The use of CP in planning is because of the problem complexity, which is less mature than its use in scheduling. Constraint-based planning thus follows the same pattern as constraint-based scheduling where CP is used as a framework for integrating efficient special purpose algorithms into a flexible and expressive paradigm. It also presents CP models for scheduling together with descriptions of propagation techniques for constraints used in these models