A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows

A branch and bound procedure for the resource constrained project scheduling problem with discounted cash flows

0.00 Avg rating0 Votes
Article ID: iaor1998751
Country: United States
Volume: 42
Issue: 10
Start Page Number: 1395
End Page Number: 1408
Publication Date: Oct 1996
Journal: Management Science
Authors: ,
Keywords: programming: branch and bound, networks: scheduling
Abstract:

Management of projects is complicated by the scarcity of resources required to execute them. Limited resources usually extend the project completion times beyond those determined by CPM/PERT. Several solution procedures have been developed for solving the resource constrained project scheduling problem. One objective commonly used for these problems is to complete the project as early as possible (minimize makespan). The problem considered in this paper is a resource constrained project scheduling problem, with the added features that there are cash flows associated with the project activities, and the objective is to schedule the project activities in such a way that the net present value of cash flows is maximized. With these features the problem becomes financially motivated and more realistic. We introduce a branch and bound procedure to solve the resource constrained project scheduling problem with discounted cash flows. Our procedure exploits the known fact that potential resource violations can be eliminated by introducing additional precedence relations between certain project activities. Specifically, we use the ‘minimal delaying alternatives’ concept to resolve resource conflicts. The bounds in the branch and bound procedure are computed by solving Payment Scheduling Problems, which can be formulated as linear programs and by that are well-solvable. We test our procedure computationally on a set of 90 test problems from the literature and compare it with the only other exact procedure we know of.

Reviews

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