A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. (February 2020) - Lin, Jian; Zhu, Lei; Gao, Kaizhou
Highlights: A GP-HH scheme is proposed to solve the MS-RCPSP. A repair-based decoding scheme is developed to generate feasible schedules. Ten simple heuristic rules are designed to construct a set of low-level heuristics. The performance of the proposed GP-HH is evaluated on a benchmark dataset. New best solutions are obtained by the proposed hyper-heuristic approach. Abstract: Multi-skill resource-constrained project scheduling problem (MS-RCPSP) is one of the most investigated problems in operations research and management science. In this paper, a genetic programming hyper-heuristic (GP-HH) algorithm is proposed to address the MS-RCPSP. Firstly, a single task sequence vector is used to encode solution, and a repair-based decoding scheme is proposed to generate feasible schedules. Secondly, ten simple heuristic rules are designed to construct a set of low-level heuristics. Thirdly, genetic programming is utilized as a high-level strategy which can manage the low-level heuristics on the heuristic domain flexibly. In addition, the design-of-experiment (DOE) method is employed to investigate the effect of parameters setting. Finally, the performance of GP-HH is evaluated on the intelligent multi-objective project scheduling environment (iMOPSE) benchmark dataset consisting of 36 instances. Computational comparisons between GP-HH and the state-of-the-art algorithms indicate the superiority of the proposed GP-HH in computing feasible solutions to the problem.