A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem

摘要

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 hyperheuristic (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. (C) 2019 Elsevier Ltd. All rights reserved.