An activity-list-based nested partitions algorithm for resource-constrained project scheduling

Abstract

The resource-constrained project scheduling problem (RCPSP) has received wide attention. In this paper, an activity-list-based nested partitions algorithm (ALNP) is developed for solving the RCPSP and a P-ALNP is proposed to improve ALNP with local adjustment. In the algorithms, to improve the search efficiency, a partial double justification is employed as local search mechanism. The computational experiments on the PSPLIB and analysis on robustness of the algorithms show that ALNP outperforms the traditional serial scheduling scheme for solving the large-scale, complex RCPSPs, and P-ALNP can improve ALNP and obtain better results. P-ALNP is a competitive algorithm for solving the RCPSP.

Keywords:

• resource-constrained project scheduling
• nested partitions
• activity list
• serial scheduling scheme
• double justification

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [grant number 71071062]; the Ministry of Education returned Fund and the Fundamental Research Funds for the Central Universities [grant number HUST: 2013TS130].