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