Exact and truncated branch-and-bound procedures for resource-constrained project scheduling with discounted cash flows and general temporal constraints

This paper is concerned with resource-constrained project scheduling problems where cash flows are associated with project activities and the net present value of the project is to be maximized. The temporal constraints between the activities are given by minimum and maximum time lags. First we study the structure of the sets of feasible and optimal schedules for the net present value problem with and without resource constraints. After that we briefly sketch a steepest ascent algorithm for the problem without resource constraints. This algorithm together with a dual variant is used for a branch-and-bound procedure for the problem with resource constraints, which is presented next. To solve larger problem instances approximately two truncated branch-and-bound procedures are proposed. An experimental performance analysis shows that the new algorithms outperform the solution methods known so far significantly.