A branch-and-bound procedure for the multiple resource-constrained project scheduling problem

A branch-and-bound procedure for the multiple resource-constrained project scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19932177
Country: United States
Volume: 38
Issue: 12
Start Page Number: 1803
End Page Number: 1818
Publication Date: Dec 1992
Journal: Management Science
Authors: ,
Keywords: scheduling, networks, programming: branch and bound
Abstract:

In this paper a branch-and-bound procedure is described for scheduling the activities of a project of the PERT/CPM variety subject to precedence and resource constraints where the objective is to minimize project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. Precedence and resource-based bounds described in the paper are combined with new dominance pruning rules to rapidly fathom major portions of the solution tree. The procedure is programmed in the C language for use on both a mainframe and a personal computer. The procedure has been validated using a standard set of test problems with between 7 and 50 activities requiring up to three resource types each. Computational experience on a personal computer indicates that the procedure is 11.6 times faster than the most rapid solution procedure reported in the literature while requiring less computer storage. Moreover, problems requiring large amounts of computer time using existing approaches for solving this problem type are rapidly solved with the present procedure using the dominance rules described, resulting in a significant reduction in the variability in solution times as well.

Reviews

Required fields are marked *. Your email address will not be published.