Hybrid L-SHADE Algorithm And Its Applied Research In The Distributed Shop Scheduling Problem

In the background of the economic globalization,cooperation among enterprises are increasing,the distributed manufacturing has become a common production model.In the distributed manufacturing mode,the efficient scheduling optimization is not only effectively applied to improve the comprehensive production efficiency of enterprises,but also integrate the distributed production resources to reduce the production energy consumption.The distributed shop scheduling problem is based on the cooperative production among different enterprises to study the distribution of jobs between factories and the processing sequence in each factory to achieve the optimal scheduling index.The distributed shop scheduling problem has been proved to be an NP-hard problem,which is difficult to solve.With the increasing of production scale,the difficulty of solving the distributed production shop scheduling problem has been become complex.Therefore,the distributed production shop scheduling problem has important academic significance and practical application.In the face with problems of different scales,traditional methods have been unable to satisfy the requirements in practical production.Therefore,the theoretical research and effective scheduling schemes of the shop scheduling problems or the distributed shop scheduling problems are still the research hotspots in this field.L-SHADE algorithm,one of the families for the differential evolution,is based on the Linear Population Size Reduction(LPSR)and success-historical parameter adaptation differential evolution.The L-SHADE algorithm has received widespread attention due to its unique update mechanism and operation mechanism,as well as easy to implement.This paper has in-depth analysis and research on the L-SHADE algorithm.The advantages and disadvantages of L-SHADE are analyzed by certain experiments and theory.Various improvements have been achieved based on the L-SHADE algorithm and to improve the search performance of the algorithm.Furthermore,the improved algorithms are used to solve the single-objective numerical optimization and the flow shop scheduling problems.The main research contents in this paper are summarized as follows.(1)It's found that L-SHADE algorithm has the problems,such as stagnation,lack of diversity in the late evolutionary period and high sensitivity to parameters after analyzing the operation mechanism of the L-SHADE algorithm.In this paper,a knowledge-based differential covariance matrix adaptation cooperative algorithm(DCMAC)is proposed to solve these problems.A weighted mutation strategy with dynamic greedy p value and covariance matrix adaptation(CMA)sampled based on differential vector are presented.Meanwhile,the knowledge acquired in the previous iteration process is adopted in the algorithm to select mutation strategy for generating the new candidate solutions in the next iteration.Meanwhile,the knowledge acquired in the previous iteration process is adopted in the algorithm to select mutation strategy for generating the new candidate solutions in the next iteration.Afterward,a parameter learning mechanism with the two sinusoidal formulas and the Cauchy distribution is introduced to balance the exploitation and exploration of DCMAC.The niching population size reduction mechanism is introduced to maintain the diversity of population and compared with the other classical population size reduction methods.The convergence property of the DCMAC is analyzed by the Markov model and the optimal combination of parameters in the DCMAC algorithm is testified by the design of experiment(DOE).Furthermore,the DCMAC is testified on the CEC2017 benchmark functions.The effectiveness and efficiency of the DCMAC are demonstrated by the experimental results in solving complex continuous problems.(2)The DCMAC algorithm is mapped to solve the No-wait Flow Shop Problem(NWFSP).DCMAC is tested on the Taillard's benchmark set.Compared with other classical algorithms,which are applied to solve the NWFSP,DCMAC has desirable convergence accuracy.The results of simulation experiments are analyzed with scientific statistical analysis methods,such as hypothesis testing.(3)In this paper,a knowledge-based discrete differential evolution(KDDE)algorithm is proposed to address the distributed permutation flow shop scheduling problem(DPFSP)with the makespan criterion.An improved NEH method is proposed to generate promising initial solutions and Taillard's acceleration method is adopted to ameliorate the operational efficiency of the KDDE.Afterward,the standard framework of DE is preserved and a new discrete mutation strategy is introduced to improve the search efficiency of the KDDE.Furthermore,four neighborhood structures,which are based on factory assignment and job sequence adjustment mechanisms,are introduced to guarantee the candidates to escape the local optimum during the search process.Meanwhile,an appropriate neighborhood search mechanism is adaptively selected through a knowledge-based optimization strategy.The optimal combinations of parameters in the KDDE algorithm are testified by the design of experiment(DOE).The comparisons with the recently published algorithms demonstrated the effectiveness and feasibility of the proposed KDDE algorithms for solving the DPFSP.