A preview version of the paper that appeared in Journal of Heuristics, Volume 8, 2002.
A Constraint-Based Method for 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
This paper presents a heuristic algorithm for solving RCPSP/max, the
resource constrained project scheduling problem with generalized
precedence relations. The algorithm relies, at its core, on a
constraint satisfaction problem solving (CSP) search procedure, which
generates a consistent set of activity start times by incrementally
removing resource conflicts from an otherwise temporally feasible
solution. Key to the effectiveness of the CSP search procedure is its
heuristic strategy for conflict selection. A conflict sampling method
biased toward selection of minimal conflict sets that involve
activities with higher-capacity requests is introduced, and coupled with a
non-deterministic choice heuristic to guide the base conflict
resolution process. This CSP search is then embedded within a larger
iterative-sampling search framework to broaden search space coverage
and promote solution optimization. The efficacy of the overall
heuristic algorithm is demonstrated empirically on a large set of
previously studied RCPSP/max benchmark 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
US Department of Defense Advanced Research Projects Agency under
contract F30602-97-20227, and by the CMU Robotics Institute.
Copyright 2000, Cesta, Oddi and Smith.
All rights reserved.
Full paper in Postscript