Simulated annealing and tabu search for multi-mode project payment scheduling

This paper involves the multi-mode project payment scheduling problem where the activities can be performed with one of several discrete modes and the objective is to assign activities' modes and progress payments so as to maximize the net present value of the contractor under the constraint of project deadline. Using the event-based method the basic model of the problem is constructed and in terms of the different payment rules it is extended as the progress based, expense based, and time based models further. For the strong NP-hardness of the problem which is proven by simplifying it to the deadline sub-problem of the discrete time-cost tradeoff problem, we develop two heuristic algorithms, namely simulated annealing and tabu search. to solve the problem. The two heuristic algorithms are compared with the multi-start iterative improvement method as well as random sampling on the basis of a computational experiment performed on a data set constructed by ProGen project generator. The results show that the proposed simulated annealing heuristic algorithm seems to be the most promising algorithm for solving the defined problem especially when the instances become larger. In addition, the effects of several key parameters on the net present value of the contractor are analyzed and some conclusions are given based on the results of the computational experiment. (C) 2008 Elsevier B.V. All rights reserved.