This tutorial is sponsored by PLANET, the European
Network of Excellence in AI Planning. 

Lecturers:

Philippe Laborie , ILOG S.A., France
Wim Nuijten , ILOG S.A., France
Objectives:

The objective of the tutorial is to give an overview of both the
most widely used techniques as well as new emerging techniques in
ConstraintBased 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
integrated.
Abstract:

Constraint Programming is a problemsolving 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 ConstraintBased Scheduling as a field of study.
This tutorial provides an overview of the most widely used or
emerging ConstraintBased Scheduling techniques. It particularly
emphasizes the features of ConstraintBased 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 ConstraintBased 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 ConstraintBased Scheduling approach.
Prerequisite knowledge:

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
postdoctoral 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.
Email: plaborie@ilog.fr
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 19921994 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
constraintbased 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
programming products.
Email: wnuijten@ilog.fr
Outline:

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) [19]
 Constraint propagation [23,4]
 Search techniques (heuristics, search tree exploration: DFS, LDS [14], ...)
 Optimizing objective functions
 Scheduling Model [2,15]
 Typology of activities: nonpreemptive, preemptive
 Temporal constraints
 Typology of resources, Alternative resources
 Extensions: setup times/costs, resource efficiency, state resources
 Objective functions
 Examples of Scheduling Problems
 Jobshop problem [16]
 Resource constrained project scheduling problem with inventories and min/max time lags [24]
 Scheduling and AI Planning
 Relations with Partial Order Planning [28,25]
 Local properties and Truth criterions [8,33]
 Propagation of Resource Constraints
 Global constraints
 From local properties to global constraints
 Close/notclose status of a resource [18,13]
 A framework to classify resource propagation algorithms
 Algorithms based on activity time windows [26,9]
 Timetabling constraint [22]
 Disjunctive constraint [17]
 EdgeFinding constraint [5]
 Notfirst/notlast [31]
 Energetic reasonning [10,11]
 Algorithms based on relative position of activities
 Precedence energy constraint [30]
 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 nondeterministic local properties
 Classical branching schemes: resource allocation, setting times, ranking first/not first, activity or timepoint pair ordering [21,6]
 Search heuristics
 Slackbased heuristics [29]
 Texturebased heuristics [3]
 Beyong the basic search scheme
 Shaving [32], Probing, Dichotomizing, large neiborhood search [12], etc.
 Putting things together on two examples
 Jobshop problem [27]
 Resource constrained project scheduling problem with inventories and min/max time lags [24]
 Conclusion
Bibliography:


1

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.

2

P. Baptiste, C. LePape, and W. Nuijten. ConstraintBased
Scheduling. Kluwer Academics Publishers, 2001.

3
 C. Beck, A. Davenport, E. Sitarski, and M. Fox. Texturebased
Heuristics for Scheduling Revisited. In Proceedings AAAI97,
1997.

4
 C. Bessière and J.C. Régin. Refining the basic constraint
propagation algorithm. In Proceedings IJCAI'01, 2001.

5
 J. Carlier and E. Pinson. A Practical Use of Jackson's
Preemptive Schedule for Solving the JobShop Problem. Annal of
Operation Research, 26:269287, 1990.

6
 A. Cesta, A. Oddi, and S. Smith. A constraintbased method for
project scheduling with time windows. Technical report, CMU RI
Technical Report, 2000.

7
 A. Cesta and C. Stella. A time and resource problem for planning
architectures. In ECP97, 1997.

8
 D. Chapman. Planning for conjunctive goals. Artificial
Intelligence, 32:333377, 1987.

9
 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 213238, 1999.

10
 J. Erschler. Analyse sous contraintes et aide à la
décision pour certains problèmes d'ordonnancement. PhD
thesis, Université Paul Sabatier, 1976.

11
 J. Erschler, P. Lopez, and C. Thuriot. Raisonnement temporel
sous contraintes de ressources et problèmes d'ordonnancement.
Revue d'Intelligence Artificielle, 5(3):732, 1991.

12
 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 92101, 2000.

13
 F. Garcia and P. Laborie. New Directions in AI Planning,
chapter Hierarchisation of the Search Space in Temporal Planning,
pages 217232. IOS Press, Amsterdam, 1996.

14
 W. Harvey and M. Ginsberg. Limited discrepancy search. In In
Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, August 1995.

15
 ILOG. ILOG Scheduler 5.2
Reference Manual, 2001.

16
 A. Jain and S. Meeran. A stateoftheart review of jobshop
scheduling techniques. Technical report, Department of Applied
Physics, Electronic and Mechanical Engineering, University of Dundee,
Dundee, 1998.

17
 S. Khambhampati and X. Yang. On the role of disjunctive
representations and constraint propagation in refinement planning. In
KR96, 1996.

18
 C. Knoblock. Automatically generating abstractions for planning.
Artificial Intelligence, 68:243302, 1994.

19
 V. Kumar. Algorithms for Cconstraint Satisfaction Problems: a
survey. AI magazine, 13(1):3244, 1992.

20
 P. Laborie. Algorithms for Propagating Resource Constraints in
AI Planning and Scheduling: Existing Approaches and New Results. In
Proceedings ECP'01, 2001.

21
 P. Laborie and M. Ghallab.
Planning with sharable resource constraints.
In Fourteenth IJCAI, pages 16431649, 1995.

22
 C. Le Pape. Implementation of Resource Constraints in ILOG
Schedule: A Library for the Development of ConstraintBased Scheduling
systems. Intelligent Systems Engineering, 3(2):5566,
1994.

23
 R. Mohr and T. Henderson. Arc and path consistency
revised. Artificial Intelligence, 28:225233, 1986.

24
 K. Neumann and C. Schwindt. Project scheduling with inventory
constraints. Technical Report WIOR572, Institut für
Wirtschaftstheorie und Operations Research. Universität
Karlsruhe, 1999.

25
 X. Nguyen and S. Kambhampati. Reviving Partial Order lanning. In
Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, pages 459464, 2001.

26
 W. Nuijten. Time and Resource Constrained Scheduling: A
Constraint Satisfaction Approach. PhD thesis, Eindhoven University
of Technology, 1994.

27
 D. Pacciarelli and A. Mascis. Jobshop scheduling of perishable
items. In INFORMS'99, 1999.

28
 D.E. Smith, J. Frank, and A.K. Jonsson. Bridging the gap between
planning and scheduling. Knowledge Engineering Review, 15(1),
2000.

29
 S. F. Smith and C. Cheng. Slackbased heuristics for constraint
satisfaction scheduling. In Proc. 11th Nat. Conf. on AI,
pages 139144, 1993.

30
 F. Sourd and W. Nuijten. Multiplemachine lower bounds for shop
scheduling problems. INFORMS Journal of Computing,
4(12):341352, 2000.

31
 P. Torres and P. Lopez. On NotFirst/NotLast Conditions in
Disjunctive Scheduling. European Journal of Operational
Research, 1999.

32
 P. Torres and P. Lopez. Overview and possible extensions of
shaving techniques for jobshop problems. In 2nd International
Workshop on Integration of AI and OR techniques in Constraint
Programming for Combinatorial Optimization Problems
(CPAIOR'2000), pages 181186, March 2000.

33
 D. Weld. An Introduction to Least Commitment Planning. AI
Magazine, 15(4):2761, 1994.