Search space decomposition for resource-constrained project scheduling: Fid-Bau Portal

Search space decomposition for resource-constrained project scheduling

Liu, Zhenyuan / Hua, Zhengming / Yang, Liu / Deng, Raoyi

Abstract The mechanism with search space decomposition has been ever proposed for resource-constrained project scheduling which can reduce the search space. Theoretical equivalence for search spaces before and after decomposition is proven in this paper. It is shown that the mechanism can be easily incorporated in diverse algorithms. Four experiential strategies and a theoretical strategy are presented. The decomposition-based approach is nested in three classic algorithms to verify the effectiveness of the mechanism in numerical experiments. The results show that the decomposition-based approach can improve the quality of schedules under certain conditions, and the influence is diverse from the algorithms in which they are incorporated. Moreover, the most suitable decomposition strategies for each algorithm are different. Future work, such as priority-rules based on the decomposition strategies, strategies according to the parameters of activity network, and parallel computing with the decomposition mechanism, may bring new opportunities in project scheduling.

Highlights • Approach with search space decomposition for resource-constrained project scheduling. • Theoretical equivalence for search spaces before and after decomposition proven. • Experiential and theoretical decomposition strategies are developed. • New enhanced algorithms easily constructed with other algorithms for RCPSP. • Effectiveness of decomposition strategies verified with numerical experiments on PSPLIB.