The Estimation Of Distribution Algorithm And Its Application For The Distributed Flow-shop Scheduling Problem

In the context of economic globalization,the manufacturing industry have to design intelligent manufacturing systems to meet the requirements of the market,such as shorter product delivery time or various product types.As a part of manufacturing system,the shop scheduling problem has been a hot topic in academic and engineering application fields.Designing effective scheduling schemes to help enterprises reduce production costs and improve production efficiency has become a bottleneck problem that needs to be solved urgently in industry and academia.As a typical combinatorial optimization problem,production scheduling usually has the characteristics of complexity,multi-constraint and multi-objective.The most production scheduling problems belong to the NP(Non-deterministic Polynomial)hard problems.The task of shop scheduling is to reasonably arrange the processing order of the job on each machine under certain resource constraints(including the material,energy and power resources,equipment,capital and technology),so as to optimize single or multiple objectives.As an important branch of shop scheduling problem,the flow-shop scheduling problem widely exists in manufacturing fields such as metallurgy,machinery,electronics,and chemical industry.Compared with the traditional flow-shop scheduling problem,the no-idle flow-shop scheduling problem considers the scheduling problem in the scenario where the machine is not allowed to stop running,which is closer to the actual production scenario,and has important theoretical significance and value of practical application.Optimal scheduling strategy is an important way to improve the efficiency of manufacturing resources utilization and production task processing in manufacturing execution system.The estimation of distribution algorithm(EDA)is an optimization algorithm based on statistical principles.This algorithm is significantly different from genetic algorithm(GA),which use operations such as crossover and mutation to generate new individuals.EDA predicts the best search area through sampling and statistical learning of search space,and then produces the offspring individuals.Compared with micro-level evolution of GA,EDA adopts the macrolevel evolution based on search space,which has stronger global search ability and faster convergence speed.The concept of EDA has been developed rapidly since it was put forward.At present,many achievements have been made in relevant theoretical research and engineering application.Combining with several constraints in actual production,the distributed flow-shop scheduling problem and its extension are studied in depth.The main research contents and work of this paper are as follows:The meta-heuristics is an effective way to solve the complex optimization problems.However,the applicability of meta-heuristic is restricted in real applications due to the various characteristics of the corresponding problems.An offline learning co-evolutionary algorithm(OLCA)based on the fitness landscape analysis that introduces the Gaussian estimation of distribution algorithm(EDA)and a variant of differential evolution(DE)for enhancing the search ability,is proposed for complex continuous real-valued problems.The relationship between strategies and fitness landscapes is established by using offline learning of a random forest.The suitable strategy is determined based on the properties of the fitness landscape trained by a random forest before the beginning of the evolutionary process.The proposed OLCA is tested by using the CEC 2017 benchmark test suite and is compared with several stateof-the-art algorithms.The results show that the proposed OLCA is efficient and competitive for solving complex continuous optimization problems.In addition,the effectiveness of the proposed OLCA is also verified by using 19 IEEE CEC 2011 benchmark problems for tackling real-world problems.The distributed assembly mixed no-idle permutation flow-shop scheduling problem(DAMNIPFSP),which is a typical scenario in the modern industry including integrated circuit production,ceramic frit production,fiberglass processing,and steel-making industry,is a novel model that takes into account mixed machines with no-idle constraints and normal machines.In this paper,an estimation of distribution algorithm-based hyper-heuristic(EDA-HH)for the DAMNIPFSP is proposed.Ten simple heuristic rules as low-level operations are utilized to search the solution space.The estimation of distribution algorithm is integrated into the framework of hyper-heuristic as the high-level strategy to control the low-level heuristics sequence in the solution space.The destruction and construction procedures are conducted on products and jobs in order to enhance the exploitation competence of EDA-HH.The computational simulation is carried out and the experimental results show that the proposed EDA-HH is significantly superior to the competitors in the statistical sense.The CPLEX solver is utilized to verify the correctness of the MILP with some small instances.For the distributed assembly blocking flow-shop scheduling problem(DABFSP),this thesis designs an estimation distribution algorithm based self-learning hyper-heuristic method(SL-HH).The construction heuristic,NEH and random methods are used to cooperative initialize the population.Twelve low-level heuristic methods aiming at the problem characteristics of DABFSP are designed to search the solution space.The incremental learning method with the historical successful experience of low-level heuristics is adopted to achieve self-learning and self-adaptive of strategies.The archiving mechanism that considers the superior population of the current generation and the previous generations is introduced to update the probability model.The archiving mechanism slows down the trend of premature convergence.The simulated experiment results based on 900 standard test instances verify the effectiveness of SL-HH.