Proceedings AIPS-98, Pittsburgh PA, June, 1998

Profile-Based Algorithms to Solve Multiple Capacitated Metric Scheduling Problems

Amedeo Cesta (1), Angelo Oddi(1) and Stephen F. Smith(2)

(1) IP-CNR
National Research Council
Viale Marx 15
I-00137 Rome, Italy

(2)The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA

Abstract

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 sufficient 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 Conflict 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 flexibility 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.
Amedeo Cesta and Angelo Oddi's work is supported by Italian Space Agency, by CNR Committee 12 on Information Technology (Project SCI*SIA), and CNR Committee 4 on Biology and Medicine. Stephen F. Smith's work has been sponsored in part by the National Aeronautics and Space Administration under contract NCC 2-976, by the US Department of Defense Advanced Research Projects Agency under contract F30602-97-20227, and by the CMU Robotics Institute.
Copyright 1998, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
Full paper in Postscript