Proceedings IJCAI-99, Stockholm, August, 1999
An Iterative Sampling Procedure for Resource Constrained
Project Scheduling with Time Windows
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
In this paper, we extend and integrate previously reported techniques
for resource constrained scheduling to develop a CSP procedure for
solving RCPSP/max, the resource constrained project scheduling problem
with time windows (generalized precedence relations between start time
of activities). RCPSP/max is a well-studied problem within the
Operations Research community and the presence of a large set of
benchmark problems provides a good opportunity for comparative
performance analysis. Our base CSP scheduling model generalizes
previous profile-based approaches to cumulative scheduling by focusing
on global analysis of minimal conflicting sets rather than
pairwise conflict analysis. This generalization increases the
tendency for more effective conflict resolution. Since RCPSP/max is
an optimization problem, other ideas from prior work are adapted to
embed this base CSP model within a multi-pass, iterative sampling
procedure. The overall procedure, called ISES (Iterative Sampling
Earliest Solutions), is applied to the above mentioned set of
benchmark problems. ISES is shown to perform quite well in comparison
to current state-of-the-art procedures for RCPSP/max, particularly as
search space size becomes limiting for systematic procedures.
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 1999, Cesta, Oddi and Smith.
All rights reserved.
Full paper in Postscript