On maximizing the net present value of a project under renewable resource constraints

In this paper we study the resource-constrained project-scheduling problem with discounted cash flows. Each activity of this resource-constrained proj ect-scheduling problem has certain resource requirements and a known determ inistic cash flow that can be either positive or negative. Deterministic ca sh flows are assumed to occur over the duration of the activities. Progress payments and cash outflows occur at the completion of activities. The obje ctive is to schedule the activities subject to a fixed deadline to maximize the net present value subject to the precedence and resource constraints. With these features the financial aspects of project management are taken i nto account. We introduce a depth-first branch-and-bound algorithm that makes use of ext ra precedence relations to resolve a number of resource conflicts and a fas t recursive search algorithm for the max-npv problem to compute upper bound s. The recursive search algorithm exploits the idea that positive cash flow s should be scheduled as early as possible while negative cash flows should be scheduled as late as possible within the precedence constraints. The pr ocedure has been coded in Visual C++, Version 4.0 under Windows NT, and has been validated on two problem sets.