Research On Evolution Strategy Algorithm For Multi-skill Resource-constrained Project Scheduling Problem

Smart manufacturing is a key strategy for the transformation and development of China’s industry,which includes product design,manufacturing,service,etc.Planning and scheduling is an important component of intelligent decision and also a core part of smart manufacturing.Resource-constrained project scheduling problem(RCPSP)is inspired from the practice of project management,which provide reasonable schedule and resource plan for tasks under the resource constraints and sequence constraints.However,the basic RCPSP is a rather abstract model and therefore cannot be directly applied to all cases.Multiskill resource-constained project scheduling problem(MS-RCPSP)is an extension of RCPSP on resource concept.The introduction of skill and the skill constraints between task and resource makes MS-RCPSP suitable for the scheduling of multi-skill human resource and multi-purpose machine.Typical applications can be seen in software development staffing,mobile assembly line workforce planning and agicultural project scheduling with unmanned aerial vehicle.Current limitatoins on MS-RCPSP is listed as follows:(1)most research focused on single-objective optimizatoin,while few on multi-objective ones;(2)most existing problem models were established under deterministic assumption,i.e.,all parameters are known at the beginning and static,while few models were made for uncertainty environment;(3)most proposed metaheuristics for MS-RCPSP just applied generic operator without considering the dedicated problem characteristics of MS-RCPSP.This thesis focusses on MS-RCPSP and its variants,i.e.,single-objective,multiobjective,and stochastic duration.A classical metaheuristics algorithm-evolution strategy(ES)and its adaptations are applied to solve these problems.A summary is given as below.ES has been applied to solve single-objective MS-RCPSP with makespan minimization.First,a resource-list encoding scheme and a left-shift-and-greedy-task decoding scheme were adopted.Second,a resource-balanced strategy is used to improve the quality of initial popluation.Third,we designed a reassign operator baed on critical resource to improve the search performance.In numerical experiment,we have conducted a comparion between ES and other state-of-art alogirhtms(GA,DEGR and DOMVO),and the results have proved the effectiveness and strength of ES.To solve bi-objective MS-RCPSP with makespan and cost minimization,we proposed multi-objective evolution strategy(MOES).First,we dersigned an encoding scheme with a partial task list and a full-size resource list,which maintains a lart search space while removing the solution with bad quality.A repair-and-greedy decoding scheme is designed featuring the repair process of task list with prcedence violation.Second,a Pareto archive is adopted to store all founded Pareto optimal solution during the search process.Third,a selection operator with fast non-dominated sorting technique and crowdeding distance measurement is used to choose potential solutions from Pareto archive.Last,for mutation operator,we used a swap operator to tweak the task list and the propsoed reassign operator to tweak the resource list.In numerical experiment,we introduced NTGA and MOFOA as competitors.As for multi-objective optimzation problem,we adopted several quality indicators from differnet aspects,e.g.,convergence and uniformity.The results proved the superiority of MOES over other algorithms.To solve MS-RCPSP with stochastic duration(MS-SRCPSP),we proposed a scenariobased multi-objective evolution strategy(S-MOES).This algorithm features a scenario generation mangement which reduce the computation effort at the initial stage.A comparison between S-MOES and deterministic MOES is conducted and the effectiveness of S-MOES is validated.Lastly,a case study – smart reconstruction of a warehouse is given to validate the feasibility of MS-SRCPSP model and the effectiveness of S-MOES.