Appeared in Proceedings 1999 Eurpoean Conference on Planning, UK, 1999:
Greedy Algorithms for the Multi-Capacitated Metric Scheduling Problem(*)
Amedeo Cesta (1), Angelo Oddi (1) and Stephen F. Smith (2)
National Research Council of Italy
Viale Marx 15, I-00137 Rome, Italy
(2) The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA
This paper investigates the performance of a set of greedy algorithms
for solving the Multi-Capacitated Metric Scheduling Problem (MCM-SP). All
algorithms considered are variants of ESTA (Earliest Start Time
Algorithm), previously proposed in [Cesta, Oddi, SMith 98]. The paper starts with an
analysis of ESTA's performance on different classes of MCM-SP problems.
ESTA is shown to be effective on several of these classes, but is also
seen to have difficulty solving problems with heavy resource contention.
Several possibilities for improving the basic algorithm are
investigated. A first crucial modification consists of substituting
ESTA's pairwise analysis of resource conflicts with a more aggregate and
thus more powerful Minimal Critical Set (MCS) computation. To cope with
the combinatorial task of enumerating MCSs,
several approximate sampling procedures are then defined.
Some systematic sampling strategies, previously shown effective on a related
but different class of scheduling problem,
are found to be less effective on MCM-SP. On the contrary, a randomized MCS
sampling technique is introduced, forming a variant of ESTA that is shown to
be quite powerful on highly constrained problems.
(*) 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.
Full paper in Postscript Format