A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling

1 Introduction

Disjunctive constraints are widely used to ensure that the time intervals over which two activities require the same resource do not overlap in time [Erschler, 1976; Carlier, 1984; Le Pape, 1988; Smith and Cheng, 1993) . If a resource is required by two activities A and B , the disjunctive constraint states that either A precedes B (i .e., ends before B starts) or .f! precede~ A .. The "pr~p­ agation" of disjunctive constramts c?ns1st.s m d~termm­ ing that only one of the two ordenngs 1s feas1ble. It resul ts in updating the time-bounds (earliest start times and latest end times) of the two activities.

The most basic disjunctive constraint can be stated as follows:

[end(A) ~ start(B)] or [end(B) ~ stal't(A)]

Claude Le Pape

ILOG S.A.

2 A venue Gallieni BP 85 94253 Gentilly Cedex FRANCE lepape@ilog.fr

In this formula, start(A), end(A), start(B) and end(B) denote constrained variables , which means that the values of start(A), end(A) , start(B) and end(B) are ini­ tially unknown.

Constraint propagation consists in reducing the set of possible values for these variables: whenever the small­ est possible value of end(A) (earliest end time of A) ex­ ceeds the greatest possible value of start( B) (latest start time of B) , A cannot precede B; hence B must precede A- the time-bounds of A and B can consequently be u~dated with respect to the new temporal constraint [end(B) ~ start(A)]. Similarly, when the. earliest p~ssi­ ble end time of B exceeds the latest possible start time of A, B cannot precede A. When neither of the two activities can precede the other, a contradiction is de­ tected. This way of propagatin~ constraints enforces arc-H-consistency [Lhomme, 1993J, i.e., arc-consistency restricted to updating the bounds of the variables rep­ resenting the start times and the end times of activities. A constraint c( v1, ... , Vn) is said to be arc-consistent if and only if for any variable v; and any value val; in the domain of v;, there exist values val1, ... , val;-1, valitl, ... , valn, in the domainsofv1, .. . , Vi-1 1 Vitl, ... , Vn, such that c(val1, ... , valn) holds. Arc-H-consistency (where B stands for bounds) guarantees only that val1 , ... , val;-1 , val;+1, ... , valn exist for val; equal to either the smallest or the greatest value in the domain of v;. [Nuijten et al. , 1993a) provides a characterization of full arc-consistency when durations of activities are fixed .

In practice, two types of extensions of the basic dis­ junctive constraint are useful:

• Extensions allowing the representation of more com­ plex constraints, including (1) activities that may or may not require the resource, (2) "state resources" to represent situations where an activity uses a re­ source only under specific conditions, and (3) setup times between activities that require the same re­ source. [Baptiste and Le Pape, 1995) describes such extensions.
• Extensions of the constraint propagation algorithm to deduce more precise time-bounds. When the amount of propagation is extended, the search space is more drastically pruned. Each decision requires more CPU time, but the number of problem-solving steps decreases . Results of experiments with flexi-

ble constraint propagation systems show that the amount of constraint propagation that enables a problem-solver to be the most efficient varies with the problem-solver, with the application, and with the problem-solving context [Van Hentenryck, 1989; Collinot and Le Pape, 1991]. The following sections present the results of an investigation of the tech­ niques that can be used to extend the propagation of disjunctive constraints.

2 Bibliographical Study

In the literature, there are roughly two types of methods that provide more precise time-bounds. The first type of method, described in Section 2.1, consists in deter­ mining whether an activity A must, can, or cannot be the first or the last to execute among a set of activities S that require the same resource [Carlier and Pinson, 1990; Nuijten et al., 1993b; Caseau and Laburthe, 1994] . The second type of method consists in comparing the amount of resource energy required over a time interval [t 1 t2) to the amount of energy that is available over the same in­ terval [Erschler et al., 1991; Beck, 1992; Le Pape, 1994] . This form of propagation is discussed in Section 2.2.

2.1 Automatic Sequencing of Activities

Rather than just looking at pairs of activities {A B}, the first type of method compares the temporal charac­ teristics of A to those of a set of activities n.

Let estA denote the earliest possible start time of A, letA denote the latest possible end time of A, and PA denote the processing time of A (the smallest possible processing time of A if the processing time of A is not fixed). Let esto denote the smallest of the earliest start times of the activities in n, leto denote the greatest of the latest end times of the activities in n, and Po denote the sum of the processing times of the activities in n. Let A-< B (A>- B) mean that A is before (after) Band A -< n (A >- r2) mean that A is before (after) all the activities in n. The following rules apply:

New time-bounds can consequently be deduced. When A is before all activities in n, the end time of A is nec­ essarily smaller than (or equal to) leto- po. When A is after all activities in n, the start time of A is necessarily greater than (or equal to) esto +PO·

The technique which consists in applying these rules is known as edge-finding [Applegate and Cook, 1991]. (Actually, Applegate and Cook use the term "edge­ finding" to denote both the above type of deduction, i.e., a "bounding" technique, and the non-deterministic choice between the possible orderings of activities, i.e., a "branching" technique. In the following, edge-finding is considered only as a deterministic deductive "bounding" technique.)

Notice that if n activities require the resource, there are potentially O(n * 2n) pairs (A r2) to consider. An algorithm that performs all time-bound adjustments in O(n 2 ) is presented in [Carlier and Pinson, 1990]:

• Compute "Jackson's preemptive schedule" for the resource under consideration. "Preemptive" means that an activity A can be interrupted to process another activity B. Jackson's preemptive schedule (JPS) is obtained by applying a very simple priority rule: whenever the resource is free and one activity is available, schedule the activity A for which letA is the smallest. If an activity B becomes available while A is in process, stop A and start B if letB is strictly smaller than letA; otherwise continue A.
• For each activity A;, compute the set W of the ac­ tivities which are not finished at t = estA; on JPS. Let pi; be the residual duration on the preemptive schedule of the activity Ak at time t = est A;. Take the activities of "IV in decreasing order of due dates and select the first activity Aj such that:

If such an Aj exists, then post the new temporal constraints:

where c~~s is the completion time of the activity Akin JPS.

[Nuijten et al. , 1993b] presents a variant of this algo­ rithm, which also runs in O(n 2 ), but is simpler in the sense that it does not require the computation of Jack­ son's preemptive schedule.

[Caseau and Laburthe, 1994] presents a constraint­ based technique based on the same principles. Two sets of rules based on the concept of "task intervals" are de­ veloped:

• edge-finding within a task interval: The edge­ finding technique is very powerful but, as we have said, it cannot be naively applied to all the subsets n of activities requiring the same resource (since for n activities, this would lead to 2n sets). To avoid this, Caseau and Laburthe associate to all couples of activities (A B) scheduled on the same machine the set of activities I<(A B) which will surely be sched­ uled between the earhest start time of A and the latest end time of B:

I<(A B) is called a task interval and is considered of interest only when A and B belong to /{(A B). Deductive edge-finding propositions are applied to task intervals: for each activity C in I<(A B) , the rules determine whether C necessarily executes be­ fore (or after) all the other activities in I<(A B) ·

• edge-finding between a task interval and an­ other task: this second set of rules is used to de­ duce that a task C cannot be performed before (or

after) a task interval J((A B) to which it does not belong.

Time-bounds can be updated accordingly. For ex­ ample, if C cannot be before K(A B), Cis at least after one of the activities D of K(A B)· Therefore, the earliest start time of C can be updated accord­ ing to the following equation:

A few remarks can be made about these rules. First, there are at most O(n 2 ) task intervals to consider for a resource on which n activities are scheduled. Therefore, a computational time in O(n 3 ) is, in the worst case, nec­ essary to apply the rules to all the task intervals and all the activities of a given resource. In comparison, the ed~e-finding algorithm of Carlier and Pinson runs in O(n ). However, the implementation of task intervals is simpler (e.g., no need to compute Jackson's preemp­ tive schedule) and can be apl?lied in an incremental way [Caseau and Laburthe, 1994], so it is difficult to deter­ mine for which values of n Carlier and Pinson's algorithm will be the most efficient.

Another remark is that when the second set of rules is applied only to task intervals, the overall propagation system (which includes those rules as well as others) can lead to different results depending on the order in which constraints are propagated. In general, a set of prop­ agation rules is said to have a "unique fixpoint" when the results of the overall propagation do not depend on the order in which the propagation steps are executed. Applying the second set of rules of Caseau and Labur­ the to task intervals only "breaks" the "unique fixpoint semantics" of constraint propagation. This means that, if other propagation rules apply, the "fixpoint" that it is reached may depend on the propagation order. This fact is illustrated below on a simple example.

The following figure displays the [estx letx) intervals of the four activities.

- - - · · · · · · · · - - - - - -

· · · · · · · · · · · · · · · · · · · ·

- - - - · · · · · · · · - - - - -

- - - - - · · · · · · · · · · · ·

A (3)

B (3)

c (1)

D (2)

Let us try now to update the time-bounds according to the previous rules.

• K(A A) ={A}. No deduction.
• J((A B) = {A, B}. Let us try to deduce something with D:

D cannot be before K(A B) = {A; B}. So estv is updated to min(estA + PA, estB + PB) = 9.

• K(A c)= {A, B, D}. No deduction.

·

Let us restart the example with estc = 7 and /etc = 14, i.e., assuming other propagation rules, related to other constraints, have allowed the deductions that C cannot start before 7 and cannot end after 14. These new val­ ues reduce the domain of the possible dates of execution of C. Therefore, the propagation should deduce at least as much new information as before. Otherwise, we would get different fixpoints by applying the different propaga­ tion rules in different orders.

• K(A A)= {A}. No deduction.
• J((A B) = {A, B, cr Let us try to deduce some­ thmg with D:

D cannot be before K(A B) = {A, B, C} .. So estv is updated to min(estA +PA, estB+PB, estc+Pc) = 8. The deduction estv = 9 is not done!

• K(A C)= {A, C}. No deduction.

·

The counterexample shows that the second set of rules, breaks "unique fixpoint semantics" when applied only to task intervals. Having different possible fixpoints is not a real problem when developing a specific algorithm, but may be annoying in the context of a generic constraint programming tool. Indeed, it means that a user of the tool can face different execution behaviors depending on the order in which constraints are posted. Such variabil­ ity makes it less easy to use the tool for the development of complex scheduling applications.

2.2 Energy-Based Reasoning

The second type of method consists in comparing the amount of resource energy required over a time interval [t 1 t 2 ) to the amount of energy that is available over the same interval.

In [Erschler et al., 1991], the authors analyze the effect of time and resource constraints on the admissibility of schedules. They study how activity characteristics and resource constraints can induce new constraints which allow to restart the propagation. Although Erschler, Lopez and Thuriot have worked on discrete resources (i.e., resources the capacity of which can be greater than one), from now on, we focus on the case of unary re­ sources (i.e., resources of capacity 1).

Let us define the concept of required energy con­ sumption W~ 1 tl) of an activity A over an interval [t1 t 2). The required energy consumption is the smallest amount of time during which A will be executed on the interval:

Of course, W~ 1 tl) is null if the previous quantity is neg­ ative. Two deduction rules apply:

• The first deduction rule is based upon the idea of picking two activities A and B and trying to find a contradiction when sequencing A before B. To achieve this, the required consumption of all the ac­ tivities over the interval [estA letB) is computed and compared to the provided amount of resource dur­ ing the same interval.

• The second deduction rule directly updates time­ bounds. Let us choose an activity A and an integer x in the interval [est A let A) . We are going to check on the interval [est A x) whether A can or cannot start at its earliest start time. If it cannot, then est A will be increased. Let us first define the quantity ~ - ~ w[utA x) . ( t ) Th .uw - L..,C#;A c + mm PA, x-es A . e deduction rule is:

In fact, Erschler, Lopez and Thuriot use a weaker bound for the earliest end time of the activity: x + Ew- (x- est A)· For a non-interruptible activ­ ity with fixed duration, this leads to the new value ~ w(e3tA x) · ( ) l" est A+ t_.,c-tA c + mm PA, x- est A - PA 10r est A. The rationale for this bound is that a mini­ mal energy of Ew- (x- est A) must be flushed out of the [estA x) interval. However, when x- estA is smaller than p A, then · p A - ( x - est A) energy is already consumed out of the [est A x) interval. Hence, it is correct to replace x + Ew - (x- est A) by X+ L:c-tA wg·tA x) + PA - (x - estA), which leads to the bound given above.

Obviously, there are many values of x for which this rule could be used. Erschler, Lopez and Thuriot suggest that the appropriate values of x are the earliest and latest start and end times of activities (which seems reasonable but is yet to be proven).

These rules are quite efficient. In a simple experiment, we combined the first of these rules with the edge-finding technique of Carlier and Pinson restricted to the overall set of yet unordered operations. With the resulting algo­ rithm, a very hard job-shop scheduling problem known as MTlO was solved to optimality (by branch-and-bound with constraint propagation performed at each node of the search tree) in about eight hours of CPU time on a HP715/50 workstation. Eight hours is significantly more than the times obtained in [Carlier and Pinson, 1990] and [Caseau and Laburthe, 1994] for the same problem;

yet the result struck us given that our algorithm was extremely simple.

While using this algorithm, we noticed that the num­ ber of backtracks required to prove the optimality of the solution varied with the order in which constraints were posted. This observation suggested that our implemen­ tation did not have a unique fixpoint. Yet we have been unable to put together a simple example with two dif­ ferent fixpoints.

Energetic reasoning is also used in the ToscA sys­ tem of Beck [Beck, 1992] and in the energetic resources of ILOG SCHEDULE (Le Pape, 1994]. Beck uses a data structure called "habograph" to compute the required energy consumption and the maximal energy available over each time interval [t1 t2) up to a given discretization of time. When the required energy consumption exceeds the maximal energy available, a failure occurs. When the required energy consumption is close to the maximal energy available, a constraint threat is indicated. The habograph can also be used to determine that an ac­ tivity cannot fully execute during a given time interval [t 1 t 2), in a way similar to applying the rules above, but with predetermined time intervals rather than intervals depending on the time-bounds of activities.

In ILOG ScHEDULE, an energetic resource represents the fact that the amount of energy that can be used over given intervals of time is limited. Roughly, an energetic resource does not represent a resource per se, but the amount of work performed by the resource over regular intervals of time. The capacity of an energetic resource is consequently not measured as a number of machines or as a number of men and women, but as a number of machining hours, or as a number of human-days, human­ weeks or human-months, spent for the performance of the activities. The following code, for example, creates an energetic resource to represent the fact that at most 50 human-days of work can be spent each week. The time unit is supposed to be the day and date 0 corre­ sponds to the beginning of the first week.

Energetic reasoning is thus performed for each time in­ terval [t1 t2) of the form [7n 7(n + 1)). In fact, an energetic resource of ILOG ScHEDULE corresponds to a "piece of habograph" used to update the time-bounds of activities. Energetic resources are occasionally used in ILOG ScHEDULE applications to implement redundant constraints (that result in more constraint propagation being performed) .

2.3 Theoretical Comparison

The previously described mechanisms have been imple­ mented in several systems and shown to give interesting results as far as computational time is concerned. One issue however to be dealt with is the management of the additional data structures used to implement these techniques. Indeed, these data structures may be more or less costly to maintain both in terms of CPU time and in terms of memory consumption.

The task intervals of [Caseau and Laburthe, 1994] re­ quire the maintenance of a data structure in 0( n 2 ) where n is the number of activities requiring a given resource.

Note that, in principle, this memory space consumption could be avoided, but at some expense in terms of CPU time. Similarly, the habograph of [Beck, 1992] uses a memory space in O((h/g) 2 ) where h is the scheduling horizon and g the grain of the habograph. An ener­ getic resource in ILOG SCHEDULE uses a memory space in 0( h/ g) only since the energetic analysis is restricted to time intervals of size g. Using implementation cues sim­ ilar to those used in the sequential time-tables of ILOG ScHEDULE [Le Pape, 1994], the habograph could be re­ duced to time intervals [estA let8 ) such that estA is the earliest start time of an activity A and letB the latest end time of another (or the same) activity B . The space complexity would then be O(n 2 ).

Erschler, Lopez and Thuriot do not say much about their implementation choices in this respect. However, the use of the energetic rules for all pairs [estA letB) obviously requires either O(n 2 ) in space, or O(n 3 ) in CPU time. The less consumin& techniques are those of [Carlier and Pinson, 1990] and [Nuijten et al., 1993b].

The following table summarizes the complexity anal­ ysis of the various propagation techniques we have dis­ cussed. The time complexity that is given corresponds to one iteration (over then activities of the same resource) of the constraint propagation process. A question mark is used when we are not sure about the actual complex­ ity of the technique. Two things that are difficult to measure a priori do not appear in the table: (1) the typ­ ical number of iterations necessary to reach the fixpoint; (2) the "pruning power" of the propagation that is being performed. In the next section, we present experiments performed to assess the effectiveness of some of these propagation techniques: arc-B-consistency, edge-finding, and energetic reasoning.

The table also includes a new algorithm developed by Carlier and Pinson, which runs in O(n * log(n)) time [Carlier and Pinson, 1994]. We have not yet found the time to study this algorithm in detail. The results of the next section are based on the O(n 2 ) algorithms of [Carlier and Pinson, 1990] and [Nuijten et al., 1993b].

3 Experimental Study

3.1 Implemented Algorithms

In addition to arc-B-consistency, three "extended" con­ straint propagation algorithms have been implemented on top of version 1.0 of ILOG SCHEDULE.

• The ERA algorithm is based on energetic reasoning.
• The EFJ algorithm performs edge-finding based on Jackson's preemptive schedule.
• The EFN algorithm performs edge-finding based on the method described in [Nuijten et al., 1993b].

ERA

In a preliminary experiment, we combined the first rule ofErschler, Lopez and Thuriot (cf. Section 2.2) with the edge-finding technique of Carlier and Pinson restricted to the overall set of yet unordered operations. Using the resulting algorithm, we noticed that the number of back­ tracks required to prove the optimality of the solution varied with the order in which constraints were posted. We consequently changed the rule as follows : rather than computing the energy required over the time interval [estA letB), we compute the energy W that would be required by other activities between the latest start time of A and the earliest end time of B if A were scheduled before B. We deduce that if A is before B, then at least W units of time must elapse between the end of A and the beginning of B . We can then use W to update, still under the hypothesis that A is before B, the latest start time of A and the earliest end time of B. As long as W increases and is not large enough to prove that A cannot be before B, we iterate.

Our implementation of energetic reasoning uses data structures in O(n) (rather than O(n 2 )). Consequently, the energetic reasoning algorithm runs in O(n 3 ), even without iterating the energy calculation. Within the same O(n 3 ) loop, the algorithm directly applies the edge­ finding technique of Carlier and Pinson to all the 3-tuples and (n-1)-tuples of activities (where n denotes the num­ ber of unscheduled activities requiring a given resource), without computing Jackson's preemptive schedule.

EFJ

The second constraint propagation algorithm is a direct implementation in ILOG ScHEDULE of the technique de­ scribed in [Carlier and Pinson, 1990]. However, our im­ plementation computes Jackson's preemptive schedule in O(n 2 ) rather than O(n * log(n)). This allows us tore­ use data structures predefined in ILOG ScHEDULE rather than implementing new ones: it would be interesting to determine the number of activities n at which the price of additional data structures would be balanced by the resulting CPU time savings.

The algorithm also applies the rules of Caseau and Laburthe to a unique task interval for each resource, i.e., the task interval consisting of all unscheduled activities. It runs in O(n 2 ) and uses data structures in O(n). It is applied iteratively as long as it results in updates of earliest and latest start and end times.

EFN

The third constraint propagation algorithm is similar but uses the algorithm of [Nuijten et al., 1993b] rather than computing Jackson's preemptive schedule. It runs in O(n 2 ) and uses data structures in O(n).

Normally, the two edge-finding algorithms result in the same deductions. However, in the case of the algorithm of [Nuijten et al., 1993b], we were incidentally able to deduce a bit more than the pure edge-finding technique. Indeed, each time the earliest start time of an activity is updated, we can note that the activity cannot be the first to execute among the yet unscheduled activities of the considered resource. This information can then be used to prune the search tree.

Such deductions are also possible in the case of the algorithm of Carlier and Pinson, but they are less nu­ merous. As we shall see in the next section, the two algorithms provide slightly different results in terms of CPU time and number of backtracks.

3.2 Results

The following table compares the three constraint prop­ agation methods on four problems taken from the con­ straint programming and operations research literature. f Results on more than eighty problems are available in Baptiste, 1994].) The first problem is a bridge construc­ tion scheduling problem that is often used as a bench­ mark problem within the constraint programming com­ munity [Van Hentenryck, 1989]. The other problems are job-shop scheduling problems with 10 jobs and 10 ma­ chines (hence with 100 activities) considered to be par­ ticularly hard to solve to optimality. The optimization algorithm consists of a branch-and-bound backtracking search, with constraint propagation being performed at each node of the search tree. Details about the prob­ lems and the optimization algorithms are available in [Baptiste, 1994].

In the table, PROB denotes the problem instance and ALGO the constraint propagation algorithm used to solve it. BT and CPU denote the total number of backtracks and CPU time needed to find an optimal so­ lution and prove its optimality. BT-PR and CPU-PR denote the number of backtracks and CPU time needed for the proof of optimality. CPU times are expressed in seconds on a HP715/50 workstation , rounded either to the closest second or to the closest tenth of a second.

For the bridge construction (BDG), the table also pro­ vides results obtained using arc-H-consistency (ARC) as a constraint propagation procedure. Such results are not provided for the job-shop problems because 10x10 job-shop problems were generally not solved with ARC after three hours of computational time. ERA results for ABZ5 are not available for the same reason . The table shows that the number of backtracks significantly de­ creases when more propagation is being performed. On the simple bridge problem, the algorithm based on arc­ H-consistency performs better than the others in terms of CPU time: the cost of additional constraint propaga­ tion is not balanced by the reduction of the search effort. On the more complex job-shop scheduling problems, the cost of additional constraint propagation is more than balanced by the reduction of the search effort.

The three algorithms were also tested on an industrial project scheduling problem submitted by a customer of ILOG, and found to be extremely difficult to solve. The problem consists of scheduling two projects that require common resources. There are forty-five activities and five resources to consider. Each activity requires up to four resources . Within each project, activities are subjected to precedence constraints. Three of the re­ sources are unary resources. The number of activities that require each unary resource is close to thirty. The two other resources are discrete resources with capacity greater than one.

There are two optimization criteria: the goal is to min­ imize the end times of two activities, one for each project. As the projects rely on common resources, these two op­ timization criteria are conflicting. As a result, the final user wants to impose upper bounds on the two criteria, and wants the system to tell whether there exists a solu­ tion satisfying these upper bounds. The following table provides the CPU times obtained for different values of the upper bounds of the two criteria. If an algorithm is incapable of solving an instance within one hour of CPU time, that is reported by "-". The results show that the algorithms which use edge-finding strongly outperform the other algorithms.

4 Conclusion

Following these experiments, an industrial version of the edge-finding algorithm of [Nuijten et al., 1993b] was im­ plemented in a new version (1.1) of ILOG ScHEDULE. We also improved our search strategy for solving job­ shop scheduling problems. The new strategy consists of:

1. generating a first solution (very quickly),
2. iteratively improving the solution by keeping part of the best solution (i.e., keeping some ordering de­ cisions, selected randomly with a probability p that decreases over time) and searching with a limit on the number of backtracks per iteration,
3. systematically exploring the search space when p falls below a given threshold.

The following table provides the average results obtained over three runs, on the ten 10x10 job-shop scheduling problem instances used by Applegate and Cook in their computational study of the job-shop scheduling problem [Applegate and Cook, 1991]. CPU times are expressed in seconds on an IBM RS6000 workstation. Over the ten in­ stances, the total number of backtracks for ILOG SCHED­ ULE is 215256, while the total number of nodes explored by Applegate and Cook's algorithm is 674128. The use of edge-finding techniques allows the user of ILOG ScHED­ ULE to enjoy the flexibility inherent to constraint pro­ gramming, with performance in the same range of effi­ ciency as specific operations research algorithms, such as the one reported in [Applegate and Cook, 1991].

Acknowledgments

The authors would like to thank Jean-Fran<;ois Puget, Younes Alaoui, Michel Leconte, Wim Nuijten, and all the members of the ILOG SoLVER development and con­ sulting team for their contributions to the design and continual improvement of ILOG SCHEDULE. Thanks also to the referees for their helpful comments.