An Evolutionary Algorithm Integrating Multi-strategy For Static And Dynamic Hybrid Flow Shop Scheduling

Hybrid Flow shop scheduling problem(HFSSP) which has a very wide application background in the engineering field, is an important research direction of shop scheduling. Dynamic disturbance events exist universally in the actual production environment, and machine breakdown is a common one. It usually has a great influence on actual workshop production process. Therefore, researches on static HFS and dynamic HFS problem with random machine breakdown(RBHFS) have great importance in theory and practical terms. This paper focuses on these two NP-hard problems and studies the solving methods based on evolutionary algorithm. The main works are as follows:(1) Comprehensive review and analysis of static and dynamic scheduling show that intelligent optimization algorithms such as evolutionary algorithm(EA), tabu search(TS) etc., are the primary methods for these two problems.(2) For the static HFS problem, an evolutionary algorithm(V-HEA) which combines different evolutionary strategies and variable neighborhood search(VNS) is proposed to minimize the maximum completion time(makespan) of HFS. A hybrid evolutionary strategy mixing two different evolutionary thoughts is proposed to enhance the search capability based on the basic framework of evolutionary algorithms, and adopts an adaptive selection strategy to select a suitable one to evolve population; In VNS, a simplified random local search strategy based on insertion and switch neighborhood structures is proposed to improve the efficiency of algorithm. By translating the HFS to a two-stage flow shop problem, this strategy takes advantage of the optimal sequence of two-stage flow shop scheduling problem to estimate the position ranges of each job in optimal sequences of HFS, aiming to shrink the search scope of neighborhoods and improve the efficiency of algorithm. The simulation results show the effectiveness of the proposed algorithm.(3) For the dynamic RBHFS problem, a two-phase multi-objective evolutionary algorithm integrating multi-strategy(MOV-HEA) based on pre-reactive scheduling strategy is adopted to solve this problem. At the first phase, we adapt V-HEA to evolve the population as a pre-scheduling, regarding the problem as a static scheduling. At the second phase, when a machine breakdown occurs, a MOV-HEA is adopted to produce a new population of the new environment, taking the robustness and stability into account. Besides, a tabu search strategy is introduced to avoid circuitous search and improve the search capabilities. Experimental results show the effectiveness of the two-phase MOV-HEA algorithm.