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

KÜPELİ, İpek; SARUCAN, Ahmet; KÜPELİ, Ahmet Sezer

doi:10.31202/ecjse.670424

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

İpek KÜPELİ, (Konya Teknik Üniversitesi, Lisansüstü Eğitim Enstitüsü, Endüstri Mühendisliği Anabilim Dalı, Konya, Türkiye)

Ahmet SARUCAN, (Konya Teknik Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Endüstri Mühendisliği Bölümü, Konya, Türkiye)

Ahmet Sezer KÜPELİ (ASC Hidrolik A.Ş. Konya, Türkiye)

El-Cezerî Journal of Science and Engineering

8 2

Yıl: 2020 Cilt: 7 Sayı: 2 Sayfa Aralığı: 549 - 562 Metin Dili: Türkçe DOI: 10.31202/ecjse.670424 İndeks Tarihi: 02-12-2021

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

Öz:

Bu çalışmada amaç fonksiyonu maksimum tamamlanma süresinin minimizasyonu 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 (Nawaz Enscore Ham) 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 ölçülmüştür. Algoritma, 14 adet sezgisel ile karşılaştırılmıştır ve en iyi sonuçları sunmuştur.

Anahtar Kelime:

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

Öz:

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.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[1]. Ruiz, R., Q.-K. Pan, and B. Naderi, Iterated Greedy methods for the distributed permutation flowshop scheduling problem, Omega, 2019, 83: 213-222.
[2]. 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, 2278-2283.
[3]. 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, 8379-8383.
[4]. 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: 464-477.
[5]. 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): 68-82.
[6]. Deng, J. and L. Wang, A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem. Swarm and Evolutionary Computation, 2017, 32: 121-131.
[7]. 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. 992-999.
[8]. 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: 239-250.
[9]. 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. 2433-2437.
[10]. 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, 2240-2246.
[11]. Naderi, B. and R. Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational Research, 2014, 239(2): 323-334.
[12]. 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): 5029-5038.
[13]. 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): 387-396.
[14]. 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): 641-651.
[15]. Gao, J. and R. Chen, An NEH-based heuristic algorithm for distributed permutation flowshop scheduling problems. Scientific Research and Essays, 2011, 6: 3094-3100.
[16]. 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): 497-508.
[17]. 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, 156-163.
[18]. Naderi, B. and R. Ruiz, The distributed permutation flowshop scheduling problem. Computers & Operations Research, 2010, 37(4): 754-768.
[19]. 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): 3471-3484.
[20]. 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): 6758-6779.
[21]. 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.
[22]. 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): 1459-1463.
[23]. 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): 1921- 1935.
[24]. 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): 3459-3475.
[25]. 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): 459-471.
[26]. Tosun, Ö., Yapay Arı Kolonisi Algoritması ve Permütasyon Akış Tipi Çizelgeleme Problemine Uygulanması, Akdeniz Üniversitesi Sosyal Bilimler Enstitüsü, 2012: 1-111.
[27]. Pan, Q.-K., et al., A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Information Sciences, 2011, 181(12): 2455-2468.
[28]. Akgüngör A.P., Yılmaz Ö., Korkmaz E., Doğan E., “Meta-Sezgisel Yöntemlerle Sabit Zamanlı Sinyalize Kavşaklar için Optimum Devre Süresi Modeli”, El-Cezerî Fen ve Mühendislik Dergisi, 2019, 6(2): 259-269.
[29]. Arseven İ., Dağıtık Permütasyonlu Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması ile Çözümü, Yüksek Lisans, Konya Teknik Üniversitesi Lisansüstü Eğitim Enstitüsü, 2019.
[30]. Arseven İ., Sarucan A., Dağıtık Permütasyonlu Akış Tipi Çizelgeleme Problemlerinin Çözümü İçin Bir Yapay Arı Koloni Algoritması, 6. Uluslararası GAP Mühendislik Kongresi, Şanlıurfa, 2018, 172-175.
[31]. Kalczynski, P. and J. Kamburowski, On the NEH heuristic for minimizing the makespan in permutation flow shops, Omega, 2007, 35(1): 53-60.

APA	KÜPELİ İ, SARUCAN A, KÜPELİ A (2020). Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. , 549 - 562. 10.31202/ecjse.670424
Chicago	KÜPELİ İpek,SARUCAN Ahmet,KÜPELİ Ahmet Sezer Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. (2020): 549 - 562. 10.31202/ecjse.670424
MLA	KÜPELİ İpek,SARUCAN Ahmet,KÜPELİ Ahmet Sezer Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. , 2020, ss.549 - 562. 10.31202/ecjse.670424
AMA	KÜPELİ İ,SARUCAN A,KÜPELİ A Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. . 2020; 549 - 562. 10.31202/ecjse.670424
Vancouver	KÜPELİ İ,SARUCAN A,KÜPELİ A Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. . 2020; 549 - 562. 10.31202/ecjse.670424
IEEE	KÜPELİ İ,SARUCAN A,KÜPELİ A "Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü." , ss.549 - 562, 2020. 10.31202/ecjse.670424
ISNAD	KÜPELİ, İpek vd. "Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü". (2020), 549-562. https://doi.org/10.31202/ecjse.670424

APA	KÜPELİ İ, SARUCAN A, KÜPELİ A (2020). Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. El-Cezerî Journal of Science and Engineering, 7(2), 549 - 562. 10.31202/ecjse.670424
Chicago	KÜPELİ İpek,SARUCAN Ahmet,KÜPELİ Ahmet Sezer Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. El-Cezerî Journal of Science and Engineering 7, no.2 (2020): 549 - 562. 10.31202/ecjse.670424
MLA	KÜPELİ İpek,SARUCAN Ahmet,KÜPELİ Ahmet Sezer Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. El-Cezerî Journal of Science and Engineering, vol.7, no.2, 2020, ss.549 - 562. 10.31202/ecjse.670424
AMA	KÜPELİ İ,SARUCAN A,KÜPELİ A Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. El-Cezerî Journal of Science and Engineering. 2020; 7(2): 549 - 562. 10.31202/ecjse.670424
Vancouver	KÜPELİ İ,SARUCAN A,KÜPELİ A Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü. El-Cezerî Journal of Science and Engineering. 2020; 7(2): 549 - 562. 10.31202/ecjse.670424
IEEE	KÜPELİ İ,SARUCAN A,KÜPELİ A "Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü." El-Cezerî Journal of Science and Engineering, 7, ss.549 - 562, 2020. 10.31202/ecjse.670424
ISNAD	KÜPELİ, İpek vd. "Dağıtık Permütasyon Akış Tipi Çizelgeleme Problemlerinin Yapay Arı Koloni Algoritması İle Çözümü". El-Cezerî Journal of Science and Engineering 7/2 (2020), 549-562. https://doi.org/10.31202/ecjse.670424