Water Wave Optimization Algorithm And Its Application In Shop Scheduling Problem

The no-wait flow shop scheduling problem(NWFSP)widely exists in modern manufacturing and production systems,such as steel rolling,food processing,chemical industry.NWFSP,as a constraint flow shop scheduling problem,is a typical NP-hard problem.With the increase of problem size,the NWFSP becomes more and more complicated and is difficult to solve completely.Traditional methods and the existing scheduling strategies have been unable to meet various needs in the actual productions.Therefore,whether in the scheduling research theory or the actual manufacturing production,exploring effective scheduling scheme is still a focus in the research of this field.Water Wave Optimization Algorithm(WWO)is a meta-heuristic optimization algorithm inspired by shallow water wave theory.The principle of the WWO is simple.There are few parameters to be tuned and it is easy to implement.In addition,it has special ways of exploring and exploiting solution space and powerful global search capability.In this thesis,the algorithm is improved by studying the operation principle of WWO.The performance of the algorithm is improved.The improved algorithm is applied to tackle the NWFSP.The main research contents are as follows:(1)Aiming at the problems of poor robustness,no directionality,and poor local search performance of WWO,a Discrete Water Wave Optimization Algorithm for No-wait Flow Shop Scheduling Problem(DWWO)is proposed and applied to solve the NWFSP for the first time.In DWWO,in order to improve the quality of candidate solutions in the initial population,a new initial population method was proposed.A dynamic iterated greedy algorithm with a changing removing size is employed as the propagation operator to enhance the exploration ability.In refraction operator,a crossover strategy is applied in DWWO to avoid the algorithm falling into local optimum.To improve the exploitation ability of local search,an insert-based local search scheme is utilized as breaking operator.A ruling out inferior solution operator is also introduced to improve the convergence speed.The global convergence performance of the DWWO is clarified with the Markov model to verify the stability of algorithm.The simulation results demonstrate that DWWO algorithm on the solution accuracy and robustness outperforms other compared intelligent algorithms.(2)In view of the defects of the water wave optimization algorithm framework,a water wave optimization algorithm with the Single Wave Mechanism for No-wait Flow Shop Scheduling Problem(SWWO)is proposed.In the SWWO,an improved NEH algorithm(NEH_COV)is applied to construct a high-quality initial candidate.In propagation operation,a self-adaptive block-shift operation is employed.In breaking operation,a VNS operation is utilized to explore the local optimal solution.According to the Schema Theory which presented in genetic algorithm,a crossover operation is adopted as the refraction operation.Furthermore,the simulated annealing strategy is introduced to decide whether to retain the solution propagated.Finally,the performance of the SWWO algorithm was tested with several test sets of different scales.Simulation results and statistical analysis demonstrated the effectiveness and efficiency of the SWWO algorithm in solving NWFSP.(3)The setting of the algorithm parameters is a key factor affecting the performance of the algorithm.In the DWWO algorithm,polynomial fitting is used to determine parameter values for sensitive parameters.First,analyze the factors that affect the value of the parameter.Then,execute the test set instance to fit and obtain the formula between the parameter values and the influencing factors under different parameter values.Finally,the fitting formula is taken as the value of the parameter in the algorithm.