Exploiting Temporal Flexibility to Obtain High Quality Schedules

July 2005

Exploiting Temporal Flexibility to Obtain High Quality Schedules

Authors:

N. Policella, X. Wang, S. F. Smith, and A. Oddi

Abstract:

We consider a schedule optimization problem where each activity to be scheduled has a duration-dependent quality profile, and activity durations must be determined that maximize overall quality within given deadline and resource constraints. To solve this quality maximization problem, prior work has proposed a hybrid search scheme, where a linear programming solver for optimally setting the durations of temporally related activities is embedded within a larger search procedure that incrementally posts sequencing constraints to resolve resource conflicts. Under this approach, dual concerns of establishing feasibility and optimizing quality are addressed in an integrated fashion. In this paper, we propose an alternative approach, where feasibility and optimization concerns are treated separately: first, we establish a resource-feasible partial order schedule, assuming minimum durations for all activities; second, these fixed duration constraints are relaxed and quality optimal durations are determined. Experimental results indicate a tradeoff: when resource capacity constraints are loose, the integrated hybrid approach performs comparably to the separated scheme. However, in problems with tighter capacity constraints we find that separation of concerns enables both better solving capability and higher quality results. Following from these results, we discuss potential synergy between problem objectives of maintaining temporal flexibility and maximizing quality.
@conference{Policella-2005-120470,
author = {N. Policella And X. Wang And S. F. Smith And A. Oddi},
title = {Exploiting Temporal Flexibility to Obtain High Quality Schedules},
booktitle = {Proceedings of 20th National Conference on Artificial Intelligence (AAAI '05)},
year = {2005},
month = {July},
volume = {3},
pages = {1199 - 1204},
}
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.