The Research On The Fitness Landscape And Intelligent Optimization Algorithm For The Shop Scheduling Problem

The shop scheduling performs an essential role in the manufacturing execution system,which is the support point for improving the performance of manufacturing industry.An efficient and complete scheduling method can improve the product quality and management efficiency of the enterprise,shorten the production cycle of the product,and improve enterprise's comprehensive strength.As a typical NP-hard problem,the production scheduling problems are complex and diverse.However,most of the existing intelligent scheduling algorithms have randomness and blindness in algorithm design and parameter selection,and it is difficult to meet the complex requirements in real-life production.Therefore,the theoretical research and effective algorithm of the shop scheduling problem are still hot topics in the field.Fitness landscape and its statistical analysis have been proved useful in many domains including permutations for understanding the behavior of evolutionary algorithms applied to combinatorial optimization problems,anticipating the performance and improving the adaptation of algorithms.The fitness landscape of the no-wait flow shop scheduling problem(NWFSP)is analyzed in the thesis.The differences in the topographic features of the fitness corresponding to different neighborhood structures are studied,and the essential characteristics of NWFSP are mined to provide theoretical support for the design of evolutionary algorithms.Finally,an efficient scheduling optimization algorithm is designed according to the results of the fitness landscape analysis.The main contents and contributions of this dissertation are as follows:(1)The fitness landscape of the factoradic representation for NWFSP is studied.The encoding and decoding schemes based on the factoradic representation are constructed for mapping between job permutations and natural numbers and convert the NWFSP into a continuous problem.Two characteristics,which are position type distributions and fitness distance correlation,are proposed to analyze the fitness landscape based on the classic benchmarks.The landscape of factoradic representation is compared with six well know neighborhood structures.The fitness-distance plot and the analysis of factoradic coding theory confirm the presence of multiple big valleys structure in the fitness landscape,which makes an evolutionary algorithm can efficiently explore the search space with factoradic representation.However,the statistical results of position type distributions revealed various local optima and a high ruggedness in the factoradic representation,which result in certain evolution algorithm have the inferior ability in the exploiting phase.The results of fitness landscape analysis provide more insight on the adoption of factoradic representation for NWFSP and offered a theory support for the develop of evolutionary algorithms.(2)A factoradic representation based particle swarm optimization algorithm with population adaptation(FPAPSO)is presented for NWFSP with the objective of minimizing the makespan.Firstly,a new encoding and decoding technique based on the factoradic representation are proposed to mapping the solutions in discrete space of NWFSP to the nature numbers in continuous space.Secondly,three operators to adapt PSO to the NWFSP are designed according to the results of the fitness landscape analysis:(a)The nearest neighbor heuristic(NN)with Nawaz-Ensore-Ham(NEH)algorithm(NN+NEH operator)to generate excellent permutations for PSO to start the searching process.(b)The variable neighborhood search operator to exploit the promising area around the current best solution.(c)The population adaptation operator to enhance population diversity and avoid particles stacking into local optima.Finally,the computational results based on well-known benchmarks and performance comparisons as well as two rigorous statistical analyses demonstrate the effectiveness,efficiency and robustness of the FPAPSO algorithm for solving NWFSP.(3)Concerning the shortcomings of iterated local search algorithms for problems in continuous space,a new hybrid population-based iterated local search algorithm(HILS)is proposed for solving numerical optimization problems.The proposed hybrid method introduces both SHADE and limited-memory BFGS as the perturbation and local search strategy respectively and integrates the benefits of good exploration capability of SHADE and good local search properties of LBFGS.In order to balance the exploration and exploitation of ILS,the simulatedannealing-typed acceptance criterion is adopted.The proposed HILS was tested on the CEC2017 benchmark functions,which evaluates the performance of the proposed algorithm on solving numerical optimization problems.Results obtained show that HILS has excellent performance and better convergence speed in comparison with some of the state-of-the-art algorithms.HILS can be extended to solve F-NWFSP problems.