Research On Hyper-heuristic Approach For Complex Multi-skill Resource-constrained Project Scheduling Problems

Resource-constrained project scheduling problem is the core of project management,which has a strong background of engineering application.It is widely encountered in the fields of manufacturing,engineering management,scientific service,etc.Research on this problem has been a hotspot in academia and industry.In RCPSP,a set of tasks with precedence relations is scheduled over time to optimize certain objectives(such as the project duration),while satisfying precedence constraints and resource availabilities.Considering the complexity of resource characteristics,the classical RCPSP model is not suitable for all the conditions.Therefore,the multi-skill resource-constrained project scheduling problem(MS-RCPSP)is proposed.In MS-RCPSP,each resource masters several skills with certain familiarity levels and each task requires a skill with certain type at the minimum level.If and only if the resource masters the required skill and the familiarity level is no less than the minimum level,the task can be assigned to the resource.As an effective search methodology,hyper-heuristic automatically selects,combines or generates several simple low-level heuristics(LLHs)to handle complicated optimization problems.Over the past few years,hyper-heuristic attracts a growing number of attentions.In this paper,the framework of hyper-heuristic is employed to address MS-RCPSP with single objective and multi-objective.The main research contents of this paper are as follows:(1)In this paper,a genetic programming hyper-heuristic(GP-HH)algorithm is proposed to address MS-RCPSP with single objective.Firstly,a single task sequence vector is used to encode the 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 LLHs.Thirdly,genetic programming is utilized as a high-level heuristics(HLH)which can manage the LLHs 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.(2)In this paper,a decomposition based genetic programming hyper-heuristic(GP-HH/D)algorithm is proposed to address MS-RCPSP with multi-objective.Different from GP-HH,GP-HH/D divided the multi-objective MS-RCPSP into several sub-problems.In order to design an efficient parameter combination,GP-HH/D adopts some parameters of GP-HH and employs the same population size and the maximum number of iterations of the comparing algorithm.In addition,the iMOPSE benchmark dataset is also employed to evaluate the performance of GP-HH/D.Computational comparisons between GP-HH/D and the state-of-the-art algorithms indicate the superiority of the proposed GP-HH/D.As the first hyper-heuristic framework which has been applied to MS-RCPSP,the proposed algorithms show great performance,the innovations of this study are as follows:(1)As a newly proposed algorithm,hyper-heuristic framework attracts a growing number of attentions.However,this is nobody has employed it to solve MS-RCPSP.In this paper,an efficient hyper-heuristic framework is presented to address MS-RCPSP with different objectives,which designs effective HLH strategy and LLHs methods.Based on the characteristic of the problem,a novel repair-based decoding scheme is designed to generate feasible schedules.This study extends the application of hyper-heuristic framework.(2)To design an efficient and universal hyper-heuristic framework,it is crucial to investigate the characteristic of the problem.In this paper,the effective heuristic rules are employed to construct LLHs,which can improve the search ability of the algorithm.Moreover,the genetic programming(GP)is employed as the HLH strategy to manage and organize a set of LLHs methods dynamically.Based on the methods mentioned above,the GP-HH and GP-HH/D are constructed to enrich the theory of the hyper-heuristic.(3)The researches of the hyper-heuristic are mainly focused on the optimization problem with single objective,while the method has not been applied to the multi objective problem.In this paper,a decomposition based genetic programming hyper-heuristic is proposed by embedding the idea of decomposition into the GP-HH.In GP-HH/D,a set of LLHs which contains ten heuristic rules and a novel repair-based decoding scheme are proposed to generate efficient schedules.Computational comparisons between GP-HH/D and the state-of-the-art algorithms indicate the superiority of the proposed GP-HH/D.