A Priority-Based Preemption Algorithm for Incremental Scheduling with Cumulative Resources

Abstract

When scheduling in dynamic continuous environments, it is necessary to integrate new tasks in a manner that reflects their intrinsic importance while at the same time minimizing solution change. A scheduling strategy that re-computes a schedule from scratch each time a new task arrives will tend to be quite disruptive. Alternative a purely non-disruptive scheduling strategy favors tasks that are already in the schedule over new ones, regardless of respective priorities. In this paper, we consider algorithms that attempt to strike a middle ground. Like a basic non-disruptive strategy, the algorithm we propose emphasizes incremental extension/revision of an existing schedule, rather than regeneration of a new schedule from scratch. However, by allowing selective preemption of currently scheduled tasks, our algorithm also gives attention to the relative importance of new tasks. We consider a specific class of scheduling problems involving the allocation of cumulative (or multi-capacity) resources. We develop an approach to preemption based on the concept of freeing up a resource area (i.e., time and capacity rectangle) comparable to the resource requirement of the new task to be scheduled. Through experimental analysis performed with a previously developed system for air combat operations scheduling, we demonstrate that our priority-based preemption algorithm is capable of producing results comparable in solution quality to those obtained by regenerating a new schedule from scratch with significantly less disruption to the current schedule.