|This tutorial is sponsored by PLANET, the European
Network of Excellence in AI Planning.
Philippe Laborie , ILOG S.A., France
Wim Nuijten , ILOG S.A., France
The objective of the tutorial is to give an overview of both the
most widely used techniques as well as new emerging techniques in
Constraint-Based Scheduling. The tutorial is particularly addressed to
A.I. Planning or Scheduling researchers who are interested in a
flexible framework in which AI Planning and Scheduling can smoothly be
Constraint Programming is a problem-solving paradigm that
establishes a clear distinction between two pivotal aspects of a
problem: (1) a precise definition of the constraints that define the
problem to be solved and (2) the algorithms and heuristics enabling
the selection of decisions to solve the problem. It is because of
these capabilities that Constraint Programming is increasingly being
employed as a tool to solve scheduling problems. Hence the
development of Constraint-Based Scheduling as a field of study.
This tutorial provides an overview of the most widely used or
emerging Constraint-Based Scheduling techniques. It particularly
emphasizes the features of Constraint-Based Scheduling that makes it a
good framework for integrating A.I. Planning and Scheduling.
The first part of the tutorial provides an overview of Constraint
Programming as well as a model for representing scheduling problems in
the Constraint Programming framework. Some classical examples of
scheduling problems are given. The end of this introductory part
investigates the relations between Scheduling and
A.I. Planning. Following the clear distinction between (1) constraint
propagation and (2) search space exploration provided by the
Constraint Programming paradigm, those two aspects are treated in the
second and third parts of the tutorial. The second part is focused on
the propagation of resource constraints, which usually are responsible
for the "hardness" of a scheduling problem. The notion of a global
constraint is introduced as a constraint that enforces a set of local
properties on the partial schedule. The different techniques to
propagate global resource constraints are then classified, described
and compared. The third part of the tutorial presents some classical
search techniques in Constraint-Based Scheduling. It describes the
most classical branching schemes and control of the search as well as
some widely used techniques to deal with large and/or hard
problems. In order to show how to put things together, the resolution
of two scheduling problems is described in the last part. These
examples illustrate the use and the practical efficiency and
flexibility of the Constraint-Based Scheduling approach.
Some knowledge about Constraint Programming and Scheduling is an
advantage but is not required as the first part of the tutorial will
recap the main notions. Some basic knowledge about Partial Order
Planning may also be useful.
About the lecturers:
Dr. Philippe Laborie graduated from Ecole Nationale
Supérieure des Télécommunications (Paris) in
1992, and received a PhD in Artificial Intelligence from LAAS/CNRS
(Toulouse) on the integration of A.I. Planning and Scheduling in 1995.
He is one of the developers of the IXTET Planning system. He then worked for two years as
post-doctoral fellow at Electricité de France (Paris) and
INRIA/IRISA (Rennes) on the Supervision and Diagnosis of complex
systems (telecommunication and power distribution networks). His main
scientific interests include planning, scheduling, supervision and
diagnosis of complex systems and more generally, all decision problems
dealing with time. Since 1998 he has been at ILOG S.A. in Gentilly,
France, where he currently holds the position of Principal Scientist.
Dr. Wim Nuijten is Director of Optimization Technology at
ILOG S.A. His main interests lie in using constraint programming,
local search, mathematical programming, and their combination to solve
scheduling problems. He received his MSc (cum laude) in 1990 and his
PhD in 1994 from the Department of Mathematics and Computing Science
of Eindhoven University. From 1992-1994 he was a consultant at RIKS
in Maastricht. Begin 1995 he joined ILOG as a software developer,
where later that year he became the Project Manager of ILOG
Scheduler. In the years that followed Dr. Nuijten was a driving force
behind making ILOG Scheduler the industrial success it is today. He
was closely involved in the introduction and successful application of
constraint-based scheduling in several major companies, amongst which
SAP and Oracle. Since mid 1999 he is in his current position and leads
a team of about 15 researchers that develop an array of constraint
Here is a preliminary overview of the tutorial. Note that this is
subject to minor changes.
- Basic Principles
- Constraint Programming
- Definition of a Constraint Satisfaction Problem (CSP)
- Constraint propagation [23,4]
- Search techniques (heuristics, search tree exploration: DFS, LDS , ...)
- Optimizing objective functions
- Scheduling Model [2,15]
- Typology of activities: non-preemptive, preemptive
- Temporal constraints
- Typology of resources, Alternative resources
- Extensions: setup times/costs, resource efficiency, state resources
- Objective functions
- Examples of Scheduling Problems
- Resource constrained project scheduling problem with inventories and min/max time lags 
- Scheduling and AI Planning
- Relations with Partial Order Planning
- Local properties and Truth criterions [8,33]
- Propagation of Resource Constraints
- Global constraints
- From local properties to global constraints
- Close/not-close status of a resource
- A framework to classify resource propagation algorithms
- Algorithms based on activity time windows [26,9]
- Disjunctive constraint 
- Edge-Finding constraint 
- Not-first/not-last 
- Energetic reasonning [10,11]
- Algorithms based on relative position of activities
- Precedence energy constraint
- Balance constraint [7,20]
- Comparison and complementarity of propagation algorithms [1,2]
- Propagation of alternative resources
- Search Techniques
- Branching schemes
- Branching schemes as a way of enforcing non-deterministic local properties
- Classical branching schemes: resource allocation, setting times, ranking first/not first, activity or time-point pair ordering
- Search heuristics
- Texture-based heuristics 
- Beyong the basic search scheme
, Probing, Dichotomizing, large neiborhood search , etc.
- Putting things together on two examples
- Jobshop problem 
- Resource constrained project scheduling problem with inventories and min/max time lags 
P. Baptiste and C. LePape. A Theoretical and Experimental
Comparison of Constraint Propagation Techniques for Disjunctive
Scheduling. In Proceedings of the Fourteenth International Joint
Conference on Artificial Intelligence, 1995.
P. Baptiste, C. LePape, and W. Nuijten. Constraint-Based
Scheduling. Kluwer Academics Publishers, 2001.
- C. Beck, A. Davenport, E. Sitarski, and M. Fox. Texture-based
Heuristics for Scheduling Revisited. In Proceedings AAAI-97,
- C. Bessière and J.C. Régin. Refining the basic constraint
propagation algorithm. In Proceedings IJCAI'01, 2001.
- J. Carlier and E. Pinson. A Practical Use of Jackson's
Preemptive Schedule for Solving the Job-Shop Problem. Annal of
Operation Research, 26:269--287, 1990.
- A. Cesta, A. Oddi, and S. Smith. A constraint-based method for
project scheduling with time windows. Technical report, CMU RI
Technical Report, 2000.
- A. Cesta and C. Stella. A time and resource problem for planning
architectures. In ECP-97, 1997.
- D. Chapman. Planning for conjunctive goals. Artificial
Intelligence, 32:333--377, 1987.
- U. Dorndorf, T. Phan Huy, and E. Pesch. A survey of interval
capacity consistency tests for time and resource constrained
scheduling. In Project Scheduling - Recent Models, Algorithms and
Applications, Kluwer Academic Publ., pages 213--238, 1999.
- J. Erschler. Analyse sous contraintes et aide à la
décision pour certains problèmes d'ordonnancement. PhD
thesis, Université Paul Sabatier, 1976.
- J. Erschler, P. Lopez, and C. Thuriot. Raisonnement temporel
sous contraintes de ressources et problèmes d'ordonnancement.
Revue d'Intelligence Artificielle, 5(3):7--32, 1991.
- F. Focacci, P. Laborie, and W. Nuijten. Solving scheduling
problems with setup times and alternative resources. In Fifth
International Conference on Artificial Intelligence Planning and
Scheduling, pages 92--101, 2000.
- F. Garcia and P. Laborie. New Directions in AI Planning,
chapter Hierarchisation of the Search Space in Temporal Planning,
pages 217--232. IOS Press, Amsterdam, 1996.
- W. Harvey and M. Ginsberg. Limited discrepancy search. In In
Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, August 1995.
- ILOG. ILOG Scheduler 5.2
Reference Manual, 2001.
- A. Jain and S. Meeran. A state-of-the-art review of job-shop
scheduling techniques. Technical report, Department of Applied
Physics, Electronic and Mechanical Engineering, University of Dundee,
- S. Khambhampati and X. Yang. On the role of disjunctive
representations and constraint propagation in refinement planning. In
- C. Knoblock. Automatically generating abstractions for planning.
Artificial Intelligence, 68:243--302, 1994.
- V. Kumar. Algorithms for Cconstraint Satisfaction Problems: a
survey. AI magazine, 13(1):32--44, 1992.
- P. Laborie. Algorithms for Propagating Resource Constraints in
AI Planning and Scheduling: Existing Approaches and New Results. In
Proceedings ECP'01, 2001.
- P. Laborie and M. Ghallab.
Planning with sharable resource constraints.
In Fourteenth IJCAI, pages 1643--1649, 1995.
- C. Le Pape. Implementation of Resource Constraints in ILOG
Schedule: A Library for the Development of Constraint-Based Scheduling
systems. Intelligent Systems Engineering, 3(2):55--66,
- R. Mohr and T. Henderson. Arc and path consistency
revised. Artificial Intelligence, 28:225--233, 1986.
- K. Neumann and C. Schwindt. Project scheduling with inventory
constraints. Technical Report WIOR-572, Institut für
Wirtschaftstheorie und Operations Research. Universität
- X. Nguyen and S. Kambhampati. Reviving Partial Order lanning. In
Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, pages 459--464, 2001.
- W. Nuijten. Time and Resource Constrained Scheduling: A
Constraint Satisfaction Approach. PhD thesis, Eindhoven University
of Technology, 1994.
- D. Pacciarelli and A. Mascis. Job-shop scheduling of perishable
items. In INFORMS'99, 1999.
- D.E. Smith, J. Frank, and A.K. Jonsson. Bridging the gap between
planning and scheduling. Knowledge Engineering Review, 15(1),
- S. F. Smith and C. Cheng. Slack-based heuristics for constraint
satisfaction scheduling. In Proc. 11th Nat. Conf. on AI,
pages 139--144, 1993.
- F. Sourd and W. Nuijten. Multiple-machine lower bounds for shop
scheduling problems. INFORMS Journal of Computing,
- P. Torres and P. Lopez. On Not-First/Not-Last Conditions in
Disjunctive Scheduling. European Journal of Operational
- P. Torres and P. Lopez. Overview and possible extensions of
shaving techniques for job-shop problems. In 2nd International
Workshop on Integration of AI and OR techniques in Constraint
Programming for Combinatorial Optimization Problems
(CP-AI-OR'2000), pages 181--186, March 2000.
- D. Weld. An Introduction to Least Commitment Planning. AI
Magazine, 15(4):27--61, 1994.