Exploiting temporal flexibility to obtain high quality schedules

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. Copyright © 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.