A Hybrid Artificial Bee Colony Algorithm for Multi-objective Flexible Job-Shop Scheduling Problem

Guan-Jun Meng ； Xin-Hua Chen ； Da-Chun Yang ； Wei Zhang

《電腦學刊》 31卷5期 (2020/10) Pp. 224-235

https://doi.org/10.3966/199115992020103105017

摘要

Flexible job shop scheduling (FJSP) is an extension of job shop scheduling problem. The traditional optimization algorithm can get better results when solving the single objective FJSP, but it is often inefficient and difficult to obtain the optimal solution in the face of multi-objective FJSP. Using artificial bee colony (ABC) algorithm with fast convergence and good global search capability and tabu search (TS) algorithm with strong local search ability, this paper designs a hybrid improved artificial bee colony (TS-ABC) algorithm for solving multi-objective FJSP. In order to evaluate the solution better, a fitness function based on Pareto rank and crowding distance is proposed. In the updating of the solution, this paper adopts multiple search mechanisms, which uses improved precedence operation crossover (IPOX) and Multipoint Preservative Crossover (MPX) in the employed bee phase and performs the exchange operation and mutation operation in the onlooker bee phase. The method can improve the performance of the search well. The combination of tabu search and improved artificial bee colony algorithm effectively improves the probability of obtaining the optimal solution. In the end, a series of experiments are carried out to solve the problem of the multi-objective FJSP by TS-ABC algorithm.

關鍵字

artificial bee colony algorithm ； flexible job-shop scheduling problem ； multi-objective Optimization ； tabu search