An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers

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.

Keywords

discrete artificial bee colony algorithm / flow shop scheduling problem with intermediate buffers / destruction and construction / tournament selection

References

[1] NawazM, EnscoreE, HamI. A heuristic algorithm for the m-machine n-job flowshop sequencing problem [J]. Omega, 1983, 11(1): 91-95

[2] PapadimitriouC H, KanellakisP C. Flowshop scheduling with limited temporary storage [J]. Journal of the ACM (JACM), 1980, 27(3): 533-549

[3] LeistenR. Flow shop sequencing problems with limited buffer storage [J]. The International Journal of Production Research, 1990, 28(11): 2085-2100

[4] RuizR, StÜTzleT. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem [J]. European Journal of Operational Research, 2007, 177(3): 2033-2049

[5] IyerS K, SaxenaB. Improved genetic algorithm for the permutation flowshop scheduling problem [J]. Computers & Operations Research, 2004, 31(4): 593-606

[6] PanQ K, TasgetirenM F, LiangY C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem [J]. Computers & Industrial Engineering, 2008, 55(4): 795-816

[7] TsengL-y, LinY-t. A hybrid genetic local search algorithm for the permutation flowshop scheduling problem [J]. European Journal of Operational Research, 2009, 198(1): 84-92

[8] TasgetirenM F, PanQ K, SuganthanP N, ChenA H L. A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops [J]. Information Sciences, 2011, 181(16): 3459-3475

[9] LiX-t, YinM-h. A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem [J]. Scientia Iranica, 2012, 19(6): 1921-1935

[10] RamananG V, RajendranC. Scheduling in kanban-controlled flowshops to minimise the makespan of containers [J]. The International Journal of Advanced Manufacturing Technology, 2003, 21(5): 348-354

[11] RonconiD P. A note on constructive heuristics for the flowshop problem with blocking [J]. International Journal of Production Economics, 2004, 87(1): 39-48

[12] FahmyS A, ElmekkawyT Y, BalakrishnanS. Mathematical formulations for scheduling in manufacturing cells with limited capacity buffers [J]. International Journal of Operational Research, 2010, 7(4): 463-486

[13] SawikT. Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers [J]. Mathematical and Computer Modeling, 2000, 31(13): 39-52

[14] SawikT. An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers [J]. Mathematical and Computer Modeling, 2002, 36(4): 461-471

[15] WengM X. Simulation in production scheduling: scheduling flow-shops with limited buffer spaces [C]. Proceedings of the 32nd Conference on Winter Simulation, 2000San Diego, CASociety for Computer Simulation International1359-1363

[16] NowickiE. The permutation flow shop with buffers: A tabu search approach [J]. European Journal of Operational Research, 1999, 116(1): 205-219

[17] WangX-p, TangL-x. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers [J]. Computers & Operations Research, 2009, 36(3): 907-918

[18] WangL, ZhangL, ZhengD-z. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers [J]. Computers & Operations Research, 2006, 33(10): 2960-2971

[19] LiuB, WangL, JinY-h. An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers [J]. Computers & Operations Research, 2008, 35(9): 2791-2806

[20] HsiehY C, YouP S, LiouC D. A note of using effective immune based approach for the flow shop scheduling with buffers [J]. Applied Mathematics and Computation, 2009, 215(5): 1984-1989

[21] PanQ-k, WangL, GaoL. A chaotic harmony search algorithm for the flow shop scheduling problem with limited buffers [J]. Applied Soft Computing, 2011, 11(8): 5270-5280

[22] PanQ K, TasgetirenM F, LiangY C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem [J]. Computers & Industrial Engineering, 2008, 55(4): 795-816

[23] QianB, WangL, HuangD-x, WangX. An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers [J]. International Journal of Production Research, 2009, 47(1): 1-24

[24] QianB, WangL, HuangD-x, WangW-l, WangX. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers [J]. Computers & Operations Research, 2009, 36(1): 209-233

[25] HuR, WangL, QianB, HuangF-z. Differential evolution method for stochastic flow shop scheduling with limited buffers [C]. IEEE World Congress on Computational Intelligence, Evolutionary Computation, 2008Hong KongIEEE Computation Intelligence Society1295-1301

[26] WangL, PanQ-k, SuganthanP N, WangW-h, WangY-m. A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems [J]. Computers & Operations Research, 2010, 37(3): 509-520

[27] PanQ-k, WangL, GaoL, LiW D. An effective hybrid discrete differential evolution algorithm for the flow shop scheduling with intermediate buffers [J]. Information Sciences, 2011, 181(3): 668-685

[28] KarabogaDAn idea based on honey bee swarm for numerical optimization [R], 2005

[29] LiuY-f, LiuS-y. A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem [J]. Applied Soft Computing, 2013, 13(3): 1459-1463

[30] TasgetirenM F, PanQ K, SuganthanP N, OnerA. A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion [J]. Applied Mathematical Modeling, 2013, 37(10): 6758-6779

[31] PanQ K, TasgetirenM F, SuganthanP N, ChuaT J. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem [J]. Information Sciences, 2011, 181(12): 2455-2468

[32] DengG-l, XuZ-h, GuX-s. A discrete artificial bee colony algorithm for minimizing the total flow time in the block flow shop scheduling [J]. Chinese Journal of Chemical Engineering, 2012, 20(6): 1067-1073

[33] HanY-y, PanQ-k, LiJ-q, SangH-y. An improved artificial bee colony algorithm for the blocking flowshop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2012, 60: 1149-1159

[34] PanQ-k, WangL, LiJ Q, LiJ-q. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization [J]. Omega, 2014, 45(2): 42-56

[35] DongX-y, HuangH-k, ChenP. An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion [J]. Computers & Operations Research, 2009, 36(5): 1664-1669

[36] RuizR, MarotoC. A comprehensive review and evaluation of permutation flowshop heuristics [J]. European Journal of Operational Research, 2005, 165(2): 479-494

[37] ZhengX-l, WangL, WangS-y. A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem [J]. Control Theory & Applications, 2014, 31(5): 159-164

[38] CarlierJ. Ordonnancements a contraintes disjonctives [J]. Rairo-Operations Research-Recherche Opérationnelle, 1978, 12(4): 333-350

[39] ReevesC R. A genetic algorithm for flowshop sequencing [J]. Computers & Operations Research, 1995, 22(1): 5-13