Solution of the Distributed Permutated Flow Shop Scheduling Problems and Artificial Bee Colony Algorithm

Abstract

In this study, distributed permutation flow type scheduling problems, whose purpose function is minimization of maximum completion time, are discussed. The difference of this problem from the classical flow-type scheduling problem is that jobs are distributed across multiple factories. Artificial bee colony algorithm, based on the foraging behavior of bees in the nature, was used to solve the problem. The NEH (Nawaz Enscore Ham) intuition has been used to produce the initial solutions of the algorithm. In the phases of the algorithm (worker, observer and explorer bee phase), the displacement method is used for neighboring solutions. In this method, different jobs were obtained by changing the positions of two randomly selected jobs. The success of the algorithm on the problem has been measured in the literature using Taillard's small and large test problems. The algorithm has been compared to 14 intuitive and has presented the best results.

Keywords

• Distributed permutation flow shop scheduling; NEH heuristic; artificial bee colony algorithm

Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü

Abstract

Bu çalışmada amaç fonksiyonu minimum tamamlanma süresi olan dağıtık permütasyon akış tipi çizelgeleme problemleri ele alınmıştır. Bu problemin klasik akış tipi çizelgeleme probleminden farkı, işlerin birden fazla fabrikaya dağıtılmasıdır. Problemin çözümünde doğadaki arıların besin arama davranışını temel alan yapay arı koloni algoritması kullanılmıştır. Algoritmanın başlangıç çözümleri üretmesinde NEH sezgiselinden yararlanılmıştır. Algoritmanın evrelerinde, (işçi, gözlemci ve kâşif arı evresi) komşu çözümler için yer değiştirme metodu kullanılmıştır. Bu metotta rastgele seçilen iki işin yerleri değiştirilerek farklı iş sıraları elde edilmiştir. Algoritmanın problem üzerindeki başarısı literatürde iyi bilinin Taillard’ın küçük ve büyük boyutlu test problemleri kullanılarak gösterilmiştir. Algoritma, 14 adet sezgisel ile karşılaştırılmıştır ve en iyi sonuçları sunmuştur.

Keywords

• Dağıtık permütasyon akış tipi çizelgeleme,yapay arı kolonisi algoritması,NEH sezgiseli

References

1. [1] Ruiz, R., Q.-K. Pan, and B. Naderi, Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega, 2019. 83: p. 213-222.
2. [2] Arseven, İ. and A. Sarucan, Dağıtık Permütasyonlu Akış Tipi Çizelgeleme Problemlerinin Çözümü İçin Bir Yapay Arı Koloni Algoritması, in 6. Uluslararası GAP Mühendislik Kongresi. 2019: Şanlıurfa. p. 172-175.
3. [3] Ling-Fang, C., W. Ling, and W. Jing-jing, A Two-Stage Memetic Algorithm for Distributed No-Idle Permutation Flowshop Scheduling Problem, in 2018 37th Chinese Control Conference (CCC). 2018. p. 2278-2283.
4. [4] Pan, J.-Q., W.-Q. Zou, and J.-H. Duan, A Discrete Artificial Bee Colony for Distributed Permutation Flowshop Scheduling Problem with Total Flow Time Minimization, in 2018 37th Chinese Control Conference (CCC). 2018: China. p. 8379-8383.
5. [5] Fernandez-Viagas, V., P. Perez-Gonzalez, and J.M. Framinan, The distributed permutation flow shop to minimise the total flowtime. Computers & Industrial Engineering, 2018. 118: p. 464-477.
6. [6] Wang, K., Y. Huang, and H. Qin, A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown. Journal of the Operational Research Society, 2017. 67(1): p. 68-82.
7. [7] Wang, K., et al., Variable neighborhood based memetic algorithm for Just-in-Time distributed assembly permutation flowshop scheduling, in 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC). 2017. p. 3700-3704.
8. [8] Deng, J. and L. Wang, A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem. Swarm and Evolutionary Computation, 2017. 32: p. 121-131.

9. [9] Shao, W., D. Pi, and Z. Shao, Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms. Knowledge-Based Systems, 2017. 137: p. 163-181.
10. [10] Ying, K.-C., et al., Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems. Computers & Industrial Engineering, 2017. 110: p. 413-423.
11. [11] Duan, W., et al., EDA based probabilistic Memetic Algorithm for distributed blocking permutation flowshop scheduling with sequence dependent setup time, in 2017 IEEE Congress on Evolutionary Computation (CEC). 2017, IEEE. p. 992-999.
12. [12] Bargaoui, H., O. Belkahla Driss, and K. Ghédira, A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion. Computers & Industrial Engineering, 2017. 111: p. 239-250.
13. [13] Li, Z., et al., The distributed permutation flowshop scheduling problem with different transport timetables and loading capacities, in 2016 IEEE Congress on Evolutionary Computation (CEC). 2016, IEEE. p. 2433-2437.
14. [14] Lin, S.-W. and K.-C. Ying, Minimizing makespan for solving the distributed no-wait flowshop scheduling problem. Computers & Industrial Engineering, 2016. 99: p. 202-209.
15. [15] Deng, J., et al. An Improved Harmony Search Algorithm for the Distributed Two Machine Flow-Shop Scheduling Problem. 2016. Berlin, Heidelberg: Springer Berlin Heidelberg.
16. [16] Deng, J., et al., A Competitive Memetic Algorithm for Carbon-Efficient Scheduling of Distributed Flow-Shop, in Intelligent Computing Theories and Application. 2016. p. 476-488.
17. [17] Lin, J. and S. Zhang, An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem. Computers & Industrial Engineering, 2016. 97: p. 128-136.
18. [18] Wang, J., L. Wang, and J. Shen, A hybrid discrete cuckoo search for distributed permutation flowshop scheduling problem, in 2016 IEEE Congress on Evolutionary Computation (CEC). 2016. p. 2240-2246.
19. [19] Rifai, A.P., H.-T. Nguyen, and S.Z.M. Dawal, Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling. Applied Soft Computing, 2016. 40: p. 42-57.
20. [20] Naderi, B. and R. Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational Research, 2014. 239(2): p. 323-334.
21. [21] Hatami, S., R. Ruiz, and C. Andrés-Romano, The Distributed Assembly Permutation Flowshop Scheduling Problem. International Journal of Production Research, 2013. 51(17): p. 5292-5308.
22. [22] Lin, S.-W., K.-C. Ying, and C.-Y. Huang, Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. International Journal of Production Research, 2013. 51(16): p. 5029-5038.
23. [23] Wang, S.-y., et al., An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. International Journal of Production Economics, 2013. 145(1): p. 387-396.
24. [24] Gao, J., R. Chen, and W. Deng, An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 2013. 51(3): p. 641-651.
25. [25] Gao, J. and R. Chen, An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems. Scientific Research and Essays, 2011. 6: p. 3094-3100.
26. [26] Gao, J. and R. Chen, A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem. International Journal of Computational Intelligence Systems, 2011. 4(4): p. 497-508.
27. [27] Liu, H. and L. Gao, A Discrete Electromagnetism-Like Mechanism Algorithm for Solving Distributed Permutation Flowshop Scheduling Problem, in 2010 International Conference on Manufacturing Automation. 2010. p. 156-163.
28. [28] Naderi, B. and R. Ruiz, The distributed permutation flowshop scheduling problem. Computers & Operations Research, 2010. 37(4): p. 754-768.
29. [29] Gong, D., Y. Han, and J. Sun, A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems. Knowledge-Based Systems, 2018. 148: p. 115-130.
30. [30] Ribas, I., R. Companys, and X. Tort-Martorell, An efficient Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with total flowtime minimization. Expert Systems with Applications, 2015. 42(15-16): p. 6155-6167.
31. [31] Zhang, S.-j. and X.-s. Gu, An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers. Journal of Central South University, 2015. 22(9): p. 3471-3484.
32. [32] Vijaychakaravarthy, G., S. Marimuthu, and A. Naveen Sait, Comparison of Improved Sheep Flock Heredity Algorithm and Artificial Bee Colony Algorithm for lot Streaming in m-Machine Flow Shop Scheduling. Arabian Journal for Science and Engineering, 2014. 39(5): p. 4285-4300.
33. [33] Tasgetiren, M.F., et al., A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Applied Mathematical Modelling, 2013. 37(10-11): p. 6758-6779.
34. [34] Cui, Z. and X. Gu. An Improved Discrete Artificial Bee Colony Algorithm for Hybrid Flow Shop Problems. in Intelligent Computing for Sustainable Energy and Environment. 2013. Berlin, Heidelberg: Springer Berlin Heidelberg.
35. [35] Liu, Y.-F. and S.-Y. Liu, A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing, 2013. 13(3): p. 1459-1463.
36. [36] Deng, G., Z. Xu, and X. Gu, A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling. Chinese Journal of Chemical Engineering, 2012. 20(6): p. 1067-1073.
37. [37] Li, X. and M. Yin, A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem. Scientia Iranica, 2012. 19(6): p. 1921-1935.
38. [38] Han, Y.-Y., et al., Effective hybrid discrete artificial bee colony algorithms for the total flowtime minimization in the blocking flowshop problem. The International Journal of Advanced Manufacturing Technology, 2012. 67(1-4): p. 397-414.
39. [39] Pan, Q.-K., et al., A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 2011. 181(12): p. 2455-2468.
40. [40] Tasgetiren, M.F., et al., A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops. Information Sciences, 2011. 181(16): p. 3459-3475.
41. [41] Han, Y.-Y., et al., Minimizing the Total Flowtime Flowshop with Blocking Using a Discrete Artificial Bee Colony. Vol. 6839. 2011, 7th international conference, ICIC 2011: 0302-9743.
42. [42] Han, Y.-Y., et al., An improved artificial bee colony algorithm for the blocking flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 2011. 60(9-12): p. 1149-1159.
43. [43] Karaboga, D. and B. Basturk, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 2007. 39(3): p. 459-471.
44. [44] Tosun, Ö., Yapay Arı Kolonisi Algoritması ve Permütasyon Akış Tipi Çizelgeleme Problemine Uygulanması. Akdeniz Üniversitesi Sosyal Bilimler Enstitüsü, 2012: p. 1-111.
45. [45] Kalczynski, P. and J. Kamburowski, On the NEH heuristic for minimizing the makespan in permutation flow shops☆. Omega, 2007. 35(1): p. 53-60.