Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems

1 Introduction

Many scheduling domains present problems that are oversub­ scribed; problems where there are more tasks to be performed over a given time frame than can be feasibly accommodated by available resources. In such problems, it is inevitably nec­ essary to exclude some tasks from the schedule. Hence, a basic objective is to maximize resource utilization (or some­ what equivalently to accommodate as many tasks as possi­ ble). However, in many cases, the situation is further com­ plicated. Input tasks are often differentiated by priorty, im­ plying that some tasks are more important than others and if necessary should be included at the expense of others. In the particular domain that motivates this work, for example, task priorities must be rigidly respected. Though it is theoretically possible to trade one higher priority task for a set of! ower pri­ ority tasks in some circumstances, this is the exception rather than the rule. Thus, the objective is to accommodate as many tasks as possible within this constraint.

Oversubscribed problems present an interesting challenge for constraint-directed search procedures. Oversubscribed problems are not particularly well suited to formulation within a standard backtracking search framework. Hence the application of constructive approaches depends heavily on the ability of search control heuristics to anticipate resource inter­ actions. Repair-based approaches, on the other hand, tend to operate myopically through infeasible intermediate states in hopes of arriving at a better final feasible state. Their effec­ tiveness in the presence of global constraints (such as enforce­ ment of priority) will similarly rely on the ability of search heuristics to effectively focus the repair process.

In this paper, we take a repair-based search perspective of the problem and focus on locally improving an initial solu­ tion. We assume that the initial solution generator is priority­ driven, and define a controlled, task swapping search proce­ dure for finding and exploiting opportunities to rearrange cur­ rently scheduled tasks and incorporate additional tasks that were excluded from the initial solution. To direct the re­ pair process we introduce a novel retraction heuristic, max­ flexibility, for choosing which tasks to (temporarily) retract to make room for additional, lower priority tasks. Max­ flexibility chooses based on a simple measure of the relative temporal flexibility that alternative competing tasks have for feasible re-assignment elsewhere in the schedule.

We evaluate the efficacy of this approach using data and the basic scheduling procedure obtained from a real­ world, multi-mission scheduling problem: the day-to-day airlift scheduling problem faced by the USAF Air Mobil­ ity Command (AM C). We compare the performance of max­ flexibility to a variant of the min-conflicts heuristic [Minton et al., 1992] (adapted to serve as a retraction heuristic) and another more-informed contention-based heuristic.

2 Basic Allocation Procedure

Without loss of generality the AMC scheduling problem can be characterized abstractly as follows:

• A set T of tasks (or missions) are submitted for exe­ cution. Each task i E T has an earliest pickup time

est;, a latest delivery time !fit, a pickup location orig;, a dropoff location dest;, a duration d; (determined by orig; and dest;) and a priority pr;

• A set Res of resources (or air wings) are available for assignment to missions. Each resource r E Res has capacity capr 2: 1 (corresponding to the number of con­ tracted aircraft for that wing).
• Each task i has an associated set Res; of feasible re­ sources (or air wings), any of which can be assigned to carry out i. Any given task i requires 1 unit of capacity (i.e., one aircraft) of the resource r that is assigned to perform it.
• Each resource r has a designated location homer. For a given task i, each resource ,. E Res; requires a posi­ tioning time posr,i to travel from homer to orig;, and a de-positioning time deposr ,i to travel from dest; back to homer.

A schedule is a feasible assignment of missions to wings. To be feasible, each task i must be scheduled to execute within its [est;, lft;] interval, and for each resource r and time yoint t, assig.ned-capr,t ::; capr. Typically, the prob­ lem IS over-subscnbed and only a subset of tasks in T can be feasibly accommodated. If all tasks cannot be scheduled preference is given to higher priority tasks. Tasks that canno~ be placed in the schedule are designated as unassignable. For each unassignable task i, pr; ::; prj, 1::/j E Scheduled(T) : l'j .E Res; 1\ [stj ,eij] n [est;,lft;] t 0, where 'rj is the ass1gned resource and [stj, etj] is the scheduled interval.

Both the scale and continuous, dynamic nature of the AMC scheduling problem effectively preclude the use of system­ atic solution procedures that can guarantee any sort of maxi­ m~! ~ccommodation of the tasks in T. The approach adopted w1thm the AMC Allocator application instead focuses on quickly obtaining a good baseline solution, and then pro­ viding a number of tools for the end user to selectively re­ lax problem constraints to incorporate as many additional (initially unassignable) tasks as possible[Becker and Smith, 2000; Kramer and Smith, 2002].

The basic allocation procedure used within the AMC Al­ locator constructs a schedule incrementally; the set of unas­ signed input missions is first prioritized, and then missions are successively inserted into the current partial scheduling in priority order. The prioritization scheme utilized in the initial step considers the assigned priority pr( i) of each mission i as its dominant ordering criterion. In case of missions of equal priority, secondary criteria give preference to missions with earlier possible start times and smaller overall slack. A given mission i is inserted into the schedule via a search of alter­ native options. More specifically, for each r E R;, a set of candidate execution intervals is generated and evaluated, and the highest ranked alternative is selected as the assignment. In the search procedure's basic configuration, only feasible intervals are generated and the evaluation function empha­ sizes choices that minimize posr ; , deposr ; and execute i as early as possible. If a mission ca~not be f~asibly assigned, it is marked as unassignable.

This scheduling process allows for assignment of individ­ ual missions on the order of milliseconds, with a two to three week window of approximately a thousand missions assignable in a few seconds.

Since it is generally expected that several or more missions will be unable to be assigned during the first pass allocation process, the user can direct the system to automatically ex­ plore the space of constraint relaxation options on a given mission, or can do this on a more interactive basis. Available relaxation options include delaying a mission beyond its due date, over-allocating beyond contracted capacity on a wing, bumping a lower priority mission, or some combination of these basic options. Specifically tailored evaluation functions are used when searching in the space of relaxed constraints. For instance, when searching for delay options, the dominant optimization criterion is minimizing tardiness. 1

3 Improving on the Initial Solution

The quality of any schedule produced by the above greedy procedure will be a function in large part of its prioritiza­ tion heuristic. This heuristic dictates the assignment possi­ bilities that will be available to a given task i at the time it is inserted into the schedule, and consequently which tasks will ulitmately end up as unassignable. As just indicated, this heuristic gives over-riding preference to higher priority tasks. This bias in fact reflects the basic scheduling policy in the AMC application domain.

At the same time, strict relance on this ordering heuristic can obviously lead to sub-optimal solutions. It is quite pos­ sible that some "rearrangement" of the assignments of higher priority tasks could enable the feasible insertion of additional lower priority tasks. Since, in practice, the end user rna; spend non-trivial amounts of time analyzing and negotiating constraint relaxation options to enable incorporation of addi­ tional unassignable missions, it makes sense to consider tech­ niques for productively broadening the search performed by this basic procedure.

Two broad classes of approaches have been pursued in the literature. One set of approaches (e.g., [Joslin and Clements, 1998; Bresina, 1996; Cicirello and Smith, 2002 ]) focuses on exploring a "neighborhood" around the trajectory of the base heuristic. In our context, this would correspond to repeat­ edly perturbing the task order in some manner and reapply­ ing the basic search procedure. Another set of approaches have been termed iterative repair (e.g., [Minton eta!., 1992; Zweben eta!., 1994; Rabideau eta!., 1999]), wherein anini­ tial base solution is progressively revised (and hopefully im­ proved) over time. In our context, this would correspond to repeated retraction and (re)assertion of subsets of task as­ signments. Both sets of approaches have natural anytime properties. One interesting requirement in the current con­ text, however, is that we would like to guarantee that higher priority missions won't be supplanted by lower priority mis­ sions. In the case of iterative re-solving approaches, enforce­ ment of this constraint would seem possible only in a rather

I

1 A separate search procedure designed to identify and exploit opportunities for reclaiming resource capacity by combining (or "merging") two or more roundtrip missions into one is also pro­ vided, but this capability is orthogonal to the techniques discussed in the current paper.

indirect way (through global filtering of the solutions gener­ ated). Iterative repair approaches typically involve generation of infeasible solutions and are thus potentially well-suited to controlled exploration of solution improvement opportu­ nities. However, they are generally not designed to enforce global solution constraints.

Accordingly, the approach we propose takes the solution improvement perspective of iterative repair methods as a starting point, but manages solution change in a more sys­ tematic, globally constrained manner. Starting with an initial baseline solution and a set U of unassignable tasks, the basic idea is to spend some amount of iterative repair search around the "footprint" of each unassignable task's feasible execution window in the schedule. Within the repair search for a given u E U, criteria other than task priority are used to determine which task(s) to retract next, and higher priority tasks can be displaced by a lower priority task. If the repair search car­ ried out for a given task u can find a feasible rearrangement of currently scheduled tasks that allows u to be incorporated, then this solution is accepted, and we move on to the next unconsidered task u' E U. If, alternatively, the repair search for a given task u is not able to feasibly reassign all tasks dis­ placed by the insertion of u into the schedule, then the state of the schedule prior to consideration of u is restored, and u re­ mains unassignable. Conceptually, the approach can be seen as successively relaxing and reasserting the global constraint that higher priority missions must take precedence over lower priority missions, temporarily creating "infeasible" solutions in hopes of arriving at a better feasible solution.

In the subsections below, we describe this task swapping procedure, and the heuristics that drive it, in more detail.

3.1 Task Swapping

Figure I: An unassignable task u

Figure I depicts a simple example of a task u that is unassignable due to prior scheduling commitments. In this case, u requires capacity on a particular resource r, and the time interval R eqfntr ,u = [est ... - posr,u, lftu + depos,. ,u] defines the "footprint" of u's allocation requirement. Within R eqfnt,. ,u , an allocation duration alloc-durr,u = posr,u + du + deposr,u is required. Thus, to accommodate u, a subin­ terval of capacity within Reqfnt r,u of at least alloc-durr,u must be freed up.

To free up capacity for u, one or more currently scheduled tasks must be retracted. We define a conflict Con fl ict,. ,int on a resource r as a set of tasks of size C ap,. that simul­ taneously use capacity over interval int . Intuitively, this is an interval where resource r is currently booked to capacity. We define the confict set ConflictSetu of an unassignable task u to be the set of all distinct conflicts over Req I nt ,. u on all r E R .... In Figure I, for example, ConflictSetu ' {{a , b} , {b,c}, {d, e}}.

MissionSwap(t ask, Prot ect ed)

1. Prot ect ed +- Protect ed U {task}
2. ConflictSet +- ComputeTaskConflicts (task)
3. R et ract ed+- RetractTasks (ConflictSet , Protect ed)
4. if R etracted = 0 then Retum(0) ; failure
5. ScheduleTask(task)
6. SchedulelnPriorityOrder(Retract ed, least-flexible-first)
7. loop for ( i E R etract ed 1\ status; = unassigned) do
8. Prot ect ed+- MissionSwap(i, P rot ect ed)
9. ; failure
10. if P rot ect ed = 0 then Retum(0)
11. IO.end-loop
12. Return( Prot ect ed) ; success
13. 12.end

RetractTasks(Conflicts, Prot ect ed)

1. R etract ed +- 0
2. loop for (OpSet E Conflicts do
3. if ( OpSet - Protect ed) = 0 then Retum(0)
4. t +- ChooseTaskToRetract(OpSet - P rot ected)
5. UnscheduleTask(t)
6. Retract ed +- Retract ed U { t}
7. end-loop
8. Return(Ret racted)
9. end

Figure 2: Basic MissionSwap Search Procedure

Given these preliminaries, the basic repair search proce­ dure for inserting an unassignable task, referred to as Mis­ sionSwap, is outlined in Figure 2. It proceeds by computing ConflictSet task (line 2), and then retracting one conflict­ ing task for each Conflictr ,int E ConflictSet task (line3). This frees up capacity for inserting task (line 5), and once this is done, an attempt is made to feasibly reassign each re­ tracted task (line 6). For those retracted tasks that remain unassignable, MissionSwap is recursively applied (lines 710). As a given task is inserted by MissionSwap, it is marked as protected, which prevents subsequent retraction by any later calls to MissionSwap.

In Figure 3, top-level InsertUnassignableTasks proce­ dure is shown. Once MissionSwap has been applied to all unassignable tasks, one last attempt is made to schedule any remaining tasks. This step attempts to capitalize on any op­ portunities that have emerged as a side-effect of Mission­ Swap's schedule re-arrangement.

The driver of this repair process is the retraction heuristic ChooseTaskToRetract. We define several possibilities in the next subsection.

3.2 Retraction Heuristics

In designing a retraction heuristic, our general goal is to re­ tract the task assignment that posseses the greatest potential for reassignment. One simple estimate ofthis potential is the scheduling flexibility provided by a task's feasible execution interval. More precisely, let avail-dur; = lft; - eft; repre­ sent the amount of time available for executing task i . Then a simple, resource-indepedent measure of flexibility is

However, recall that d; is not the total amount of time that the supporting resource must be allocated for. d; only ac­ counts for the time required to execute the task; it does not account for the time to position and deposition the resource for task execution. The total time that a given resource r must be allocated for is alloc-durr,i = posr,i + d; + deposr,i. Given that the resources being allocated are generally sched­ uled near to capacity, a worst-case, resource-dependent mea­ sure offlexibilty is

Using this notion, we define an overall measure of i 's tempo­ ral flexibility as

and the following retraction heuristic:

where C E ConflictSetu for some unassignable task u.

An alternative approach to estimating a task i 's poten­ tial for reassignment is to measure the level of contention across its required execution interval Reqlntr,i · Assume as before that Conflict Set; is the set of conflicts within Reqlntr,;Vr E R;. Then, a very basic measure of ~on­ tention for a given task i is simply the number of conf11cts, i.e. ICon fl ictSet; 1. For purposes of choosing which task to retract in the case of a conflict C E Con flictSetu, this mea­ sure leads to a "min-conflicts" like heuristic[Minton eta/. , 1992]:

M inCon fl icts = i E C : IConflictSet; I :::; IConflictSet j I

A potentially more informed measure of contention is one that considers the proportion of a task i's required execution interval on resource r that is currently unavailable (i .e. , con­ tained in a conflict). For any conflict Cr,int E Con fl ictSet;, assume that durc designates the duration of int . Then we define a task i 's overall contention level as

Using this measure, we can define a third retraction heuristic:

4 Computational Analysis

The genesis of the max-flexibility heuristic and the mission­ swap algorithm took place while experimenting with the canonical data set used to test and demonstrate the AMC Al­ locator. This data set, which we'll refer to as the Tutorial Data Set consists of982 actual missions (3,251 operations) and 12 act~al air wings, and represents a two to three week horizon of AMC airlift and air refueling missions.

Using the basic allocation procedure the system is able to feasibly allocate all but two of the 982 missions in the Tutorial Data Set. For demonstration purposes those two missions are usually added to the schedule by over-allocating a given wing.

It turned out that this particular data set was not as re­ source over-constrained as we had thought. Application of the mission-swap algorithm with even a random retraction heuristic is able to schedule the two unassignable missions in a few seconds.

4.1 Experimental Design

For our experiments we generated data sets using the Tutorial Data Set as a seed: five data sets of twenty problems each were generated, with the wing capacities randomly reduced from 0 to 10%, 0 to 20%, 0 to 30%, 0 to 40%, and 0 to 50%. For each data set, the basic allocation procedure was employed to quickly schedule as many missions as possible in priority order. The number of unassignable missions was recorded, and then InsertUnassignableTasks was executed on the set of unassignable missions. Then run-time, nodes searched (number of times MissionSwap was called), and final number of unassignable missions were recorded. For each run this process was repeated with min-conflicts, min­ contention, max-flexibility and random choice as the retrac­ tion heuristic (ChooseTaskToRetract, in Figure2).

Experiments were run on a 1.8Ghz Pentium IV PC with 1Gb of RAM, running Windows 2000. The scheduling engine is implemented in Allegro Common Lisp 6.1.

4.2 Results

The results of our experiments are shown in Figures 4, 5, and 6. As expected, as the random degree of over­ allocation was increased from 10% to 50%, the number of initial unassignable missions increased, as did the numbers of unassignables after application oflnsertUnassignableTasks. Over all problem sets the baseline random-choice heuristic was able to assign 36% of the unassignable missions. Min­ conflicts, min-contention and max-flexibility were able to as­ sign 30%, 38%, and 42%, respectively.

What is most striking, though, are the results shown in fig­ ures five and six. While max-flexibility achieved somewhat better results in solution quality, it did so while searching far less and reaching a solution far more quickly than any of the competing heuristics.

4.3 Discussion

Our preliminary results show that in the face of a resource constrained scheduling problem, the decision of what tasks to temporarily retract in order admit more tasks into the sched­ ule may be delegated to an extremely simple and cheap retrac­ tion heuristic: max-flexibility. In order for this heuristic to be effective it should retract tasks that have a high likelihood of reassignment elsewhere within their feasible windows.

It is somewhat counter-intuitive, then, that max-flexibility is able to perform so well, based only on task flexibility tore­ schedule, irrespective of other competing tasks in the sched­ ule. Min-contention performance approaches that of max­ flexibility, but only at significant additional cost - approxi­ mately triple the run-time on average in our experiments.

Our conjecture is that as a schedule becomes more and more highly constrained, contention will increase to the limit of available capacity, and thus its measure will serve as a less informed heuristic. Under these conditions, though, a met­ ric based on a task's "innate" flexibility to schedule along a timeline might be more useful.

5 Related Work

The use of measures of temporal flexibility and resource con· tention as guidance for variable and value ordering has a long history in the field of constraint-directed scheduling [Sadeh, 1991; Smith and Cheng, 1993; Beck, 1999 ], although for the most part use has been in constructive search contexts. Our work, alternatively, seeks to exploit these measures in an iter­ ative repair search context, to determine which tasks to retract and reassign.

Work in manufacturing scheduling domains has addressed a broad range of priority based scheduling problems [Mor­ ton and Pentico, 1993 ], and some of this work (e.g., [Smith, 1994 ]) discusses heuristic techniques for schedule repair. However, a broad assumption that underlies most of this work is that due dates are relaxable and the objective is to minimize tardiness. As such, these are not over-subscribed problems in the same sense as the type of problem considered here.

Research in the domain of space mission planning and scheduling, alternatively, has focused on the solution of over­ subscribed problems (e.g., [Minton et a!., 1992; Johnston and Miller, 1994; Rabideau et a!., 1999 ]). Generally this re­ search is aimed at solving the single mission, single resource problem (e.g., the observing schedule for a space telescope). [Zweben et al., 1994]'s shuttle ground processing domain is one exception, wherein both multiple resources and multi­ capacity resources are considered. The approach employed here is repair-based, and simple heuristics are employed to mitigate resource constraint violations. It is not clear how useful this technique would be, however, in addressing prob­ lems where maintaining task priority is crucial.

Recent work in the area of scheduling observations on mul­ tiple earth satellites comes closest to tackling the same is­ sues which we address: multiple resources, multi-capacity resources, fixed time windows, and mission priority. [Pem­ berton, 2000] proposes a solution to preserving priority in the face of over-constrained resources by segmenting the prob­ lem into priority classes, solving them individually, and re­ combining them. [Frank et a!., 200 I] propose a contention­ based heuristic for use in solving a very similar problem within an iterative sampling framework. However, no experi­ mental analysis is given.

Finally, work in constraint satisfaction problem solving (CSP) has explored ideas similar to those introduced in this paper. [Verfaillie and Schiex, 1994] describe a repair proce­ dure similar to MissionSwap for non-disruptively resolving conflicts in dynamic CSPs (actually motivated by previous work on a continuous, single-resource scheduling problem). [Prestwich, 200 I] utilizes a "largest domain first" retraction heuristic to drive an incomplete backtracking procedure.

6 Conclusions

We have presented a novel retraction heuristic, max­ flexibility, and shown its applicability to a multi-mission air­ lift scheduling problem. This heuristic is much faster and less memory intensive than min-conflicts and min-contention, and provides better solution quality. We suggest that max­ flexibility as used in a generic task swapping algorithm like mission-swap may generally be applicable to resource­ constrained scheduling problems with fixed time windows. This method is particularly suitable to dynamic scheduling domains, where an existing schedule must be preserved as tasks change and new ones are added.

It is possible that with further study and experimentation a more informed retraction heuristic than max-flexibility might be found. It is likely, though, that such a heuristic would be much more expensive, and that a heuristic that is fairly smart, but very cheap, may be the best choice of all.

Acknowledgements

The work reported in this paper was sponsored in part by the Department of Defense Advanced Research Projects Agency (DARPA) and the US Air Force Research Labora­ tory under contracts F30602-00-2-0503 and F30602-02-20149, by the USAF Air Mobility Command under subcon­ tract 10382000 to Northrop-Grumman Corporation, and by the CMU Robotics Institute.