Early-tardy cost trade-offs in resource constrained projects with cashflows: An optimization-guided heuristic approach

In this paper the authors consider the Resource Constrained Project Scheduling Problem with the objective of maximizing the Net Present Value of project cash flows. They present eight greedy heuristics, embedded in a single-pass, forward algorithm that uses information from a relaxed optimization model to schedule activities. In contrast to the previous research, activities are released for scheduling when they are precedence feasible. The heuristics require the evaluation of the earliness costs and tardiness penalties for each activity that are provided by the relaxed optimization model. The authors compare the performance of these heuristics to that of heuristics selected from our earlier research that delay the consideration of an activity for scheduling until the activities’ target time specified by the optimization model becomes current. The results of a series of experiments across 144 different experimental environments indicate that the early release heuristics provide superior NPV results in many project environments.