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

Xiaofang Wang and Stephen Smith
Proceedings of the 15th International Conference on Automated Planning and Scheduling, ICAPS'05, June, 2005.


Download
  • Adobe portable document format (pdf) (188KB)
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(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Number of pages: 10

Text Reference
Xiaofang Wang and Stephen 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",
}