Solving time/cost trade-off problems with discounted cash flows using generalized Benders decomposition

In this article the authors consider a project scheduling problem where there are cash flows throughout the life of the project and where shorter activity durations can be attained by incurring greater direct costs. In particular, the objective of this problem is to determine the activity durations and a schedule of activity start times so that the net present value of cash flows is maximized. The authors formulate this problem as a mixed-integer nonlinear program which is amenable to solution using the generalized Benders decomposition technique developed by Geoffrion. They test the algorithm on 140 project scheduling problems, the largest of which contains 30 nodes and 64 activities. The present computational results are quite encouraging inasmuch as 123 of the 140 problems required less than 1 CPU second of solution time.