The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems

Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory

Number of pages: 24

Text Reference

Qu Zhou and Stephen Smith , "A Priority-Based Preemption Algorithm for Incremental Scheduling with Cumulative Resources," tech. report CMU-RI-TR-02-19, Robotics Institute, Carnegie Mellon University, June, 2003

BibTeX Reference

@techreport{Zhou_2003_4426,
   author = "Qu Zhou and Stephen {Smith }",
   title = "A Priority-Based Preemption Algorithm for Incremental Scheduling with Cumulative Resources",
   booktitle = "",
   institution = "Robotics Institute",
   month = "June",
   year = "2003",
   number= "CMU-RI-TR-02-19",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu