Abstract: Compared with the traditional assembly line,the hybrid flow shop has higher flexibility and can adapt to the changing production scenarios.However,the solution complexity of its scheduling scheme is higher,which is a common problem in modern actual manufacturing systems.Aiming at the problems of high computational difficulty and low search efficiency of swarm intelligence evolutionary algorithm in solving this problem,an improved genetic algorithm with tabu search is proposed to minimize the total completion time.According to the characteristics of all workpieces in the scheduling problem with the same production process,the large number of workpieces,and the different speeds of parallel machines in each stage,the proposed algorithm adopts a single-layer coding based on the first-stage workpiece order,a decoding method considering the three-layer priority of machine selection,a variety of genetic operators and tabu search operators.It has better search performance and improves the convergence speed of the algorithm on the basis of ensuring the quality of the solution.Finally,the performance of the algorithm is evaluated by 40 instances and workshop cases,and is compared with other algorithms.The experimental results show that the proposed algorithm performs well in solving medium-scale instances,large-scale instances and processing workshop cases.The completion time of the scheduling results is shortened by 10.71% on average.The number of iterations required for the algorithm to reach the optimal solutions is reduced by 25.72%,and the running time is shortened by 10.79%.

Key words: Scheduling optimization, Improved genetic algorithm, Tabu search, Hybrid flow shop scheduling, Asynchronous parallel machine