A New Hybird Distribution Estimation Algorithm For Flow-shop Scheduling Problem

Nowadays, as a super manufacture industry country and the world manufacturing center, our country’s manufacturing industry is immature. Compared with western developed countries, there are many drawbacks such as wasting of resources, working long hours, and the low production efficiency and so on. How to improve the production efficiency and collocate the resources reasonably has attracted more and more attention. The research of Shop Scheduling focus in the manufacturing system has received widespread attention and has made great progress in recent years.Flow shop scheduling problem is a typical NP-hard problem. And at the same time, FSP also is a common problem in shop scheduling problem. Therefore it is highly theoretical and practically valuable to propose an effective solution for the problem of the FSP algorithms. In this paper, a hybrid Estimation of Distribution Algorithms is proposed to solve permutation flow shop scheduling problem and No-wait flow shop scheduling problem. Estimation of Distribution Algorithms is developed on the basis of Genetic Algorithm. EDA is widely used in in the research of NP-Hard problems. The algorithm is different from genetic algorithm which has complex operators such as the crossover and mutation. In the EDA, a probability model of the most promising area is built by statistical information based on searching experience, and then the probability model is used for sampling to generate the new individuals.According to the characteristics of the flow shop scheduling problem(FSP), this paper proposes a hybrid distribution of estimation algorithm based on the work piece machining probability of position and connection. The hybrid algorithm is the combination of the location probability and connection probability together. As a result, the population evolution trend is more reasonable. To improve the searching quality, the heuristic methods are presented to improve the quality of initial solution and optimize the neighborhood search strategy. In addition a new neighborhood search strategy and the second element optimization method is presented to enhance the quality of the local optimal solution. At the same time, the mutation and limit are proposed to enhance the exploitation ability. The simulation results and comparisons based on benchmarks validate the efficiency of the proposed algorithm.