The Multi-strategy Water Wave Optimization Algorithm And Its Application For The Shop Scheduling Problem

Shop scheduling is an important portion of the manufacturing execution system(MES)and its efficiency is the core and key to the efficient operation of the intelligent manufacturing system.With the development of globalization economy,the market presents the superior requirements for the manufacturing system.For instance,online response to customer order,dynamic adjust the production scheduling,tacking disrupt events and mulit-task allocation.The scheduling strategy and control algorithms do not satisfied the requiremens.The scheduling system has become the bottlemneck and key issue for the manufacturing system.Therefore,the scheduling model,strategy and optimization algorithms are of great improtance for the production planning and scheduling.The shop scheduling,which is to satisfy the changing market requirements,has switched from the single-shop model to multi-shop model and formed a distributed shop production scheduling model.Reasonable and efficient scheduling methods and optimization techniques have become the core means to improve productivity effect and economic benefits during the process of the production system.Various shop scheduling problems have been proved to be NPhard problems.Due to the diversity and complexity of shop scheduling problems,traditional optimization methods are not applied to obtain the optimal solution through efficient search.Therefore,various meta-heuristic methods has become the mainstream method for solving shop scheduling problems.The theoretical research and effective optimization methods for shop scheduling problems still have significant research significance and application value.According to the water wave theory,the water wave optimization algorithm(WWO),which is inspired by the physical phenomenon,is proposed.The framework of the WWO is simple and easy to implement.The WWO has been drawn various attention owing to the unique operation mechanism and effective global serach ability.This paper has done certain reseaches for the WWO algorithm.According to analyze the operation mechanism,advantages and disadvantages of the WWO algorithm,the three improved algorithms based on the framwork of the WWO algorithm are proposed to enhance the local search ability of the WWO algorithm,balance the exploration and exploitation,and promote the search performance of algorithms.The performace of the improved algorithms are verified by tested on the continuous optimization problem and shop scheduling problem.The main research contents and work of this paper are as follows.(1)For the disadvantages of the WWO,such as weak local search ability and easy to fall into the local optimal,an improved water wave optimisation algorithm enhanced by the covariance matrix adaptation evolution strategy(CMA-ES)and opposition-based learning(EWWO)is proposed to solve the single-objective real parameter optimization problem.First,the random opposition-based learning(ROBL)mechanism is introduced to generate the initial population with high quality.Second,a new modified operation is embedded into propagation operation to balance the global exploration and the local exploitation.Finally,the refraction operation is replaced by the CMA-ES to further strengthen the local exploitation.Furthermore,the diversity of the population is maintained in the evolution process by using a crossover operator and the design of experiments method(DOE)is applied to calibrate the parameters.The experiment results based on CEC 2017 benchmarks indicate that the EWWO outperforms the state-of-the-art variant algorithms of the WWO and the standard WWO.(2)For the no-idle flowshop scheduling problem(NIFSP),a hybrid discrete water wave optimization algorithm,named HWWO,is designed to solve the NIFSP with total tardiness criterion.In order to improve the quality of a population,an initialize method based on a new priority rule combined with the modified NEH method is proposed to generate a population.In the propagation phase,a self-adaption selection neighborhood search structure is introduced to amplify the search range of waves and balance the exploration and exploitation ability of the HWWO.Afterwards,a variable neighborhood search is adopted to strengthen the local search and maintain the diversity of the population in the breaking phase.In the refraction operation,a perturbation sequence is generated and combined with the local optimal solution found by the breaking operation,in order to generate a new solution,and prevent the algorithm from becoming trapped in the local optimum.Furthermore,the control parameters and time complexity of the HWWO algorithm are analyzed.The experimental results and comparisons with the other state-of-the-art algorithms evaluated on Taillard's and Ruiz's benchmark sets reveal that the effectiveness and efficiency of the HWWO outperformed the compared algorithms for solving the NIFSP.(3)A cooperative water wave optimization algorithm based on the three-stage variable neighborhood search(CWWO)is designed to solve the distributed assembly no-idle flowshop scheduling problem(DANIFSP)with the goal of minimizing the maximum assembly completion time.In the CWWO,the initial population is generated by random sequences and the current optimal solution as the historical optimal solution is recorded.In the propagation operation phase,reinforcement learning -7)0)(69)4)9)2)controlled by the wavelength is introduced to balance the global search ability and local search ability.In the wave breaking operation phase,a path-relinking(PR)mechanism is used to enhance the exploitation and improve the convergence speed of the algorithm.The 0)(84)9)-9)(84)9)is used in the refraction operation phase to control the diversity of the population and maintain local search.Finally,the simulating annealing is adopted to determine whether the neighborhood solution is received.Additionally,the effective parameters of the CWWO and the effects of the three operations on the performance of the algorithm are analyzed.The benchmark sets proposed for the distributed assembly flow shop scheduling problem verifies that the CWWO is significantly better than other comparison algorithms.