ÇOK AMAÇLI PERMÜTASYON AKIŞ TİPİ ÇİZELGELEME PROBLEMİ İÇİN BİR NSGA-II ALGORİTMASI

Yıl 2020, , 105 - 121, 31.08.2020

Tuğba Saraç , Nilay Bilgiçer

https://doi.org/10.46465/endustrimuhendisligi.623030

Öz

Bu çalışmada, sıra
bağımlı hazırlık sürelerinin olduğu çok amaçlı permütasyon akış tipi
çizelgeleme problemi ele alınmıştır. Problemin amaçları, son işin tamamlanma
zamanının, toplam gecikmenin ve toplam erken tamamlanma süresinin enküçüklenmesidir.
Ele alınan problemin çözümüne yönelik olarak bir genetik algoritma ve problemin
çok amaçlı doğası dikkate alınarak bir NSGA-II algoritması önerilmiştir. Ayrıca,
literatürde tek makine çizelgeleme problemleri için önerilmiş olan öncelik
kurallarından bazıları uyarlanarak, ilk neslin başarısını arttırmakta
kullanılmıştır. Önerilen algoritmaların başarısı, rassal türetilen test
problemleri kullanılarak gösterilmiştir. 

Anahtar Kelimeler

Çok amaçlı akış tipi çizelgeleme problemi, sıra bağımlı hazırlık süreleri, genetik algoritma, NSGA-II algoritması

Kaynakça

• Behnamian, J., Fatemi Ghomi, S.M.T & Zandieh, M. (2009). A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. Expert Systems with Applications, 36(8), 11057-11069. doi: 10.1016/j.eswa.2009.02.080
• Ciavotta, M., Minella, G. & Ruiz, R. (2013). Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study. European Journal of Operational Research, 227(2), 301–313. doi: 10.1016/j.ejor.2012.12.031
• Ciavotta, M., Ruiz, R. & Minella, G. (2009). New results for the multi-objective sequence dependent setup times flowshop problem. Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2009), Dublin, Ireland, Dublin, Ireland, 10-12 August.
• Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions On Evolutionary Computation, 6(2), 182-197. doi: 10.1109/4235.996017
• Deng J. & Wang L. (2017). A competitive memetic algorithm for multi-objective distributedDhingra, A. & Chandna, P. (2009). Hybrid genetic algorithm for multicriteria scheduling with sequence dependent setup time. International Journal of Engineering (IJE), 3(5), 510-520. Erişim adresi: https://www.cscjournals.org/manuscript/Journals/ IJE/Volume3/ Issue5/IJE-112.pdf
• Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R. & Maboudian, Y. (2010). Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times. Int J Adv Manuf Technol, 50(9), 1153–1164. doi: 10.1007/s00170-010-2579-5
• Huang R.H. & Yang C.L. (2009). Solving a multi-objective overlapping flowshop scheduling. Int J Adv Manuf Technol, 42(9), 955–962. doi: 10.1007/s00170-008-1652-9
• Jiang E. & Wang L. (2019). An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time. International Journal of Production Research, 57(6), 1756-1771. doi: 10.1080/00207543.2018.1504251
• Kahraman, C., Engin, O. & Yilmaz, M.K. (2009). A New Artificial Immune System Algorithm for Multiobjective Fuzzy Flow Shop Problems. International Journal Of Computational Intelligence Systems, 3, 236-247. doi: 10.1080/18756891.2009.9727656
• Karimi, N. & Davoudpour, H. (2014). A high performing metaheuristic for multi-objective flowshop scheduling problem. Computers & Operations Research, 52, 149–156. doi: 10.1016/j.cor.2014.01.006
• Karimi, N., Zandieh, M. & Karamooz, H.R. (2010). Bi-objective group scheduling in melez flexible flowshop: A multi-phase approach. Expert Systems with Applications, 37(6), 4024-4032. doi: 10.1016/j.eswa.2009.09.005
• Lacoste , J., Ibanez, M.L. & Stützle, T. (2011). A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems. Computers & Operations Research, 38(8), 1219–1236. doi: 10.1016/j.cor.2010.10.008
• Mokotoff, E. (2009). Minimizing the Makespan and Total Flow Time on the Permutation Flowshop Scheduling Problem. Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2009), Dublin, Ireland, 10-12 August. Erişim adresi: http://www.mistaconference.org/2009/papers/479-506-069-P.pdf
• Mokotoff, E. (2011). Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal Of Industrial And Management Optimization, 7(1), 253-282. doi: 10.3934/jimo.2011.7.253
• Naderi, B., Tavakkoli-Moghaddam, R. & Khalili, M. (2010). Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowl Based Syst, 23(2), 77–85. doi: 10.1016/j.knosys.2009.06.002
• Naderi, B., Zandieh, M., Balagh, A.K.G. & Roshanaei, V. (2009). An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems Applications, 36(6), 9625–9633. doi: 10.1016/j.eswa.2008.09.063
• Pan, Q.K., Wang, L. & Qian, B. (2009). A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems. Computers & Operations Research, 36(8), 2498 – 2511. doi: 10.1016/j.cor.2008.10.008
• permutation flow shop scheduling problem. Swarm and Evolutionary Computation, 32, 121–131. doi: 10.1016/j.swevo.2016.06.002
• Qian, B., Wang, L., Huang, D., Wang, W. & Wang X. (2009). An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research, 36(1), 209 – 233. doi: 10.1016/j.cor.2007.08.007
• Qian, B., Wang, L., Huang, D.X. & Wang X., (2009). Mutli-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution. Soft Comput, 13, 847–869. doi: 10.1007/s00500-008-0350-8
• Rajendran, C. & Ziegler, H. (2003). Scheduling to Minimize the Sum of Weighted Flowtime and Weighted Tardiness of Jobs in A Flowshop with Sequence-Dependent Setup Times. European Journal of Operational Research, 149 (3), 513–522. doi: 10.1016/S0377-2217(02)00485-X
• Robert R.B.J. & Rajkumar R. (2019). A hybrid algorithm for multi-objective optimization of minimizing makespan and total flow time in permutation flow shop scheduling problems. Journal of Information Technology and Control, 48 (1), 47-57. doi: 10.5755/j01.itc.48.1.20909
• Schaller, J. & Valente, J.M.S. (2013). An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness. Journal of the Operational Research Society, 64(6), 805–816. doi: 10.1057/jors.2012.94
• Seif J., Yu A.J.& Rahmanniyay F. (2018). Modelling and optimization of a bi-objective flow shop scheduling with diverse maintenance requirements. International Journal of Production Research, 56(9), 3204-3225. doi:10.1080/00207543.2017.1403660
• Sha, D.Y. & Lin, H.H. (2009). A particle swarm optimization for multiobjective flowshop scheduling. Int J Adv Manuf Technol, 45(7-8), 749–758. doi: 10.1007/s00170-009-1970-6
• Vahed, A.R., Dangchi, M., Rafiei, H. & Salimi, E. (2009). A novel hybrid multi-objective shuffled frog-leaping algorithm for a bi-criteria permutation flow shop scheduling problem. Int J Adv Manuf Technol, 41(11), 1227-1239. doi: 10.1007/s00170-008-1558-6
• Valente, J.S.M. (2003). Using instance statistics to determine the lookahead parameter value in the ATC dispatch rule: Making a good heuristic better. FEP Working Papers, Universidade do Porto, Faculdade de Economia do Porto. Erişim adresi: http://wps.fep.up.pt/wps/wp127.pdf
• Xu, J. & Zhou, X. (2009). A class of multi-objective expected value decision-making model with birandom coefficients and its application to flow shop scheduling problem. Information Sciences, 179(17), 2997–3017. doi: 10.1016/j.ins.2009.04.009
• Yagmahan, B. & Yenisey, M.M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 37(2), 1361–1368. doi: 10.1016/j.eswa.2009.06.105
• Yuan F., Xu X. & Yin M. (2019). A novel fuzzy model for multi-objective permutation flow shop scheduling problem with fuzzy processing time. Advances in Mechanical Engineering, , 11(4), 1–9. doi: 10.1177/1687814019843699