Informedness vs. Computational Cost of Heuristics in Iterative Repair Scheduling

1 Introduction

Space Shuttle ground processing encompasses the in­ spection, repair, and refurbishment of shuttle orbiters in preparation for launch. Each orbiter's complete prepara­ tion (called a flow) at the Kennedy Space Center requires constant attention from flow managers, whose job is to make certain that all tasks are accomplished in a safe and timely manner. Flow Management frequently revises the schedule in order to accommodate unanticipated events, such as the unavailability of specialized personnel, and the need to repair newly discovered problems.

GERRY is a scheduling system that has been used operationally in the shuttle ground processing domain since early 1992. GERRY uses constraint-based itera­ tive repair [Zweben et. al., 1990] when considering modifications to schedules. Iterative repair methods such as [Zweben et. al., 1990; Minton et. a/., 1990; Biefeld and Cooper, 1991; Lin and Kernighan, 1973; Kurtzman and Aiken, 1989; Johnson et. a/., 1990; Morris, 1990] differ from constructive scheduling meth­ ods in that they begin with a complete, but possibly flawed, set of assignments and then iteratively mod­ ify or repair those assignments to improve the overall schedule. Constructive scheduling methods [Fox, 1987; Sadeh and Fox, 1989] incrementally extend valid, par­ tial schedules until a complete schedule is synthesized or until backtracking is required.

"Red Pepper Software Company

'University of Toronto/Recom Technologies

in repairing schedules that contain violated constraints.

GERRY's constraint-based iterative repair mecha­ nism begins with a complete schedule of unaccept­ able quality and iteratively modifies it until its qual­ ity is found to be satisfactory. The quality of a schedule S is measured by the cost function: cost(S) = :Z:::c;<con·traint. penaltyc, (S) * weightc,, which is a weighted sum of constraint violations. The penalty function of a constraint returns a non-negative num­ ber reflecting the degree to which the constraint is vio­ lated. The weight function of a constraint returns a non­ negative number representing the importance or utility of a constraint. ·

GERRY performs repairs in each of its iterations by selecting a violated constraint (i.e. one whose product of weight and penalty is greater than zero), identifying candidate modifications to the schedule that might lower the violated constraint's penalty, and finally selecting and performing one of these modifications. This step may be performed several times per iteration.

Repairing any violation typically involves moving a task to a different time. If so, other tasks may be forced to move as well since GERRY always preserves all temporal constraints. We use the Waltz constraint propagation algorithm over time intervals [Waltz , 1975; Davis, 1987] to carry this out (thus enforcing a form of arc-consistency [Mackworth, 1977; Freuder, 1982]). If any temporal constraint violations cannot be resolved by the Waltz algorithm, the initial move that caused the violations is rejected.

At the end of each iteration, the system re-evaluates the cost function to determine whether the new sched­ ule resulting from the repairs is better than the current solution. If the new schedule is an improvement, it be­ comes the current schedule for the next iteration; if it is also better than any previous solution, it is cached as the best solution so far . If it is not an improvement, it is either accepted anyway with some probability (described below), or it is rejected and the changes are not kept .

The system sometimes accepts a new solution that is worse than the current solution in order to escape local minima and cycles. This stocha8tic technique is referred to as simulated annealing [Kirkpatrick et. a/., 1983]. The escape function for accepting inferior solutions is: Escape(S, S', T) = e-ICo·t(S)-Co·t(S')I/T where T is a "temperature" parameter that is gradually reduced (i.e. cooled) during the search process. When a random num­ ber between 0 and 1 exceeds the value of the escape function, the system accepts the worse solution.

4 Repair Heuristics

The amount of knowledge used to make repair decisions can vary significantly. Intuitively it makes sense to em­ ploy knowledge in decision-making when it is available. However using knowledge is not free - computational overhead is incurred to evaluate and use repair knowl­ edge. This is analogous to the utility problem of ma­ chine learning [Minton, 1988] which states that learn­ ing can degrade the performance of a problem solver if the learned knowledge is not useful. Similarly, a knowledge-intensive repair method could degrade the problem solver if the method is overly expensive and does not provide enough heuristic power to compensate for its expense.

One repair-based heuristic that has achieved notable success in the scheduling domain is MIN-CONFLICTS [Minton et. a/., 1990]. A common use of this technique is to randomly select a violated constraint, consider all pos­ sible moves for the tasks involved in the violation, and perform the move that minimizes the resulting number of constraint violations. In effect, MIN-CONFLICTS per­ forms lookahead to determine which move to perform.

GERRY's repair framework also randomly selects a con­ straint to repair. However, in the selection of candi­ date repairs, we have found that considering all possible moves in a given repair is computationally infeasible. A single repair might need to consider thousands of candi­ date moves. In addition, the most promising moves are typically the shortest ones, since these moves are less likely to unnecessarily perturb the schedule.

Instead, GERRY identifies a small set of candidate schedule modifications that are deemed most likely to have a chance to repair the violation while minimizing unnecessary perturbation. The types of modifications depend upon the constraint being repaired:

• A repair to a resource constraint always moves one of the violated tasks to a new location. For each task participating in the violation, two candidate moves are identified. These moves are to the nearest times (one earlier and one later) that would satisfy the violated constraint for this task.
• A repair to a state constraint cannot always be achieved by task-moves, since the required state may not exist anywhere on the schedule. It may be possible then to insert a new achiever task whose sole purpose is to set the desired state over the time interval that the constraint specifies. This option is considered along with moving the task to the near­ est locations (one earlier and one later) where the state constraint is already properly set (or could be properly set with the insertion of a new achiever task).

Once a set of candidate modifications has been iden­ tified, GERRY can perform a wide variety of heuristics to select the actual repair to perform.

4.1 Static Repair Measurement

One simple heuristic consists of simply taking measure­ ments of the existing schedule and making an informed guess as to which of the available repairs appears most promising. Each repair receives a score based upon the measurements taken; these scores serve as a basis for selecting the repair to perform. We have found this in­ expensive heuristic, which we refer to as the static mea­ surement heuristic, to be quite effective in the domain of shuttle ground processing. The kinds of measurements performed for the scoring of available repairs, again, are a function of the constraint being repaired:

• For resource constraints, each candidate move is scored by several criteria, and each score is normal­ ized by what are considered the best and worst pos-

sible scores for that criteria. A net score is derived from a linear combination of all individual scores. GERRY uses the net scores to weigh each move be­ fore randomly selecting one. The following scoring criteria are used:

1. Assign higher scores to moves whose task's re­ quirement more closely matches the amount of resource overallocation.
2. Assign higher scores to moves whose task has fewer temporal dependents.
3. Assign higher scores to shorter moves.
4. For state constraints, prefer to insert a new task that will satisfy the proper state for the violated constraint if this can be done without actually hav­ ing to move the task with the violation. Otherwise, score each task-move (to where the state is or can be satisfied properly) according to the magnitude of the move itself.

4.2 Lookahead Repair Measurement

An alternative repair selection heuristic is to perform lookahead on each candidate modification, record there­ sulting cost, then select the modification that reduces the cost by the greatest amount. This is a version of MIN­ CONFLICTS on the restricted subset of candidate modifi­ cations the system has identified.

Clearly the lookahead heuristic has more knowledge at its disposal when choosing a repair. But is the computa­ tional expense of that enhanced knowledge too great? We knew that our static measurement heuristic per­ formed well in our application domain, and were curious how well the lookahead heuristic would perform in its place. We expected that each iteration of the lookahead method would lower the cost more than an iteration of the static method, but also expected the less-informed static repair mechanism to be able to perform more it­ erations per unit time than the lookahead method.

5 Experiments

We performed experiments in order to explore the com­ parative utility of the static and lookahead measurement heuristics. For both heuristics, the same method (de­ scribed above) is employed to select the constraint tore­ pair and the set of candidate modifications to the sched­ ule. The two methods were compared on both schedul­ ing and rescheduling problems and on both artificially generated and actual Space Shuttle data.

5.1 Problem Data Sets

Scheduling problems were constructed using a problem generator. These problems were built with varying char­ acteristics (e.g. number of tasks, task durations, tem­ poral dependencies, amount and frequency of resource requests and state requirements and effects). The prob­ lem generator initially assigns all tasks in the schedule to their earliest locations that preserve temporal con­ straints: this changes the initial scheduling problem into a rescheduling problem, where the resource and state constraints must now be repaired.

All of the rescheduling experiments used Space Shut­ tle data. One data set, corresponding to the STS-43 mission of the orbiter Atlantis, contained no state con­ straints. A rescheduling experiment was generated by taking a conflict-free schedule and moving 10 pending tasks by a random amount. After this "perturbation", the rescheduler was invoked to resolve any conflicts created by the moves. ·

The penalty of a resource capacity constraint was 1 if the resource was overallocated. When a required state variable was not set correctly, the penalty of the asso­ ciated state constraint returned 1. Weights for all con­ straints were set to 1.

All experiments were run on a Sun SPARCstation 2 with 32MB of memory. Each experiment ran until there were no outstanding violations or a 30-minute CPU time bound was reached. Since the repair functions are prob­ abilistic, we calculated average results over at least 10 repeated trials for each experiment.

5.2 Empirical Results

Table 1 presents results for the entire experimental suite. For each problem the average time to solution, percent timeouts, and average cost at timeout are reported for the static (S) and lookahead (L) repair heuristics. The "Due Date" column represents the position of the com­ pletion date for the problem as a percentage beyond the shortest possible schedule with respect to temporal con­ straints only. In other words, if Due Date = 30, and ESsoP is the earliest start for the StartO I Project task and EFsoP is the earliest finish for the EndO I Project task, then all tasks had to be scheduled in a time frame = 1.3x(EFeop-ESsop). Problems with smaller "Due Date" values were more tightly constrained and therefore more difficult to schedule. The data shows that for most of the experiments run, especially the larger problems, static value selection outperforms lookahead.

Figure 1 shows average best cost against time for the 50-task problem with increasingly smaller · "Due Date" values. These graphs show that as the problem becomes more constrained, the lookahead technique fares increas­ ingly better on average. In the highly constrained graph, we can see a "crossover" behavior, where the static repair technique quickly brings the cost to a low value, but has a hard time going much further. In contrast, the looka­ head technique requires more time to get to the same low cost, but can find better schedules more efficiently beyond that point.

This seems to indicate that the static repair measure­ ment is not as useful in resolving the more highly con­ strained violations. The heuristic is blind to secondary effects it may cause (e.g. new violations on other re­ sources), and is thus more prone to cycle between moves that it scores highly. Lookahead is not blind to sec­ ondary effects, since it will base its repair selection on each repair's resulting cost for the entire schedule.

Figure 2 shows representative behavior from our rescheduling tests on STS-43 and STS-50. In the STS43 tests, the static heuristic was superior, while in the STS-50 tests, the static heuristic's advantage is not as clear. We believe that the competitiveness of lookahead on STS-50 is because there are fewer candidate repairs to explore on average when repairing a state constraint as opposed to a resource constraint . In addition, a repair to a state constraint can be accomplished without moving any tasks, so lookahead has less work to do in measuring each candidate modification. Consequently, it is compu­ tationally less expensive to perform this limited form of lookahead.

6 Conclusions and Future Work

Our experiments suggest that the selection of an effi­ cient repair mechanism in a system such as GERRY de­ pends at least in part on two problem characteristics - problem size and constraint tightness. Static evaluation - a less informed technique - serves better on larger and less constrained problems; lookahead techniques are es­ pecially effective on more difficult and smaller problems. Clearly lookahead suffers in problems with many tasks, where the overhead of preserving temporal relations is substantial. It is apparent that the size of the shuttle ground processing problem is a more dominating feature than the tightness of its resource and state constraints.

The tabular data shows that neither heuristic is im­ mune from cycling. We see that occasionally no solution is found on problems where the average time to solution is well below the 30-minute timeout . Perhaps using a heuristic that selects a modification randomly in these cases would help escape the cycling behavior.

We observed (although the data is not presented here) that when both static and lookahead methods reached a cost of zero, the lookahead technique did so in a fewer number of iterations. Thus the lookahead mechanism more often chose the best repair candidate, even though it may have spent too much time in doing so.

From the graphs shown, we see that early in the re­ pair process it is better to perform some kind of repair quickly, instead of wasting time evaluating which repair will reduce the cost by the greatest amount . But later in the repair process as a system is attempting to resolve a final few "tough" violations, the lookahead heuristic Our work was heavily influenced by previous constraint­ based scheduling [Fox, 1987; Fox and Smith, 1984; Sadeh and Fox, 1989] and rescheduling efforts [Ow et. al., 1988].

ISIS [Fox, 1987] and GERRY both have metrics of con­ straint violation (the penalty function in GERRY) and constraint importance (the weight function in GERRY). In contrast with our repair-based method, ISIS uses an in­ cremental, beam search through a space of partial sched­ ules and reschedules by restarting the beam search from an intermediate state.

OPIS [Fox and Smith, 1984; Ow et. a/., 1988], which is the successor of ISIS, opportunistically selects a rescheduling method. It chooses between the ISIS beam search, a resource-based dispatch method, or a repair­ based approach. The dispatch method concentrates on a bottleneck resource and assigns tasks to it according to its dispatch rule. The repair method shifts tasks until they are conflict-free. These "greedy" assignments could yield globally poor schedules if used incorrectly. Conse­ quently, OPIS only uses the dispatch rule when there is strong evidence of a bottleneck and only uses the re­ pair method if the duration of the conflict is short. In contrast, GERRY uses the simulated annealing search to perform multiple iterations of repairs, possibly retracting "greedy" repairs when they yield prohibitive costs.

Our use of simulated annealing was influenced by the experiments performed in [Johnson et. a/., 1990a; Johnson et. a/., 1990b]. In contrast with our constraint­ based repair, their repairs were generally uninformed.

The repair-based scheduling methods considered here are related to the repair-based methods that have been previously used in AI planning systems such as the "fixes" used in HACKER [Sussman, 1973] and, more re­ cently, the repair strategies used in the GORDIUs[Sim­ mons, 1988] generate-test-debug system, in the PRIAR plan modification system [Kambhampati, 1990], and the CHEF cased-based planner [Hammond, 1986].

Miller et a!. [Miller et. a/., 1988], Currie and Tate [Currie and Tate, 1991], and Drummond and Bresina [Drummond and Bresina, 1990] describe other efforts that deal with resource and deadline constraints.

8 Acknowledgments

We wish to thank Mark Drummond, Peter Friedland, Steve Minton, Holly Pease and the anonymous reviewers for their comments.