MPPSP and its simulated annealing and tabu search heuristics based on different payment rules

This paper involves the multi-mode project payment scheduling problem based on different payment rules. Firstly the studied problem is identified and the optimization models under different payment rules are constructed. For the strong NP-hardness of the problem, two heuristic algorithms, namely simulated annealing and tabu search, are developed. The two algorithms are tested and evaluated on the basis of a computational experiment performed on a data set constructed by ProGen. The results show that the proposed simulated annealing heuristic algorithm outperforms the tabu search heuristic algorithm especially when the instances become larger. The objective value ascends with the increase of the payment number or the compensation proportion whereas descends as the interest rate per period goes up. Moreover, the desirable objective values under the time-based, progress-based, and expense-based rules cannot exceed those under the corresponding basic rule anyway.