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 integrated.

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.

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.

E-mail: 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 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 programming products.

E-mail: wnuijten@ilog.fr

Here is a preliminary overview of the tutorial. Note that this is subject to minor changes.

1. 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: non-preemptive, 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]

2. Propagation of Resource Constraints
   • Global constraints
     • From local properties to global constraints
     • Close/not-close 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]
     • Edge-Finding constraint [5]
     • Not-first/not-last [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

3. 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 [21,6]
   • Search heuristics
     • Slack-based heuristics [29]
     • Texture-based heuristics [3]
   • Beyong the basic search scheme
     • Shaving [32], Probing, Dichotomizing, large neiborhood search [12], etc.

4. Putting things together on two examples
   • Jobshop problem [27]
   • Resource constrained project scheduling problem with inventories and min/max time lags [24]

5. Conclusion

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. Constraint-Based Scheduling. Kluwer Academics Publishers, 2001.

3

C. Beck, A. Davenport, E. Sitarski, and M. Fox. Texture-based Heuristics for Scheduling Revisited. In Proceedings AAAI-97, 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 Job-Shop Problem. Annal of Operation Research, 26:269--287, 1990.

6

A. Cesta, A. Oddi, and S. Smith. A constraint-based 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 ECP-97, 1997.

8

D. Chapman. Planning for conjunctive goals. Artificial Intelligence, 32:333--377, 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 213--238, 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):7--32, 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 92--101, 2000.

13

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.

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 state-of-the-art review of job-shop 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:243--302, 1994.

19

V. Kumar. Algorithms for Cconstraint Satisfaction Problems: a survey. AI magazine, 13(1):32--44, 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 1643--1649, 1995.

22

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, 1994.

23

R. Mohr and T. Henderson. Arc and path consistency revised. Artificial Intelligence, 28:225--233, 1986.

24

K. Neumann and C. Schwindt. Project scheduling with inventory constraints. Technical Report WIOR-572, 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 459--464, 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. Job-shop 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. Slack-based heuristics for constraint satisfaction scheduling. In Proc. 11th Nat. Conf. on AI, pages 139--144, 1993.

30

F. Sourd and W. Nuijten. Multiple-machine lower bounds for shop scheduling problems. INFORMS Journal of Computing, 4(12):341--352, 2000.

31

P. Torres and P. Lopez. On Not-First/Not-Last Conditions in Disjunctive Scheduling. European Journal of Operational Research, 1999.

32

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.

33

D. Weld. An Introduction to Least Commitment Planning. AI Magazine, 15(4):27--61, 1994.