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

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

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. Ç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
18. 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
19. 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
20. 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
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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
33. 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
34. 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
35. 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
36. 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
37. 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
38. 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
39. 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
40. 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
41. 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
42. 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
43. 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
44. 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
45. 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
46. 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
47. 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
48. 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
49. 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
50. 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
51. 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
52. 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
53. 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
54. 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
55. 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
56. 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
57. 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
58. 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
59. 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
60. 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
61. 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
62. 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
63. 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
64. 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