K.U.Leuven - Departement toegepaste economische wetenschappen
DTEW Research Report 9949 pages:1-33
In this paper we study the unconstrained project scheduling problem with discounted cash flows where the net cash flows are assumed to be linear dependent on the completion times of the corresponding activities. Each activity of this unconstrained project scheduling problem has a known deterministic net cash flow which is linear and non-increasing in time. Progress payments and cash outflows occur at the completion of activities. The objective is to schedule the activities in order to maximize the net present value (npv) subject to the precedence constraints and a fixed deadline. Despite the growing amount of research concerning the financial aspects in project scheduling, little research has been done on the problem with time-dependent cash flows. Nevertheless, this problem gives an incentive to solve more realistic versions of project scheduling problems with financial objectives. We introduce an extension of an exact recursive algorithm which has been used in solving the max-npv problem with time-independent cash flows and which is embedded in an enumeration procedure. The recursive search algorithm schedules the activities as soon as possible and searches for sets of activities to shift towards the deadline in order to increase the net present value. The enumeration procedure enumerates all sets of activities for which such a shift has not been made but could, eventually, have been advantageous. The procedure has been coded in Visual C++ version 4.0 under Windows NT and has been validated on a randomly generated problem set.