A two stage search heuristic for scheduling payments in projects

When the Net Present Value (NPV) of a project is used as a measure of its f inancial performance, effective management of cash flows over the duration of the project is critical for improved profitability. Progress payments ar e a major component of project cash flows. In many project environments, th e contractor can negotiate payment terms. Payments are typically tied to co mpletion of project activities and therefore have significant impact on the schedule of activities and the timing of the payments. In this paper, we c onsider the problem of simultaneously determining the amount, timing and lo cation of progress payments in projects to maximize NPV. Due to the combina torial nature of the problem, heuristics are a practical approach to solvin g the problem. We propose a two-stage heuristic where simulated annealing i s used in the first stage to determine a set of payments. In the second sta ge, activities are rescheduled to improve project NPV We compare the perfor mance of this general purpose heuristic with other problem-dependent heuris tics from the literature. Our results indicate that the simulated annealing heuristic significantly outperforms the parameter-based heuristics. Althou gh rescheduling in the second stage improves NPV, increases are relatively small in magnitude. While the specific parameters settings suggested by the simulated annealing heuristic in this study may have limited generalizabil ity at this time due to the narrow range of problems tested, our analysis s uggests that a pure simulated annealing approach is a very attractive alter native for obtaining good heuristic solutions to the complex problem of sch eduling payments in projects.