K.U.Leuven - Departement toegepaste economische wetenschappen
DTEW Research Report 9915 pages:1-24
In this paper we study the resource-constrained project scheduling problem with discounted cash flows. Each activity of this resource-constrained project scheduling problem has resource requirements for each resource type and a known deterministic cash flow which can be either positive or negative. Cash flows are assumed to be known in both their amount and timing. Progress payments and cash outflows occur at the completion of activities. The objective is to schedule the activities subject to a fixed deadline in order to maximize the net present value (npv) subject to the precedence and resource constraints. With these features the financial aspects of project management are no longer ignored. We introduce a depth-first branch-and-bound algorithm which makes use of extra precedence relations to solve a number of resource conflicts and a fast recursive search algorithm for the max-npv problem to compute the upper bounds. The recursive search algorithm exploits the idea that positive cash flows should be scheduled as early as possible while negative cash flows should be scheduled as late as possible within the precedence constraints. The procedure has been coded in Visual C++, version 4.0 under Windows NT and has been validated on three randomly generated problem sets.