A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. (February 2020)

• Record Type: Journal Article
• Authors: Lin, Jian; Zhu, Lei; Gao, Kaizhou
• Is Part Of: Expert systems with applications. Volume 140(2020)
• Publication Date: 2020-02
• Subjects: Genetic programming -- Hyper-heuristic -- Multi-skill -- Project scheduling; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.112915
• Languages: English
• ISSNs: 0957-4174

Abstract

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.