An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers
来源期刊:中南大学学报(英文版)2015年第9期
论文作者:ZHANG Su-jun GU Xing-sheng
文章页码:3471 - 3484
Key words:discrete artificial bee colony algorithm; flow shop scheduling problem with intermediate buffers; destruction and construction; tournament selection
Abstract: An effective discrete artificial bee colony(DABC) algorithm is proposed for the flow shop scheduling problem with intermediate buffers (IBFSP) in order to minimize the maximum completion time (i.e makespan). The effective combination of the insertion and swap operator is applied to producing neighborhood individual at the employed bee phase. The tournament selection is adopted to avoid falling into local optima, while, the optimized insert operator embeds in onlooker bee phase for further searching the neighborhood solution to enhance the local search ability of algorithm. The tournament selection with size 2 is again applied and a better selected solution will be performed destruction and construction of iterated greedy (IG) algorithm, and then the result replaces the worse one. Simulation results show that our algorithm has a better performance compared with the HDDE and CHS which were proposed recently. It provides the better known solutions for the makespan criterion to flow shop scheduling problem with limited buffers for the Car benchmark by Carlier and Rec benchmark by Reeves. The convergence curves show that the algorithm not only has faster convergence speed but also has better convergence value.
ZHANG Su-jun(张素君)1, 2, GU Xing-sheng(顾幸生)2
(1. School of Mechanical and Electrical Engineering,
Henan Institute of Science and Technology, Xinxiang 453003, China;
2. Key Laboratory of Advanced Control and Optimization for Chemical Process, Ministry of Education,
East China University of Science and Technology, Shanghai 200237, China)
Abstract:An effective discrete artificial bee colony(DABC) algorithm is proposed for the flow shop scheduling problem with intermediate buffers (IBFSP) in order to minimize the maximum completion time (i.e makespan). The effective combination of the insertion and swap operator is applied to producing neighborhood individual at the employed bee phase. The tournament selection is adopted to avoid falling into local optima, while, the optimized insert operator embeds in onlooker bee phase for further searching the neighborhood solution to enhance the local search ability of algorithm. The tournament selection with size 2 is again applied and a better selected solution will be performed destruction and construction of iterated greedy (IG) algorithm, and then the result replaces the worse one. Simulation results show that our algorithm has a better performance compared with the HDDE and CHS which were proposed recently. It provides the better known solutions for the makespan criterion to flow shop scheduling problem with limited buffers for the Car benchmark by Carlier and Rec benchmark by Reeves. The convergence curves show that the algorithm not only has faster convergence speed but also has better convergence value.
Key words:discrete artificial bee colony algorithm; flow shop scheduling problem with intermediate buffers; destruction and construction; tournament selection