Research On Complex Shop Scheduling Problem Based On EDA Intelligent Optimization Algorithm

The complex production scheduling systems often encounters some complexities,such as large-scale,strong constraint,non-linear,multi-objective,uncertain and and NP-hard,etc.The study on scheduling theory and efficient algorithms is always a hot topic in academic and engineering fields.The flow shop production scheduling problem is a typical complex combinatorial optimization problem with wide engineering background.Research on the flow shop production scheduling in terms of theory and methodology has important academic significance and potential application value.As a focus in intelligent optimization,estimation of distribution algorithms(EDAs)are good at global search according to the probabilistic model and statistical learning.Aim at two typical flow shop manufacturing scheduling problems,this thesis analyzes the problem characteristics,builds proper probabilistic models,and develops effective search operators,and then proposes the EDA-based optimization algorithms to provide theoretical and algorithmic support for flexible production scheduling.After completely reviewing and deeply studying the two-complex flow shop production scheduling problems and the EDAs,this dissertation achieves the following main results:Firstly,an effective hybrid estimation of distribution algorithm which utilized the speed-up evaluation method and Insert based problem-dependent local search is proposed for the no-wait flow-shop scheduling problem with sequence dependent setup times and release dates to minimize the total completion time.And simulation results and comparisons verify the effectiveness,efficiency and robustness of our proposed algorithms.Secondly,an innovative three,dimensional matrix cube based estimation of distribution algorithm(MCEDA)is first proposed to minimize the total earliness and tardiness of the no-wait flow shop scheduling problem with sequence dependent setup times and release dates,which can learn the information of jobs' order and building blocks from the promising solutions to guild the global direction.A fast-local search with the speed-up scanning method and two search strategies is developed to execute exploitation from the promising sub-regions.Extensive computational experiments and analysis based on benchmarks demonstrate the effectiveness,efficiency and robustness of our proposed algorithms,and the effects of key operations and parameters are investigated as well.Thirdly,the permutation based mathematical model for distributed two stage assembly permutation flow shop scheduling problem(DTSAPFSP)is proposed and the effective encoding and decoding methods are given.The MCEDA is also presented for DTSAPFSP.In order to accelerate the evolution direction toward the global optimal regions,the Insert and Interchange local search is proposed by combining the critical-path based search method and the variable neighborhood search.Computer-based simulation and comparisons based on the international benchmarks show that the effectiveness,efficiency,and robustness of the proposed MCEDA-based algorithms.