An Iterative Sampling Procedure for Resource Constrained Project Scheduling with Time Windows

Abstract

In this paper, we extend and integrate pre-viously reported techniques for resource con-strained scheduling to develop a CSP proce-dure for solving RCPSP/max, the resource con-strained project scheduling problem with time windows (generalized precedence relations be-tween start time of activities). RCPSP/max is a well-studied problem within the Opera-tions 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 gen-eralizes 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 con-flict resolution. Since RCPSP/max is an opti-mization problem, other ideas from prior work are adapted to embed this base CSP model within a multi-pass, iterative sampling proce-dure. The overall procedure, called ISES (It-erative Sampling Earliest Solutions), is applied to the above mentioned set of benchmark prob-lems. ISES is shown to perform quite well in comparison to current state-of-the-art proce-dures for RCPSP/max, particularly as search space size becomes limiting for systematic pro-cedures. 1