It has been argued that the use of constraint-based techniques and tools enables the implementation of precise, flexible, efficient and extensible scheduling systems: precise and flexible as the system can take into account any constraint expressible in the constraint language; efficient inasmuch as highly optimized constraint propagation procedures are now available; extensible as the consideration of a new type of constraint may require (especially in an object-oriented framework) only an extension to the constraint system or, in the worst case, the implementation of additional decision-making modules (without needs for modification of the existing code). The following paper presents ILOG SCHEDULE, a C++ library enabling the representation of a wide collection of scheduling constraints in terms of "resources" and "activities." ILOG SCHEDULE is based on SOLVER, the generic software tool for object-oriented constraint programming developed and marketed by ILOG. SOLVER variables and constraints can be accessed from SCHEDULE activities and resources. As a result, the user of SCHEDULE can make use of SOLVER to represent specific constraints, and implement and combine the specific problem-solving strategies that are the most appropriate for the scheduling application under consideration. It is hoped -and expected -that object-oriented constraint programming tools like SCHEDULE will enable the industry to make decisive steps toward the implementation of "state of the art," highly flexible, constraint-based scheduling applications. 1 In: Intelligent Systems Engineering, 1994, 3, (2), pp. 55-66. -2 - Scheduling is the process of assigning activities to resources in time. It is a decision-making process -the process of determining a schedule. A variety of constraints affect this process: activity durations, release dates and due dates, precedence constraints, transfer and set-up times, resource availability constraints (shifts, down-time), and resource sharing. These constraints define the space of admissible solutions. In addition, relaxable preference constraints characterize the quality of scheduling decisions. These preferences are related to due dates, productivity, frequency of tool changes, inventory levels, overtime, etc. Since preference constraints may conflict with one another, the resolution of a scheduling problem also consists in deciding which preferences should be satisfied and to what extent others should be relaxed. In practice, however, preference constraints are often either combined into a unique evaluation (or cost) function to maximize (or minimize), or compiled into evaluation heuristics to favour candidate solutions which satisfy (or are likely to satisfy) the preferences. In both cases, the scheduling problem is eventually defined as a set of constraints to satisfy [1] . A solution to the scheduling problem is a set of compatible scheduling decisions (such as "perform activity A 2 as soon as possible after activity A 1 on machine M") which guarantee the satisfaction of the constraints. Scheduling problems are very different one from the other: • First, three broad families of scheduling problems can be distinguished depending on the degrees of freedom in positioning resource supply and resource demand intervals in time. In pure scheduling problems (e.g., job-shop machine scheduling), the capacity of each resource is defined over a number of time intervals and the problem consists of positioning resource-demanding activities over time, without ever exceeding the available capacity. In pure resource allocation problems (e.g., allocation of personnel to planes or trains), the demand for each resource is known beforehand and the problem consists of allocating resources in time to guarantee that the supply always equals or exceeds the demand. In joint scheduling and resource allocation problems, degrees of freedom exist for deciding both which activities to perform and when, and which resources to make available for these activities. -3 - • Different environments are subjected to different constraints which more or less contribute to the complexity of the problem. For example, a factory scheduling problem may involve only machines as resources, while another may (in addition) require the consideration of the abilities of human operators. The size of a scheduling problem may vary from a few dozens activities to thousands of activities. For complexity reasons, the scheduling algorithms that work well for the small problems may not be applicable to the bigger problems. • Important numerical features of scheduling problems vary from one environment to the other. In the same environment, they also vary from a problem-solving situation to the other. For example, the variation of the duration of manufacturing operations depends on the manufactured products, and the importance of bottleneck resources varies with the global load of the shop. Again, the scheduling algorithms that work well for some problems may not be applicable to other problems. • Depending on the environment, the suitable response time for the construction of a schedule may vary from a few microseconds to a few days. Also, it may be necessary to incrementally modify the schedule, either as a response to environmental changes, or because it is more appropriate for a human to "make the decisions." The existence of such disparities implies that rigid scheduling procedures, designed to provide optimal or near-optimal schedules in particular circumstances, are in general not satisfactorily applicable in other circumstances, either because some constraints (e.g., abilities of human operators) cannot be taken into account, or because satisfactory schedules cannot be generated in an acceptable amount of time. There are two conceivable responses to the important variety and variability of scheduling problems. The first is to develop highly flexible systems, enabling the scheduler to combine various types of schedule formation and revision algorithms and dynamically adapt the overall scheduling strategy to the problem-solving situation at hand. Examples of flexible constraint-based scheduling systems include ISIS [2] [3] , OPIS [4] [5] , FLYPAST [6] , SONIA [1, [7] [8] [9] , DAS [10] [11] [12] , and more recently the REDS 2 -4 -system of Hadavi et al [13] . Interesting comments about the most well-known systems and the evolution of work in this domain appear in the reviews of Anne Collinot [7] , Peter Burke [10] , Pauline Berry [12] , Howard Beck [14] , Khalil Hindi [15] , Patrick Prosser [16] , and Claude Le Pape [17] . The present paper argues that the emergence of object-oriented constraint programming tools brings about important opportunities for the industrial implementation of flexible constraint-based scheduling systems. This assertion is backed up with the development of SCHEDULE, a library enabling the representation of a wide collection of scheduling constraints, and with the results of preliminary experiments (not reproduced here but in previous papers [18] [19] [20] ) involving the low-level primitives of the library. A second, complementary, response is to enable the rapid development and adaptation of efficient scheduling applications, targeted to particular problems. In this perspective, a library of scheduling constraints is undoubtedly useful. However, the user of such a library must be able to (a) extend the library to enable the representation of domain-specific constraints and (b) implement and combine the specific problem-solving strategies that are the most appropriate for the considered problems. SCHEDULE is based on SOLVER, the generic software tool for object-oriented constraint programming developed and marketed by ILOG. SOLVER variables and constraints can be accessed from SCHEDULE activities and resources. As a result, the user of SCHEDULE benefits from all the flexibility and extensibility of SOLVER to develop new types of constraints and implement new problem-solving strategies. Section 2 presents the main concepts of constraint programming and discusses the use of these concepts for the development of flexible scheduling systems. Section 3 describes resource time-tables as implemented in the SCHEDULE library to enable the representation of many sorts of resource constraints, i.e., constraints concerning the use of resources over time. Section 4 provides an overview of SCHEDULE (version 1.0) and Section 5 presents an example. Finally, Section 6 discusses the possibility of extending the SCHEDULE library. -5 - The main interest of constraint programming lies in actively using the constraints to reduce the computational effort needed to solve a problem. Constraints are used not only to test the validity of a solution, as in conventional programming languages, but also in a constructive mode to deduce new constraints and detect inconsistencies.  In the first type of model, generally limited to discrete problems, a constraint satisfaction problem is described as a graph. The nodes of the graph represent the problem variables, to which finite domains are associated, and the edges represent the constraints [21] . • The second type of model stems from logic programming, where constraint solving can be viewed as an extension of unification [22] [23] [24] [25] [26] [27] [28] [29] [30] . • Finally, a third type of model consists in distinguishing the concept of a generic constraint (a relation represented, for example, by a class in an object-oriented language) and the concept of an instance of the constraint applied to specific variables of the problem to solve [31] [32] [33] [34] [35] . The main advantage of this type of model is that it allows the user to define very precisely the constraints of the problem on the one hand, and to implement the most appropriate problem-solving strategy on the other hand. In addition, it permits the close integration of constraint-based methods with an object-oriented programming environment [34] . The availability of constraint propagation methods within an object-oriented environment brings numerous advantages for the development of complex scheduling applications. First, it is easy to define multiple classes of resources and attach appropriate constraint propagation methods to each class. For example, the capacity of a resource may be bounded either in terms of power or in terms of energy (or both). In the first case, the power available at any time (e.g., number of machines, number of men and women, electrical power measured in watts) is limited. In the second case, a limited amount of energy (e.g., in person-days, in watt hours) can be spent over a given time interval. Let us suppose, for example, that a resource consists of a group of 10 persons, each of which accepts to work every day (including the week-end) but globally not more than 5 days each week. Then the power available each day is 10 persons, and the energy available each week is 50 person-days. The use of multiple classes of resources allows the scheduling system to take both constraints into account and allow the same syntax for stating that an activity requires a resource, regardless of whether the resource capacity is defined in terms of power or in terms of energy. -7 -Similarly, it is easy to define as many resource utilization patterns as needed for the activities to schedule. The simplest case is when an activity requires a fixed quantity q of a resource throughout its execution. But many variants are conceivable. For example, an activity may definitely consume a resource. And another may require 2 units of a resource (e.g., 2 human operators) when it starts, no resource during most of its execution and 2 units of the resource when it ends. The use of an object-oriented constraint-based programming tool enables the organization of a variety of resource utilization constraints as subclasses of a root "resource constraint" class. With other approaches, either code would have to be duplicated or tests would have to be made at run-time to distinguish among the different types of resource requirements. The use of an object-oriented constraint-based programming tool also simplifies the implementation of multiple versions of a constraint. "Multiple versions" means that the semantic meaning of the constraint does not change from a version to the other, but each "version" may differ from an operational point of view. For example, one version of the constraint may support non-monotonic reasoning while another may not. The second version will propagate more efficiently and imply much less bookkeeping, but will allow only chronological backtracking in reaction to detected inconsistencies. Another version of the constraint may also propagate more than the others: the resolution of a "really hard" problem [36] may require a large amount of constraint propagation (including propagation of redundant constraints [37] [38] ) while the resolution of an easier problem may be more rapid if the scheduling system can make stronger decisions without propagating too much after each decision [8] . To statically impose a constraint propagation scenario, one just has to use the corresponding version of the constraint. To dynamically impose and update the scenario, one just has to create the versions of interest (instances of different constraint classes) and inhibit or activate the appropriate versions at the appropriate instants in the problem-solving process. More generally speaking, an object-oriented constraint-based formalism endows a scheduling system with much flexibility along three dimensions: constraint representation, problem-solving control, and integration with other systems [39] [40] . In the context of an object-oriented constraint programming tool, this leads to the design of different classes of constraints that correspond to different tradeoffs between precision, efficiency, flexibility and extensibility of the final scheduling application. Given a -8 -scheduling application, the selection (and possibly the implementation) of the most appropriate constraint classes is then under the responsability of the scheduling system designer, each possible selection resulting in different tradeoffs between precision, flexibility, efficiency and extensibility. The following section focuses on the representation of resource constraints. It discusses the representations used in OPIS [4] [5] and SONIA [1, [7] [8] [9] , and presents the generic mechanism proposed in the SCHEDULE library. Two main categories of constraints occur in most scheduling problems: temporal constraints and resource constraints. • A temporal constraint is logically expressed by a formula (I 1 + d ≤ I 2 ). I 1 and I 2 are time points, i.e., variables representing start times or end times of activities, and d a minimal delay that must elapse between the two time points. In practice, the propagation of such a constraint results in a constant update of (a) the minimal value of I 2 , and (b) the maximal value of I 1 , i.e., in the update of earliest and latest start and end times of activities. • A resource constraint specifies that the execution of a given activity requires (or provides) a given amount (either a constant or a variable) of capacity from a given resource. Constraint propagation occurs in both directions: from resources to activities, in order to update the earliest and latest start and end times of activities; and from activities to resources in order to update the minimal and maximal capacities that can be used at any point in time. The representation of scheduling and resource allocation problems often requires the representation of time-tables to precisely define the availability of different types of resources over time. In this respect, the modeling requirements to consider when designing a scheduling system for a given environment vary tremendously from an environment to the other. -9 - The following cases represent three increasingly complex types of resource usage constraints that one might wish to enforce: • Case A. The availability of each resource type varies over time (e.g., according to shifts in a factory) independently of the availability of the other resource types. For example, there may be six persons working in a manufacturing cell over a given weekday shift, and only three persons working over the corresponding weekend shift. • Case B. Resource types are aggregated into more and more abstract types, typically to allow the representation of resource interchangeability. For example, there may be six persons working in a manufacturing cell during a given shift, two able to operate lathes and five able to operate milling machines. There are in this case three constraints to consider over the given shift: never more than two lathe operations in parallel; never more than five milling operations in parallel; and never more than six "lathe or milling" operations in parallel. • Case C. The availability of a resource type at some points in time depends on the availability of other resource types at other points in time. For example, it may be the case that a polyvalent operator (able to operate both lathes and milling machines) must, over each shift, remain assigned to the same type of machine, either a lathe or a milling machine. In such a case, an additional constraint applies: if at some point during the shift the operator must be assigned to a lathe, then over the shift (s)he cannot be assigned to a milling machine, and conversely. Consideration of these examples lead us to generalize the time-table modeling schemes previously adopted in a number of flexible scheduling systems such as OPIS [4] [5] and SONIA [1, [7] [8] [9] . The solution adopted in SCHEDULE consists of a very generic framework allowing the definition of "tables of variables" as part of the SOLVER object-oriented constraint programming library (previously known as PECOS [33] [34] ). Semantically, a table of variables represents a variable the value of which is a function of some parameter, typically time. Hence, the availability of a resource is viewed as a variable the value of which must eventually be a function associating a quantity v(t) to each point in time t. As we shall see in Section 3.3, this allows representation of cases A, B and C above. -10 -Section 3.1 discusses the constraint-based representations of time-tables used in OPIS and SONIA, Section 3.2 presents the generic mechanism used in SCHEDULE, and Section 3.3 provides information about its current implementations (in LE-LISP and in C++). A number of constraint-based representations of resource time-tables have been described in the literature. These representations achieve basically the same goal: constraint propagation through the time-table of a resource allows the scheduling system to maintain accurate time bounds (earliest and latest possible start and end times) for the activities that require the use of the resource, and consequently for the related activities. The first significant constraint-based framework for the representation of resource time-tables was developed as part of the ISIS scheduling system [2] [3] . This framework enables the specification of shifts and reservations of resources for scheduled activities at various levels of aggregation, i.e. for both individual machines and homogeneous work areas consisting of equivalent or similar machines. Stephen Smith [41] describes the first design of this framework for which a "one unscheduled order at a time" implementation was developed. "One unscheduled order at a time" means that constraint propagation is performed for a unique order to schedule, i.e., that the constraint propagation system cannot simultaneously handle two unscheduled orders. A new object-oriented design, allowing any number of unscheduled orders, was then put together by the OPIS team and implemented by Kevin Neel and Claude Le Pape as part of the OPIS system [42] . The approach used in OPIS may be summarized as follows: •
Constraint logic programming allowed implementation of a variety of constraints available in ILOG Scheduler REF .
Implementation of Resource Constraints in ILOG SCHEDULE: A Library for the Development of Constraint-Based Scheduling Systems
Intelligent Systems Engineering
Computer Science