Profile-Based Algorithms to Solve Multiple Capacitated Metric Scheduling Problems

Amedeo Cesta, Angelo Oddi, and Stephen F. Smith

Though CSP scheduling models have tended to assume fairly general representations of temporal constraints, most work has restricted attention to problems that require allocation of simple, unit-capacity resources. This paper considers an extended class of scheduling problems where resources have capacity to simultaneously support more than one activity, and resource availability at any point in time is consequently a function of whether suffcient unallocated capacity remains. We present a progression of algorithms for solving such multiple-capacitated scheduling problems, and evaluate the performance of each with respect to problem solving ability and quality of solutions generated. A previously reported algorithm, named the Con ict Free Solution Algorithm (CFSA), is first evaluated against a set of problems of increasing dimension and is shown to be of limited effectiveness. Two variations of this algorithm are then introduced which incorporate measures of temporal exibility as an alternative heuristic basis for directing the search, and the variant making broadest use of these search heuristics is shown to yield significant performance improvement. Observations about the tendency of the CFSA solution approach to produce unnecessarily overconstrained solutions then lead to development of a second heuristic algorithm, named Earliest Start Time Algorithm (ESTA). ESTA is shown to be the most effective of the set, both in terms of its ability to efficiently solve problems of increasing scale and its ability to produce schedules that minimize overall completion time while retaining solution robustness.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.