A tabu search procedure for the Resource Constrained Project Scheduling Problem with Discounted Cash Flows

In this paper, the Resource Constrained Project Scheduling Problem with Discounted Cash Flows (RCPSPDC) is considered. This problem involves scheduling the project activities with cash inflows and outflows, in such a way the net present value of the cash flows is maximized subject to resource and precedence constraints. A tabu search procedure was proposed as a heuristic solution technique for this problem. The procedure was, then, modified to invoke a long term memory function. Both procedures were tested on 50 problems derived from Patterson’s data set. Solutions produced by these procedures were compared to upper bounds obtained from a Linear Programming Relaxation of RCPSPDC which is strengthened by valid cuts. Furthermore, a comparison of these solutions to solutions obtained by Minimum Slack Heuristic was provided. In general, Tabu Search successfully produced near-optimal solutions with reasonable computational effort.