Beklemesiz Akış Tipi Çizelgeleme Problemlerinin Analizi ve Hibrit Dağınık Arama Yöntemi ile Çözümü

Year 2022, Volume: 8 Issue: 2, 293 - 308, 23.06.2022

Ramazan Başar , Orhan Engin

https://doi.org/10.28979/jarnas.936151

Cited By: 3

Abstract

Beklemesiz Akış Tipi Çizelgeleme (BATÇ), pratik uygulamalarından dolayı kapsamlı bir araştırma alanıdır. BATÇ problemlerinde işler, makinelerde kesintisiz olarak işlem görmek zorundadır. Bir işin tüm makinelerde işlenme süresi boyunca, makineler bekleyebilir fakat işler kesintisiz olarak işlenmelidir. Amaç ise makinelerin boşta bekleme süresini en aza indirmektir. BATÇ problemlerinin çoğunluğunda toplam gecikmenin ve maksimum tamamlanma zamanının minimizasyonu olmak üzere, iki performans ölçüsü göz önünde bulundurulur. Literatürde, son yirmi beş yılda BATÇ ile ilgili yapılan çalışmalar analiz edilmiştir. BATÇ problemlerinin çözümü ile ilgili geliştirilen kesin ve yaklaşık çözüm veren yöntemler incelenmiştir. Literatürde 1 ve 2 makineli problemler için optimum çözüm veren matematiksel yöntemler bulunurken, 3 ve daha fazla makineli problemler için standart zamanda optimum çözüm veren bir yöntem bulunmamaktadır. Kabul edilebilir bir süre içerisinde m makine içeren problemlere optimum ya da optimuma yakın çözümler üretebilmek için sezgisel ve meta sezgisel yöntemler geliştirilmektedir. Bu çalışmada, BATÇ problemlerinin çözümü için Hibrit Dağınık Arama (HDA) yöntemi önerilmiştir. Önerilen yöntem, literatürde iyi bilinen kıyaslama problemleri yardımı ile test edilmiştir. Elde edilen sonuçlar, Hibrit Uyarlanabilir Öğrenme Yaklaşım (HUÖY) algoritması ve Hibrit Karınca Kolonileri Optimizasyon (HKKO) algoritması ile kıyaslanmıştır. Amaç fonksiyonu olarak maksimum tamamlanma zamanının minimizasyonu seçilmiştir. Elde edilen çözüm sonuçları, önerilen HDA yönteminin BATÇ problemlerinin çözümünde etkili olduğunu göstermiştir.

Keywords

hibrit dağınık arama, tamamlanma zamanı, beklemesiz çizelgeleme, Akış tipi

Analysis of No-wait Flow Shop Scheduling Problems and Solving with Hybrid Scatter Search Method

Abstract

No-wait flow shop (NWFS) is extensively research area due to its practical applications. In NWFS, jobs are pro-cessed in machines without interruption. During the schedule period, machines can wait, but jobs cannot wait. The aim is to minimize the idle time for machines. The majority of NWFS, two performance measures are considered: minimization of total delay and minimization of the makespan. The researches on the NWFS in the last twenty-five years have been analysed from the literature. The methods developed for the solution of the NWFS, which give exact and approximate solutions, have been examined. While there are mathematical methods that give optimum solutions for 1 and 2 machine problems in the literature, there is no method that provides optimum solutions in standard time for problems with 3 or more machines. The difference methods are developed in order to produce optimum or near-optimum solutions to m-machine problems in an acceptable time. A Hybrid Scatter Search Meth-od (HSSM) is proposed for solving the NWFS. The developed HSSM tested with the well-known benchmarking instances in the literature. The results obtained were compared with the Hybrid Adaptive Learning Approach algo-rithm and the Hybrid Ant Colonies Optimization algorithm. The objective function is makespan minimization. According to solutions, the proposed HSSM is an effective metaheuristic to solve NWFS.

Keywords

hybrid scatter search, makespan, no-wait scheduling, Flow shop

References

• Akhshabi, M., Moghaddam, R.T. ve Roodposhti, F.R. (2014). A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time, Int J Adv Manuf Technol, 70: 1181-1188. https://link.springer.com/content/pdf/10.1007/s00170-013-5351-9.pdf
• Allahverdi A. ve Aydilek H. (2014). Total completion time with makespan constraint in no-wait flowshops with setup times, European Journal of Operational Research, 238: 724-734. https://doi.org/10.1016/j.ejor.2014.04.031
• Allahverdi, A., Aydilek, H. ve Aydilek, A. (2020). No-wait flowshop scheduling problem with separate setup times to minimize total tardiness subject to makespan, Applied Mathematics and Computation, 365: 124688. https://doi.org/10.1016/j.amc.2019.124688
• Allahverdi, M., Aydilek, H., Aydilek, A. ve Allahverdi, A. (2021). A better dominance relation and heuristics for two-machine no-wait flowshops with maximum lateness performance measure, Journal of Industrial & Management Optimization, 17(4): 1973-1991. http://dx.doi.org/10.3934/jimo.2020054
• Alsaidi, S. A. A. A., Muhsen, D. K. ve Ali, S. M. (2020). Improved scatter search algorithm based on meerkat clan algorithm to solve NP-hard problems, Periodicals of Engineering and Natural Sciences (PEN), 8(3): 1555-1565. http://dx.doi.org/10.21533/pen.v8i3.1563.g642
• Asefi H., Jolai, F., Rabiee, M. ve Araghi, M.E.T. (2014). A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem, Int J Adv Manuf Technol, 75: 1017-1033. https://link.springer.com/content/pdf/10.1007/s00170-014-6177-9.pdf
• Aydilek, H. ve Allahverdi, A. (2012). Heuristics for no-wait flowshops with makespan subject to mean completion time, Applied Mathematics and Computation, 219: 351-359. https://doi.org/10.1016/j.amc.2012.06.024
• Başar, R. ve Engin, O. (2021). A No-Wait Flow Shop Scheduling Problem with Setup Time in Fuzzy Environment. In International Conference on Intelligent and Fuzzy Systems, Springer, Cham 607-614. https://link.springer.com/chapter/10.1007/978-3-030-85626-7_71
• Bewoor, L. A., Chandraprakash, V. ve Sapkal, S. U. (2019). Evolutıonary hybrıd partıcle swarm optımızatıon algorıthm to mınımıze makespan toschedule a flow shop wıth no waıt, Journal of Engineering Science and Technology, 14(2): 609-628. https://jestec.taylors.edu.my/Vol%2014%20issue%202%20April%202019/14_2_8.pdf
• Bewoor, L.A., Prakash, V.C. ve Sapkal, S.U. (2017). Evolutionary Hybrid Particle Swarm Optimization Algorithm for Solving NP-Hard No-Wait Flow Shop Scheduling Problems, Algorithms, 10(121): 1-17. https://doi.org/10.3390/a10040121
• Bożejko, W. ve Wodecki, M. (2007). Parallel scatter search algorithm for the flow shop sequencing problem, International Conference on Parallel Processing and Applied Mathematics, Springer, Berlin, Heidelberg, 180-188. https://link.springer.com/chapter/10.1007/978-3-540-68111-3_20
• Chaudhry, I.A., Elbadawi, I.A.Q., Usman, M. ve Chugtai, M.T. (2018). Minimising Total Flowtime in a No-Wait Flow Shop (NWFS) using Genetic Algorithms, Ingenıería E Investıgacıón, 38(3): 68-79. https://doi.org/10.15446/ing.investig.v38n3.75281
• Chen, K., Li, D. ve Wang, X.. (2020). Makespan minimization in two-machine flow-shop scheduling under no-wait and deterministic unavailable ınterval constraints, Journal of Systems Science and Systems Engineering, 29(4): 400-411. https://link.springer.com/article/10.1007/s11518-020-5456-2
• Cheng, C. Y., Ying, K. C., Li, S. F. ve Hsieh, Y. C. (2019). Minimizing makespan in mixed no-wait flowshops with sequence-dependent setup times, Computers & Industrial Engineering, 130: 338-347. https://doi.org/10.1016/j.cie.2019.02.041
• Chihaoui, F.B., Kacem, I., Hadj-Alouane, A.B., Dridi, N. ve Rezg, N. (2011). No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates, International Journal of Production Research, 49(21): 6273-6286. https://doi.org/10.1080/00207543.2010.531775
• Czogalla, J. ve Fink, A. (2012). Fitness landscape analysis for the no-wait flow-shop scheduling problem, J Heuristics, 18: 25-51. https://link.springer.com/content/pdf/10.1007/s10732-010-9155-x.pdf
• Çiçekli, U. G. ve Bozkurt, S, (2016). Permütasyon Akış Tipi Çizelgeleme Probleminin Dağınık Arama ile Optimizasyonu, Ege Academic Review, 16: 31-40. Doi: 10.21121/eab.2018OZEL24421
• Deng, G., Wei, M., Su, Q. ve Zhao, M. (2015). An effective co-evolutionary quantum genetic algorithm for the no-wait flow shop scheduling problem, Advances in Mechanical Engineering, 7(12): 1-10. https://doi.org/10.1177/1687814015622900
• Engin, O. ve Güçlü, A. (2018). A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems, Applied Soft Computing, 72: 166-176. https://doi.org/10.1016/j.asoc.2018.08.002
• Engin, O. ve Günaydın, C. (2011). An adaptive learning approach for no-wait flowshop scheduling problems to minimize makespan, International Journal of Computational Intelligence Systems, 4(4): 521-529. https://doi.org/10.1080/18756891.2011.9727810
• Engin, O., Kahraman C. ve Yilmaz, M. K. (2009). A scatter search method for multiobjective fuzzy permutation flow shop scheduling problem: a real world application, U.K. Chakraborty (Ed.): Comput. Intel. in Flow Shop and Job Shop Sched., SCI 230: 169-189. https://link.springer.com/chapter/10.1007/978-3-642-02836-6_6
• Engin, O., Yılmaz, M. K., Baysal, M. E. ve Sarucan, A. (2013). Solving Fuzzy Job Shop Scheduling Problems with Availability Constraints Using a Scatter Search Method, J. of Mult.-Valued Logic and Soft Computing, 21: 317-334. https://www.researchgate.net/publication/259478991
• Espinouse, M.L., Formanowicz, P. ve Penz, B. (1999). Minimizing the Makespan in the Two-Machine No-Wait Flow- Shop with Limited Machine Availability, Computers & Industrial Engineering, 37: 497-500. https://doi.org/10.1016/S0360-8352(99)00127-8
• Ferretti, I. ve Zavanella, L. E. (2020). Batch energy scheduling problem with no-wait/blocking constraints for the general flow-shop problem, Procedia Manufacturing, 42: 273-280. https://doi.org/10.1016/j.promfg.2020.02.097
• Gao, F., Liu, M., Wang, J.J. ve Lu, Y.Y. (2018). No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times, International Journal of Production Research, 56(6): 2361-2369. https://doi.org/10.1080/00207543.2017.1371353
• Haq, A. N., Saravanan, M., Vivekraj, A. R. ve Prasad, T. (2007). A scatter search approach for general flowshop scheduling problem, The International Journal of Advanced Manufacturing Technology, 31(7-8): 731-736. https://link.springer.com/content/pdf/10.1007/s00170-005-0244-1.pdf
• Jolai, F., Rabiee M. ve Asefi, H. (2012). A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times, International Journal of Production Research, 50(24): 7447-7466. https://doi.org/10.1080/00207543.2011.653012
• Kaya, S., Akgöbek Ö. ve Engin, O. (2011). Scatter Search Metaheuristic for Solving the Flow Shop Scheduling with Earliness and Tardiness Penalties, NWSA e-Journal of New World Science Academy, Engineering Sciences, 6(1): 415- 420. https://dergipark.org.tr/tr/download/article-file/186280
• Keskin, K. ve Engin, O. (2021). A hybrid genetic local and global search algorithm for solving no-wait flow shop problem with bi criteria, SN Appl Sci, 3: 628: 1–15. https://doi.org/10.1007/s42452-021-04615-3
• Koulamas, C. ve Kyparisis, G. J. (2021). The no-wait flow shop with rejection, International Journal of Production Research, 59(6): 1852-1859. https://doi.org/10.1080/00207543.2020.1727042
• Kumar, S., Bagchi, T.P. ve Sriskandarajah, C. (2000). Lot streaming and scheduling heuristics for m-machine no-wait flowshops, Computers & Industrial Engineering, 38: 149-172. https://doi.org/10.1016/S0360-8352(00)00035-8
• Labıdı, M., Koolı, A., Ladharı, T., Gharbı, A. ve Suryahatmaja, U.S. (2018). A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints, IEEE Access, 6: 16294-16304. DOI: 10.1109/ACCESS.2018.2815598
• Laha, D. ve Gupta, J.N.D. (2016). A Hungarian penalty-based construction algorithm to minimize makespan and total flow time in no-wait flow shops, Computers & Industrial Engineering, 98: 373-383. https://doi.org/10.1016/j.cie.2016.06.003
• Li, H., Li, X. ve Gao, L. (2021). A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem, Applied Soft Computing, 100: 106946. https://doi.org/10.1016/j.asoc.2020.106946
• Lin, S. W. ve Ying, K. C. (2019). Makespan optimization in a no-wait flowline manufacturing cell with sequence-dependent family setup times, Computers & Industrial Engineering, 128: 1-7. https://doi.org/10.1016/j.cie.2018.12.025
• Moghaddam, R.T., Vahed, A.R.R. ve Mirzaei, A.H. (2008). Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm, Int J Adv Manuf Technol, 36: 969-981. https://link.springer.com/article/10.1007/s00170-006-0906-7
• Moradinasab, N., Shafaei, R., Rabiee, M. ve Ramezani, P. (2013). No-wait two stage hybrid flow shop scheduling with genetic and adaptive imperialist competitive algorithms, Journal of Experimental & Theoretical Artificial Intelligence, 25(2): 207-225. https://doi.org/10.1080/0952813X.2012.682752
• Naderi, B. ve Ruiz, R. (2014). A scatter search algorithm for the distributed permutation flowshop scheduling problem, European Journal of Operational Research, 239(2): 323-334. https://doi.org/10.1016/j.ejor.2014.05.024
• Nowicki, E. ve Smutnicki, C. (2006). Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research, 169(2): 654-666. https://doi.org/10.1016/j.ejor.2004.08.021
• Oktay, S. ve Engin, O. (2006). Endüstriyel Problemlerin Çözümünde Dağınık Arama Yöntemi: Literatür Araştırması, Sigma: Mühendislik ve Fen Bilimleri Dergisi, 24(3): 144-155. https://kutuphane.dogus.edu.tr/mvt/pdf.php
• Pourhejazy, P., Lin, S. W., Cheng, C. Y., Ying, K. C. ve Lin, P. Y. (2020). Improved beam search for optimizing no-wait flowshops with release times, IEEE Access, 8: 148100-148124. DOI: 10.1109/ACCESS.2020.3015737
• Qi, X., Wang, H., Zhu, H., Zhang, J., Chen, F. ve Yang, J. (2016). Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization, International Journal of Production Research, 54(16): 4957-4972. https://doi.org/10.1080/00207543.2016.1150615
• Riahi, V., Khorramizadeh, M., Newton, M. H. ve Sattar, A. (2017). Scatter search for mixed blocking flowshop scheduling, Expert Systems with Applications, 79: 20-32. https://doi.org/10.1016/j.eswa.2017.02.027
• Samarghandi, H. (2015a). A no-wait flow shop system with sequence dependent setup times and server constraints, IFAC-PapersOnLine, 48(3): 1604-1609. https://doi.org/10.1016/j.ifacol.2015.06.315
• Samarghandi, H. (2015b). Studying the effect of server side-constraints on the makespan of the no-wait flow shop problem with sequence dependent setup times, International Journal of Production Research, 53(9): 2652-2673. https://doi.org/10.1080/00207543.2014.974846
• Samarghandi, H. ve Behroozi, M. (2017). On the exact solution of the no-wait flow shop problem with due date constraints, Computers and Operations Research, 81: 141-159. https://doi.org/10.1016/j.cor.2016.12.013
• Samarghandi, H. ve ElMekkawy, T.Y. (2012). A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion, Int J Adv Manuf Technol, 61: 1101-1114. https://link.springer.com/content/pdf/10.1007/s00170-011-3766-8.pdf
• Saravanan, M., Haq, A. N., Vivekraj, A. R. ve Prasad, T. (2008). Performance evaluation of the scatter search method for permutation flowshop sequencing problems, The International Journal of Advanced Manufacturing Technology, 37(11-12): 1200-1208. https://link.springer.com/content/pdf/10.1007/s00170-007-1053-5.pdf
• Schaller, J. ve Valente, J. M. (2020). Minimizing total earliness and tardiness in a nowait flow shop, International Journal of Production Economics, 224: 107542. https://doi.org/10.1016/j.ijpe.2019.107542
• Shabtay, D., Arviv, K., Stern, H. ve Edan, Y. (2014). A combined robot selection and scheduling problem for flow-shops with no-wait restrictions, Omega, 43: 96-107. https://doi.org/10.1016/j.omega.2013.07.001
• Shao, W., Pi, D. ve Shao, Z. (2017). An extended teaching-learning based optimization algorithm for solving no-wait flow shop scheduling problem, Applied Soft Computing, 61: 193-210. https://doi.org/10.1016/j.asoc.2017.08.020
• Strusevich, V.A. (1995). Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds, Discrete Applied Mathematics, 59: 75-86. https://doi.org/10.1016/0166-218X(93)E0153-P
• Sun, X., Geng, X. N., Wang, J. B. ve Liu, F. (2019). Convex resource allocation scheduling in the no-wait flowshop with common flow allowance and learning effect, International Journal of Production Research, 57(6): 1873-1891. https://doi.org/10.1080/00207543.2018.1510559
• Tan, Y., Zhou, M., Zhang, Y., Guo, X., Qi, L. ve Wang, Y. (2020). Hybrid scatter search algorithm for optimal and energy-efficient steelmaking-continuous casting, IEEE Transactions on Automation Science and Engineering, 17(4): 1814-1828. DOI: 10.1109/TASE.2020.2979079
• Tasgetiren, M. F., Yüksel, D., Gao, L., Pan, Q. K. ve Li, P. (2019). A discrete artificial bee colony algorithm for the energy-efficient no-wait flowshop scheduling problem, Procedia Manufacturing, 39: 1223-1231. https://doi.org/10.1016/j.promfg.2020.01.347
• Wang, S. ve Liu, M. (2013). A genetic algorithm for two-stage no-wait hybrid flow shop Scheduling problem, Computers & Operations Research, 40: 1064-1075. doi.org/10.1016/j.cor.2012.10.015
• Wang, S., Liu, M. ve Chu, C. (2015). A genetic algorithm for two-stage no-wait hybrid flow shop Scheduling problem, International Journal of Production Research, 53(4): 1143-1167. https://doi.org/10.1016/j.cor.2012.10.015
• Yang, Y., Li, P., Wang, S., Liu, B. ve Luo, Y. (2017). Scatter search for distributed assembly flowshop scheduling to minimize total tardiness, 2017 IEEE Congress on evolutionary computation (CEC), 861-868. DOI: 10.1109/CEC.2017.7969399
• Zhao, F., He, X. ve Wang, L. (2020). A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem, IEEE Transactions on Cybernetics. DOI: 10.1109/TCYB.2020.3025662
• Zhao, F., He, X., Zhang, Y., Lei, W., Ma, W., Zhang, C. ve Song, H. (2020a). A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems, Applied Intelligence, 50(1): 87-100. https://link.springer.com/article/10.1007/s10489-019-01497-2
• Zhao, F., Zhang, L., Liu, H., Zhang, Y., Ma, W., Zhang, C. ve Song, H. (2019). An improved water wave optimization algorithm with the single wave mechanism for the no-wait flow-shop scheduling problem, Engıneerıng Optımızatıon, 51(10): 1727-1742. doi.org/10.1080/0305215X.2018.1542693
• Zhao, F., Xue, F., Yang, G., Ma, W., Zhang, C. ve Song, H. (2019a). A Fitness Landscape Analysis for the No-Wait Flow Shop Scheduling Problem With Factorial Representation, IEEE Access, 7: 21032-21047. DOI: 10.1109/ACCESS.2019.2896355
• Zhu, H., Luo, N. ve Li, X. (2021). A quantum‐inspired cuckoo co‐evolutionary algorithm for no‐wait flow shop scheduling, IET Collaborative Intelligent Manufacturing. https://doi.org/10.1049/cim2.12002
• Zhu, H., Qi, X., Chen, F., He, X., Chen, L. ve Zhang, Z. (2019). Quantum-inspired cuckoo co-search algorithm for no-wait flow shop scheduling, Applied Intelligence, 49: 791-803. https://link.springer.com/article/10.1007/s10489-018-1285-0