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

June 2005

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

Authors:

Xiaofang Wang and Stephen Smith

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.
@conference{Wang-2005-9185,
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 15th International Conference on Automated Planning and Scheduling (ICAPS '05)},
year = {2005},
month = {June},
pages = {212 - 221},
}
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.