CMU Robotics Institute Technical Report CMU-RI-TR-98-17.
Scheduling Multi-Capacitated Resources Under Complex Temporal Constraints
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
Most CSP scheduling models make the restrictive assumption
that a resource can only support a single activity at a time (i.e., it
is either available or in-use). However, in many practical domains,
resources in fact have the capability to simultaneously support
multiple activities, and hence availability at any point is a function
of unallocated {\em capacity}. In this paper, we develop and evaluate
algorithms for solving multi-capacitated scheduling problems. We
first define a basic CSP model for this extended problem class, which
provides a basic framework for formulating alternative solution
procedures. Using this model, we then develop variants of two
different solution approaches that have been recently proposed in the
literature: (1) a profile-based procedure - which relies on local
analysis of potential resource conflicts to heuristically direct the
problem solving process, and (2) a clique-based procedure - which
exploits a global analysis of resource conflicts at greater
computational cost. In each case, improvements are made to previously
proposed techniques. Performance results are given on a series of
problems of increasing scale and constrainedness, indicating the
relative strengths of each procedure.
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, Cesta, Oddi and Smith.
All rights reserved.
Full paper in Postscript