The effects of initial populations in the solution of flow shop scheduling problems by hybrid firefly and particle swarm optimization algorithms

Abstract

The classical flow shop scheduling problem is based on the principle that the machines are sequenced sequentially and that the same machine sequence is followed for each job. The flow shop scheduling problems become very complex, with the increase in the number of jobs and machines. Many meta-heuristic methods are used to solve these complex problems. The effect of initial populations has great importance for searching optimal solutions by meta-heuristics methods. In this study, it is aimed to observe the effect of different initial populations in flow shop scheduling problems in the literature by using hybrid firefly particle swarm optimization algorithm. For this purpose, 5 different initial population generation methods were set and comparison tests were performed. The mean relative deviation values of the methods including the Nawaz-Enscore-Ham algorithm were determined to be better. The success of the Nawaz-Enscore-Ham algorithm for different particle count levels has been tested and the results are presented.

Keywords

• The flow shop scheduling problem,meta-heuristic methods,Hybrid firefly particle swarm optimization,Initial population,NEH

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

Öz

Klasik akış tipi çizelgeleme problemi, birbiri ardına sıralanmış makinelerin bulunduğu ve her iş için aynı makine sırasının takip edilmesi prensibine dayalıdır. İş ve makine sayılarının artmasıyla akış tipi çizelgeleme problemleri çok karmaşık hale dönüşmektedir. Bu karmaşık problemleri çözmek üzere birçok meta sezgisel yöntem kullanılmaktadır. Meta sezgisel yöntemlerle optimum çözüm aranırken başlangıç popülasyonlarının etkisi çok büyük önem arz etmektedir. Bu çalışmada hibrit ateşböceği parçacık sürü optimizasyonu algoritması kullanılarak literatürdeki akış tipi çizelgeleme problemlerinde, farklı başlangıç popülasyonlarının etkisinin gözlemlenmesi amaçlanmaktadır. Bu amaçla beş farklı başlangıç popülasyonu oluşturma yöntemi ele alınarak, karşılaştırma testleri yapılmıştır. Nawaz-Enscore-Ham algoritmasını içeren yöntemlerin ortalama göreli sapma değerlerinin daha iyi olduğu belirlenmiştir. Nawaz-Enscore-Ham algoritmasının farklı parçacık sayısı düzeyleri için başarısı test edilmiş ve sonuçlar sunulmuştur.

Anahtar Kelimeler

• Akış tipi çizelgeleme,Meta sezgisel yöntemler,Hibrit ateşböceği parçacık sürü optimizasyonu,Başlangıç popülasyonu,NEH

Kaynakça

1. Yağmahan B, Yenisey MM. “Akış tipi çizelgeleme problemi için KKE parametre eniyileme”. İTÜ Dergisi, 5(2), 133-141, 2006.
2. Kaya S, Fığlalı N. “Çok amaçlı esnek atölye tipi çizelgeleme problemlerinin çözümünde meta sezgisel yöntemlerin kullanımı”. Harran Üniversitesi Mühendislik Dergisi, 3(3), 222-233, 2018.
3. Aydilek İB. “A hybrid firefly and particle swarm optimization algorithm for computationally expensive numerical problems”. Applied Soft Computing, 66, 232-249, 2018.
4. Johnson SM. “Optimal two and three stage production schedules with setup time ıncluded”. Naval Research Logistics Quarterly, 1(1), 61-68, 1954.
5. Palmer D. “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, 1965.
6. Campbell HG, Dudek RA, Smıth BL. “A heuristic algorithm for the n job, m machine sequencing problem”. Management Science, 16(10), 630-637, 1970.
7. Gupta JND. “A Functional heuristic algorithm for flow-shop scheduling problem”. Operations Research, 22, 39-47,1971.
8. Dannenbring DG. “An evaluation of flow-shop sequencing heuristic”. Management Science, 23(11), 1174-1182, 1977.

9. Nawaz M, Enscore EJ, Ham I. “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem”. Omega, the International Journal Of Management Science, 11(1), 91-95, 1983.
10. Hundal TS, Rajgopal J. “An extension of palmer’s heuristic for the flow shop scheduling problem”. International Journal of Production Research, 26, 1119-1124, 1988.
11. Widmer M, Hertz A. “A new heuristic method for the flowshop sequencing problem”. European Journal of Operational Research, 41, 186-193, 1989.
12. Ho JC, Chang Y. “A new heuristic for the n-Job, m-Machine flow-shop problem”. European Journal of Operational Research, 52(2), 194-202, 1991.
13. Engin O, Fığlalı A. “Akış tipi çizelgeleme problemlerinin genetik algoritma yardımı ile çözümünde uygun çaprazlama operatörünün belirlenmesi”. Doğuş Üniversitesi Dergisi, 6, 27-35, 2002.
14. Janiak A. “General Flow-shop scheduling with resource constraints”. International Journal of Production Research, 26(6), 1089-1093, 1988.
15. Tandon M, Cummings PT, LeVan MD. “Flowshop sequencing with non-permutation schedules”. Computing Chem Engineering, 15(8), 601-607, 1991.
16. Benavides AJ, Ritt M. “Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops”. Computer and Operation Research, 66, 160-169, 2016.
17. Cui WW, Lu Z, Zhou B, Li C, Han X. “A hybrid genetic algorithm for non-permutation flow shop scheduling problems with unavailability constraints”. International Journal Computing Integrated Manufacturing, 29(9),1-18, 2016.
18. Henneberg M, Neufeld JS. “A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations”. International Journal Production Research, 54(12), 3534-50, 2016.
19. Pugazhenthi R, Xavior MA. “Computation of Makespan Using Genetic Algorithm in a Flowshop”. American-Eurasian Journal of Scientific Research, 9, 105-113, 2014.
20. Benavides AJ, Ritt M. “Iterated local search heuristics for minimizing total completion time in permutation and non-permutation flow shops”. TwentyFifth International Conference on Automated Planning and Scheduling ICAPS, Jerusalem, Israel, 7-11 June 2015.
21. Reeves CR, Yamada T. “Genetic algorithm path relinking and the flow shop sequencing problem”. Evolutionary Computation, 6, 45-60, 1998.
22. Rajendran C, Ziegler H. “Ant-colony algorithms for permutation flow shop scheduling to minimize makespan total flowtime of jobs”. European Journal of Operational Research, 155, 426-438, 2004.
23. Taşgetiren F, Liang Y C, Sevkli M, Gencyilmaz G. “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flow shop sequencing problem”. European Journal of Operational Research, 177, 1930-1947, 2007.
24. İşler M. Bulanık Esnek Akış Tipi Çizelgeleme Problemlerinin Paralel Doyumsuz Algoritma Ile Çözümü: Bir Hazır Giyim işletmesine Uygulanması. Yüksek Lisans Tezi, Selçuk Üniversitesi, Konya, Türkiye, 2009.
25. Alaykıran K, Engin O, Döyen A. “Using Ant Colony Optimization to Solve Hybrid Flow Shop Scheduling Problems”. International Journal Advanced Manufacturing Technology, 35, 541-550, 2007.
26. Kahraman C, Engin O, Kaya İ, Yılmaz MK. “An application of effective genetic algorithms for solving hybrid flow shop scheduling problems”. International Journal of Computational Intelligence Systems, 1(2), 134-147, 2008.
27. Kianfar K, Ghomi SMTF, Jadid AO. “Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA”. Engineering Applications of Artificial Intelligence, 25, 494-506, 2012.
28. Jolai F, Asefi H, Rabiee M, Ramezani P. “Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem”. Scientia Iranica, 20, 861-872, 2013.
29. Keskin K. Beklemesiz Akış Tipi Çizelgeleme Problemlerinin Çok Amaçlı Genetik Algoritma ile Çözümü, Yüksek Lisans Tezi, Selçuk Üniversitesi, Konya, Türkiye, 2010.
30. Laha D, Sapkal SU. “An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop”. Computers & Industrial Engineering, 67, 36-43, 2014.
31. Tseng L, Lin Y. “A hybrid genetic algorithm for no-wait flow shop scheduling problem”. International Journal of Production Economics, 128, 144-152, 2010.
32. Chaudhry IA, Mahmood S. “No-wait Flow shop Scheduling Using Genetic Algorithm”. No-wait Flowshop Scheduling Using Genetic Algorithm, 3, 4-6, 2012.
33. Czogalla J, Fink A. “Design and analysis of evolutionary algorithms for the no-wait flow shop scheduling problem”. Metaheuristics in the Service Industry, Lecture Notes in Economics and Mathematical Systems, 624, 99-126, 2009.
34. Pan QK, Wang L, Qian B. “A novel differential evolution algorithm for bi criteria no wait flow shop scheduling problems”. Computers & Industrial Engineering, 36, 2498-2511, 2009.
35. Moghaddam RT, Vahed ARR, Mirzaei AH. “Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm”. International Journal Advanced Manufacturing Technology, 36, 969-981, 2008.
36. Allahverdi A, Aldowaisan T. “No-wait flowshops with bicriteria of makespan and maximum lateness”. European Journal of Operational Research, 152, 132-147, 2004.
37. Araújoa DC, Nagano MS. “A new effective heuristic method for the no-wait flowshop with sequence-dependent setup times problem”. International Journal of Industrial Engineering Computations, 2, 155-166, 2011.
38. Kumar G, Singhal S. “Genetic Algorithm Optimization of Flowshop Scheduling Problem with Sequence Dependent Setup Time and Lot Splitting”. International Journal of Engineering, Business and Enterprise Applications (IJEBEA), 4(1), 62-71, 2013.
39. İşler MC, Çelik V, Toklu B. “İki makine akış tipi öğrenme etkili çizelgelemede ortak teslim tarihinden mutlak sapmaların en küçüklenmesi”. Journal Faculty Engineering Arch Gazi University, 24(2), 351-357, 2009.
40. Akçay E. Akış Tipi İş Çizelgeleme Problemlerinin Yapay Bağışıklık Sistemi İle Çok Amaçlı Optimizasyonuna Yönelik Bir Model Önerisi. Doktora Tezi, Kocaeli Üniversitesi, Kocaeli, Türkiye. 2009.
41. Rossit DA, Tohméb F, Frutos M. “The Non-Permutation Flow-Shop scheduling problem: A literature review”. Omega, 77, 143-153, 2018.
42. Yang XS. Firefly algorithms for multimodal optimization. Editors: Watanabe O, Zeugmann T. Stochastic Algorithms: Foundations and Applications, 169-178. Berlin, GERMANY, Springer, 2009.
43. Kennedy J, Eberhart R. "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks, 4, 1942-1948, 1995.
44. Xin J, Chen G, Hai Y. “A Particle Swarm Optimizer with Multistage Linearly-Decreasing Inertia Weight”. International Joint Conference on Computational Sciences and Optimization (CSO-2009), Sanya, Hainan, China. 24-26 April 2009.
45. Bean JC. “Genetic algorithm and random keys for sequencing and optimization”. ORSA journal on computing, 6(2), 154-160, 1994.
46. Taillard E. “Benchmarks For Basic Scheduling Problems”. http://mistic.heig-ve diğ.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html (04.02.2019).
47. Wang H, Wang W, Sun H, Cui Z, Rahnamayan S, Zeng S. "A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems". Soft Computing, 21, 4297-4307, 2017.