Study On Multi-Objective Hybrid Evolutionary Algorithm For Flow Shop Scheduling Problem

Job-shop Scheduling Problem locating in the core position in manufacturing system is an important part in the production management and has been a hot research in the field of scheduling. The reasonable using of the scheme can improve the production efficiency rapidly, save the cost of production and promote the efficient use of productive resources. Flow shop scheduling is the most common type in the shop scheduling and has been applied in many production areas. Because of considering multiple objectives in the actual production, the study on the multi-objective flow shop scheduling problem has more realistic significance.This paper proposed a multi-objective hybrid evolutionary algorithm. The hybrid algorithm learned the advantage of the classical algorithm Vector Evaluated Genetic Algorithm(VEGA), and offset the defect of VEGA. The unique sampling strategy makes VEGA has the ability of fast convergence and low time complexity. However, the preference of VEGA to the Pareto front edge region leads to a bad performance on the distribution. This paper adopted a new sampling strategy according to the Pareto dominating and dominated relationship-based fitness function, making up the shortage of the sampling strategy of VEGA. The hybrid algorithm combined these two kinds of sampling mechanism, making it possible to converge to the Pareto front quickly and smoothly.This paper constructed the mathematical modeling of bi-criteria flow shop scheduling problem with the objectives of minimizing makespan and total flow time. The hybrid algorithm was tested on the well-known benchmark problems and then the Taillard problems on the flow shop scheduling. At last, multi-objective hybrid evolutionary algorithm was improved by combining with a multi-objective local search for the flow shop scheduling problem with the objectives of minimizing makespan and tardiness time.The simulation experiment results show that, compared with NSGA-II and SPEA2, the hybrid evolutionary algorithm has improvement in the two aspects of convergence and distribution, and has obvious advantage in the efficiency. The simulation results of Taillard test set can be seen that the multi-objective hybrid evolutionary algorithm is more suitable for solving multi-objective flow shop scheduling problem than NSGA-II and SPEA2. The comparisons results of the old algorithm and the improved algorithm show that, the multi-objective local search improved the hybrid evolutionary algorithm on the efficacy for solving the flow shop scheduling problem with the objectives of minimizing makespan and tardiness time.Performance of the multi-objective hybrid evolutionary algorithm on performance index is better than the NSGA-II and SPEA2’s whether for solving benchmark test problems or solving multi-objective flow shop scheduling problems. The improvement of the algorithm has also achieved good results.