Solution of Permutation Flow Scheduling Problem with Grenade Explosion Method

Year 2023, Volume: 10 Issue: 2, 491 - 510, 30.06.2023

Celal Özkale Kasım Baynal Turgay Öztürk

https://doi.org/10.47097/piar.1273593

Abstract

For the efficient use of resources in production, the studies should be scheduled in the best way. The permutation flowshop scheduling problem (PFSP), which has many applications in real life, has been attracting the attention of researchers for more than half a century. Grenade Explosion Method (GEM) is an evolutionary algorithm proposed by Ahrari et al., inspired by the explosions of grenades. In this study, GEM was adapted to solve permutation flowshop scheduling problems. Then, the effect of the radius of the agent region, which distinguishes the method from other metaheuristics, on the method performance was analysed and its performance on the test problems presented by Taillard was examined regards the makespan criterion. Finally, it has been observed that GEM can reach acceptable results in reasonable time and can be used to solve these problems.

Keywords

Permutation flowshop scheduling problem, Grenade Explosion Method, Metaheuristics

Permütasyon Akış Tipi Çizelgeleme Probleminin El Bombası Patlatma Metodu ile Çözümü

Abstract

Üretimde kaynakların verimli kullanımı için işlerin en iyi şekilde çizelgelenmesi gerekmektedir. Gerçek hayatta çok sayıda uygulaması bulunan permütasyon akış tipi çizelgeleme problemi (PATÇP) yarım asırdan uzun süredir araştırmacıların ilgisini çekmektedir. El Bombası Patlatma Metodu (EBPM) Ahrari ve arkadaşları tarafından el bombalarının patlamalarından esinlenerek geliştirilmiş evrimsel bir algoritmadır. Bu çalışmada EBPM, permütasyon akış tipi çizelgeleme problemlerinin çözümü için uyarlanmıştır. Daha sonra metodu diğer metasezgisellerden ayıran özellik olan ajan bölgesi yarıçapının metot performansına etkisi araştırılmış ve metodun maksimum tamamlanma zamanı performans ölçütüne göre Taillard tarafından geliştirilmiş olan test problemleri üzerindeki performansları incelenmiştir. Sonuç olarak EBPM’nin makul sürelerde kabul edilebilir sonuçlara ulaşabildiği ve PATÇP’lerin çözümünde kullanılabileceği görülmüştür.

Keywords

Permütasyon akış tipi çizelgeleme problemi, El Bombası Patlatma Metodu, Metasezgisel Yöntemler

References

• Aguiar, H., & Junior, O. (2015). Evolutionary Global Optimization, Manifolds and Applications. Studies in Systems, Decision and Control, 43, 17-18.
• Ahmadizar, F. (2012). A new ant colony algorithm for makespan minimization in permutation flow shops. Computers and Industrial Engineering, 63(2), 355-361.
• Ahrari, , Panahi, M. S., & Atai, A. (2009). GEM : A novel evolutionary optimization method with improved neighborhood search. Applied Mathematics and Computation, 210(2), 376-386.
• Ahrari, A., & Atai, A. (2010). Grenade Explosion Method - A novel tool for optimization of multimodal functions. Applied Soft Computing Journal, 10(4), 1132-1140.
• Ahrari, A., Saadatmand, M., Shariat-Panahi, M., & Atai, A. (2010). On the limitations of classical benchmark functions for evaluating robustness of evolutionary algorithms. Applied Mathematics and Computation, 215(9), 3222-3229.
• Ali, A., Gajpal, Y., & Elmekkawy, T. (2021). Distributed permutation flowshop scheduling problem with total completion time objective. OPSEARCH, 58(2), 425-447.
• Bacha, S. Z., Benatchba, K., & Tayeb, F. B.-S. (2022). Adaptive search space to generate a per-instance genetical gorithm for the permutation flow shop problem. Applied Soft Computing(124), 1-13.
• Baker, K., & Trietsch, D. (2009). Principles of Sequencing and Scheduling. John Wiley & Sons Inc.
• Bean, J. (1994). Genetic Algorithms and Random Keys for Sequencing and Optimization. HomeORSA Journal on Computing, 6(2), 154-160.
• Bouchekara, H., Chaib, ·., & Abido, ·. (2016). Multiobjective optimal power flow using a fuzzy based grenade explosion method. Energy Systems, 7, 699-721.
• Campbell, H., Dudek, R., & Smith, M. (1970, 6). A Heuristic Algorithm for the n Job, m Machine Sequencing Problem. Management Science, 16(10), 630-637.
• Ceri̇t, B., Onural, A. Ş., ve Yilmaz, B. (2005). Montaj ve işleme alt sistemlerini içeren bir esnek üretim sisteminin iki aşamalı çizelgelenmesi. Teknoloji, 8, 147-155.
• Cura, T. (2006). Modern Meta Sezgisel Teknikler ve Uygulamaları. İstanbul: Papatya Yayınları.
• Çiçekli, U. G., ve Bozkurt, s. (2016). Permütasyon Akış Tipi Çizelgeleme Probleminin Dağınık Arama İle Optimizasyonu. Ege Akademik Bakış, 16(Özel Sayı), 31-40.
• Dannenbring, D. (1977). An Evaluation of Flow Shop Sequencing Heuristics. Management Science, 23(11), 1149-1259.
• Dasgupta, P., & Das, S. (2015). A discrete inter-species cuckoo search for flowshop scheduling problems. Computers and Operations Research, 60, 111-120.
• Daya, M., & Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, 109(1), 88-95.
• Engin, O., ve Fıglalı, A. (2002). Genetik Algoritmalarla akış tipi çizelgelemede üreme yöntemi optimizasyonu. İtü dergisi, 1(1), 1-7.
• Famila, S., Jawahar, A., Sariga, A., & Shankar, K. (2020). Improved artificial bee colony optimization based clustering algorithm for SMART sensor environments. Peer-to-Peer Networking and Applications, 13(4), 1071-1079.
• Ghanavati, M., Wong, R., Fong, S., & Gholamian, M. (2016). Extending the grenade explosion approach for effective clustering. The 10th International Conference on Digital Information Management, ICDIM 2015, 28-35
• Grabowski, J., & Wodecki, M. (2004). A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers and Operations Research, 31(11), 1891-1909.
• Gupta, J. (1971). A Functional Heuristic Algorithm for the Flowshop Scheduling Problem. Journal of the Operational Research Society, 22, 39-47.
• Ho, J., & Chang, Y. (1991). A new heuristic for the n-job, M-machine flow-shop problem. European Journal of Operational Research, 52(2), 194-202.
• Ishibuchi, H., Misaki, S., & Tanaka, H. (1995). Modified simulated annealing algorithms for the flow shop sequencing problem. European Journal of Operational Research, 81(2), 388-398.
• İşler, M. C., Toklu, B., Çelik, V., ve Ersöz, S. (2009). Öğrenme Etkili Tam Zamanında Çizelgeleme Problemi ve KOBİ’de Uygulama. International Journal of Engineering Research and Development, 1(2), 29-33.
• Karaboğa, D. (2002). Yapay Zeka Optimizasyon Algoritmaları. Ankara: Atlas Yayın Dağıtım.
• Kaya, S., Karaçizmeli, İ. H., Aydilek, İ. B., Tenekeci, M. E., ve Gümüşçü, A. (2020). Akış tipi çizelgeme problemlerinin hibrit ateşböceği ve parçacık sürü optimizasyonu algoritmasıyla çözümünde başlangıç popülasyonlarının etkileri. Pamukkale Universitesi Mühendislik Bilimleri Dergisi, 26(1), 140-149.
• Khavari, F., Naseri, V., & Naghshbandy, A. (2011). Optimal PMUs placement for power system observability using grenade explosion algorithm. International Review of Electrical Engineering, 6(3), 1332-1338.
• Kurnaz, M. S., ve Kart, Ö. (2010). İş Akış Çizelgeleme Problemi Üzerinde NEH, FRB3 veFRB4 Sezgisellerinin Karşılaştırılması. Akademik Bilişim’10 - XII. Akademik Bilişim Konferansı Bildirileri (s. 625-630). Muğla: Muğla Üniversitesi.
• Küpeli, İ., Sarucan, A., ve Küpeli, A. (2020). Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü (Cilt 7). TUBITAK.
• Li, X., & Yin, M. (2012). A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem. Scientia Iranica, 19(6), 1921-1935.
• Li, Y., Pan, Q., Gao, K., Tasgetiren, M., Zhang, B., & Li, J. (2021). A green scheduling algorithm for the distributed flowshop problem. Applied Soft Computing, 109;1-17.
• Liu, B., Wang, L., & Jin, Y.-H. (2007). An effective PSO-based memetic algorithm for flow shop scheduling. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society, 37(1), 18-27.
• Liu, Y., & Liu, S. (2013). A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem. Applied Soft Computing Journal, 13(3), 1459-1463.
• Liu, Y., Yin, M., & Gu, W. (2014). An effective differential evolution algorithm for permutation flow shop scheduling problem. Applied Mathematics and Computation, 248, 143-159.
• Marouani, Ι., Boudjemline, A., Guesmi, T., & Abdallah, H. (2018). A Modified Artificial Bee Colony for the Non-Smooth Dynamic Economic/Environmental Dispatch. Engineering, Technology & Applied Science Research, 8(5), 3321-3328.
• Mishra, S., & Ray, P. (2016). Power Quality Improvement Using Photovoltaic Fed DSTATCOM Based on JAYA Optimization. IEEE Transactions on Sustainable Energy, 7(4), 1672-1680.
• Mishra, S., Ray, P., & Dash, S. (2016). A TLBO optimized photovoltaic fed DSTATCOM for power quality improvement. 1st IEEE International Conference on Power Electronics, Intelligent Control and Energy Systems, ICPEICES 2016. Institute of Electrical and Electronics Engineers Inc.
• Mouwafi, M., El-Sehiemy, R., Abou El-Ela, A., & Kinawy, A. (2016). Optimal placement of phasor measurement units with minimum availability of measuring channels in smart power systems. Electric Power Systems Research, 141, 421-431.
• Nawaz, M., Enscore, E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
• Nearchou, A. (2004). A novel metaheuristic approach for the flow shop scheduling problem. Engineering Applications of Artificial Intelligence, 17(3), 289-300.
• Onwubolu, G., & Davendra, D. (2006). Scheduling flow shops using differential evolution algorithm. European Journal of Operational Research, 171(2), 674-692.
• Palamutçuoğlu, B. (2022). Üretim Çizelgeleme Problemlerinde Yapay Zekâ Uygulamaları: Bir Derleme Çalışması. 3. Sektör Sosyal Ekonomi Dergisi, 57(4), 3360-3379.
• Pallantla, M., & Singh, A. (2012). Grenade explosion method for maximum weight clique problem. Communications in Computer and Information Science. 306 CCIS, s. 20-27. Springer, Berlin, Heidelberg.
• Palmer, D. (1965). Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time—A Quick Method of Obtaining a Near Optimum. Operational Research Quarterly, 16(1), 101-107.
• Pan, Q., Tasgetiren, M., & Liang, Y. (2008a). A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers and Industrial Engineering, 55(4), 795-816.
• Pan, Q., Fatih Tasgetiren, M., & Liang, Y. (2008b). A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers and Operations Research, 35(9), 2807-2839.
• Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426-438.
• Rakhade, R., Patil, N., & Panchbhai, M. (2017). Application of Grenade Explosion Method Optimization for Plate-Fin Type Heat Exchanger (PFHE). IOSR Journal of Mechanical and Civil Engineering (IOSR-JMCE) e-ISSN, 17-18.
• Rao, R., & More, K. (2015). Optimal design of the heat pipe using TLBO (teaching-learning-based optimization) algorithm. Energy, 80, 535-544.
• Rao, R., Savsani, V., & Vakharia, D. (2012). Teaching-Learning-Based Optimization: An optimization method for continuous non-linear large scale problems. Information Sciences, 183(1), 1-15.
• Reevest, C. (1995). A Genetıc Algorıthm For Flowshop Sequencıng. Computers Ops Res, 22(1), 5-13.
• Ruiz, R., Maroto, C., & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 34(5), 461-476.
• Salhi, A., Salhi, A., Naimi, D., & Bouktir, T. (2016). Optimal power flow resolution using artificial bee colony algorithm based grenade explosion method. J. Electrical Systems, 12(4), 734-756.
• Surender Reddy. (2016). Congestion Management Using Multi-Objective Grenade Explosion Method. Wseas Transactions On Power Systems, 11, 81-89.
• Şevkli, M., ve Yenisey, M. M. (2006). Atölye tipi çizelgeleme problemleri için parçacık sürü optimizasyonu yöntemi. İTÜ Dergisi, 5(2), 58-68.
• Taillard, E. (1993). Benchmarks For Basic Scheduling Problems. URL:http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html, (Erişim: 21.03.2023).
• Tarłowski, D. (2014). Nonautonomous stochastic search for global minimum in continuous optimization. Journal of Mathematical Analysis and Applications, 412(2), 631-645.
• Tasgetiren, M., Liang, Y.-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930-1947.
• Tasgetiren, M., Pan, Q.-K., Suganthan, P., & Chen, A.-L. (2011). A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops. Information Sciences, 181(16), 3459-3475.
• Tseng, L., & Lin, Y. (2009). A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 198(1), 84-92.
• Widmer, M., & Hertz, A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41(2), 186-193.
• Yağmahan, B., & Yenisey, M. M. (2006an). Akış Tipi Çizelgeleme Problemi İçin KKE Parametre Eniyileme. İTÜ Dergisi, 5(2), 133-141.
• Ying, K.-C., & Liao, C.-J. (2004). An ant colony system for permutation flow-shop sequencing. Computers & Operations Research, 31(5), 791-801.
• Yu, Y., Zhang, F., Yang, G., Wang, Y., Huang, J., & Han, Y. (2022). A discrete artificial bee colony method based on variable neighborhood structures for the distributed permutation flowshop problem with sequence-dependent setup times. Swarm and Evolutionary Computation, 75, 1-15.
• Zhang, C., Zheng, J., & Zhou, Y. (2015). Two modified Artificial Bee Colony algorithms inspired by Grenade Explosion Method. Neurocomputing, 151(P3), 1198-1207.
• Zheng, J.-G., Zhang, C.-Q., & Zhou, Y.-Q. (2015). Artificial Bee Colony Algorithm Combined with Grenade Explosion Method and Cauchy Operator for Global Optimization. Hindawi Publishing Corporation Mathematical Problems in Engineering, 1-15.