RI | Publications | Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations

Text only version of this site

Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations
X. Wang and S. Smith
Proceedings of the 15th International Conference on Automated Planning and Scheduling, ICAPS'05, June, 2005.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [187 KB]

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

In many resource constrained scheduling applications, the ability to vary task durations provides another degree of freedom for resolving resource conflicts. Furthermore, when each task is associated with a duration-dependent quality profile, activity durations must be determined to maximize overall quality while respecting process deadlines and resource capacity constraints. In this paper, we formulate this type of scheduling problem, which we refer to generally as quality maximization. We develop and empirically evaluate a new precedence constraint posting (PCP) algorithm, along with a number of search control heuristics for solving this class of problems. Our PCP algorithm incorporates linear optimization to set activity durations at each step, and search control heuristics direct the search toward resource feasibility. A central concept in the heuristics we define is use of a measure that combines an activity's reducible duration with its quality profile as a basis for determining how to resolve resource conflicts. This concept is found to yield heuristics that exhibit superior performance. Surprisingly, we also find that use of a simple local estimation of quality degradation at each posting step leads to better performance than use of an exact computation at dramatically reduced computation expense. Overall, the experimental analysis indicates that a good heuristic must strike the right balance between minimizing quality loss at each step and retaining flexibility for future duration reduction.

Notes

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory

Number of pages: 10

Text Reference

X. Wang and S. Smith, "Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations," Proceedings of the 15th International Conference on Automated Planning and Scheduling, ICAPS'05, June, 2005.

BibTeX Reference

@inproceedings{Wang_2005_5001,
   author = "Xiaofang Wang and Stephen Smith",
   title = "Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations",
   booktitle = "Proceedings of the 15th International Conference on Automated Planning and Scheduling, ICAPS'05",
   month = "June",
   year = "2005"
}