Comparison of a Multi-Pass Heuristic Decomposition Procedure with Other Resource-Constrained Project Scheduling Procedures

The purpose of this paper is to evaluate a heuristic procedure for solving the resource-constrained project scheduling problem. Projects that involve completing a sequence of well defined activities, some of which can be done in parallel, often are characterized by capacity limitations on some resources. This means schedules generated using standard critical path methods often are not feasible. Resource leveling procedures have been developed to improve the schedule. Formulating the problem with explicit resource constraints is another, more direct, way to accommodate limited capacities. Solution procedures to this problem include simple, single-pass heuristics and branch-and-bound optimization procedures. The former are easy to apply but may yield poor results. The latter provide optimal results but require a substantial amount of computation even for small problems. The procedure evaluated here is representative of a class of multi-pass procedures based on problem decomposition. A brief outline of the heuristic procedure and the method of decomposition is given in the paper. It is applicable to single or multiple project networks. Comparisons were made between this procedure and single-pass heuristics and branch-and-bound procedures. Solutions found using the multi-pass procedure were comparable to those obtained with a branch-and-bound optimization algorithm while computing times were significantly shorter. Analysis based on the sample of problems tested indicates the procedure is much less sensitive to problem size than the branch-and-bound algorithm. The evaluation, consisting of testing procedures using a set of test problems, is described in detail. The overall results suggest that the method and procedure used may provide an effective means of computing schedules for resource-constrained projects.