Hibrit Genetik Algoritma Kullanarak Ameliyat Odası Çizelgeleme

Year 2022, , 255 - 274, 31.01.2022

Tunahan Timuçin , Serdar Biroğul

https://doi.org/10.29130/dubited.946453

Abstract

Günümüzün en önemli kurumlarının başında hastaneler gelmektedir. Hastaneler için ise ameliyathanelerin verimli kullanılması büyük önem taşımaktadır. Ameliyathanelerin verimli kullanımı çözülmesi gereken bir problemdir. Ameliyat odası çizelgeleme problemi, kısıt sayısı çok fazla olan, oldukça karmaşık bir problemdir. Bu tip problemler, NP-Hard tipi problem olarak adlandırılmaktadır. NP-Hard tipi problemler polinomik değerlerden oluşmazlar. Bu yüzden, bu problemlerin çözümü de çok karmaşık ve zordur. Polinomik değerlerden oluşan çözümler mevcut matematiksel yöntemlerle etkili bir şekilde çözülebilmektedir. Ancak NP-hard tipi problemlerin çözümü için daha etkili algoritmalara ihtiyaç duyulmuştur. Yapılan çalışmalar sonucunda, Genetik Algoritma (GA), Parçacık Sürüsü Optimizasyonu, Benzetilmiş Tavlama, Tabu Arama Algoritması gibi sezgisel veya meta-sezgisel çok sayıda algoritma, NP-Hard problemlerin karmaşıklığını çözmek için geliştirilmiştir. Bu makalede, hibrit bir genetik algoritma ile ameliyat odası çizelgeleme problemi çözüme ulaştırılmıştır. Bu çözümde, algoritmanın, ameliyathane parametrelerinden olan, cerrah sayısı, ameliyat odası sayısı ve ameliyathane rezervasyon sayısının değişimlerinde, çözüm alanını nasıl etkilediği gösterilmiştir. Geliştirilen yazılımda, son kullanıcının rahat kullanımını sağlamak için, C# programlama dili tercih edilmiştir.

Keywords

Ameliyat odası çizelgeleme, Genetik algoritma, Tamir operatörü, Kısıtlı optimizasyon

Operating Room Scheduling by Using Hybrid Genetic Algorithm

Abstract

Hospitals are among the most important institutions of today. For hospitals, efficient use of operating rooms is of great importance. Efficient use of operating rooms is a problem that needs to be solved. The operating room scheduling problem is a very complex problem with large number of constraints. This type of problem called as NP-Hard type problem. NP-Hard type problems do not consist of polynomial values. Therefore, the solution of these problems is very complex and difficult. Solutions consisting of polynomial values can be solved effectively with existing mathematical methods. However, more effective algorithms were needed to solve NP-hard type problems. As a result of the studies, many heuristic, meta-heuristic algorithms such as Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Taboo Search Algorithm have been developed to solve the complexity of NP-Hard problems. In this article, the operating room scheduling problem solved with a hybrid genetic algorithm. In this solution, it shows how the algorithm affects the solution area in the changes in the number of surgeons, operating rooms and operating room reservations, which are among the operating room parameters. In the developed software, C# programming language has been preferred in order to provide comfortable use of the end user.

Keywords

Operating Room Scheduling, Genetic Algorithm, Repair Operator, Constrained Optimization

References

• [1] Sağlık Bakanlığı. (2018, 27 Ekim). A-b-c Grubu Toplam Ameliyatlar, [Çevrimiçi]. Erişim: http://rapor.saglik.gov.tr/istatistik/rapor/index.php
• [2] M. Dorigo and T.Stützle, "Ant colony optimization for NP-Hard problems," in Ant Colony Optimization, 1st ed., ch.5, Boston, MA, USA: Springer, 2004, pp.167-181.
• [3] O. Engin ve A. Fığlalı, “Akış tipi çizelgeleme problemlerinin genetik algoritma yardımı ile çözümünde uygun çaprazlama operatörünün belirlenmesi,” Doğuş Üniversitesi Dergisi., c. 3, s. 2, ss. 27-35, 2002.
• [4] F. Guerriero and R. Guido, “Operational research in the management of the operating theatre: A survey,” Health Care Management Science, vol. 14, no 1, pp. 89–114, 2011.
• [5] B. Cardoen, E. Demeulemeester and J. Beliën, “Operating room planning and scheduling: A literature review,” European Journal Operational Research, vol. 201, no 3, pp. 921–932, 2010.
• [6] S. Brailsford and J. Vissers, “OR in healthcare: A European perspective,” European Journal Operational Research, vol. 212, no 2, pp. 223–234, 2011.
• [7] Z. Y. Abdelrasol, N. Harraz and A. Eltawil, “A proposed solution framework for the operating room scheduling problems,” World Congress on Engineering and Computer Science, San Francisco, USA, 2013, pp. 23-25
• [8] P. Patterson, “What makes a well-oiled scheduling system,” OR Manager, vol. 12, no 9, pp. 19–23, 1996.
• [9] I. Marques, M. E. Captivo and M. V. Pato, “An integer programming approach to elective surgery scheduling,” Operations Research-Spectrum, vol. 34, no 2, pp. 407–27, 2012.
• [10] D. Conforti, F. Guerriero and R.Guido, “A multi-objective block scheduling model for the management of surgical operating rooms: New solution approaches via genetic algorithms,” in Proc. IEEE Workshop on Health Care Management (WHCM), Venice, Italy, 2010, pp. 1–5.
• [11] I. Marques, M. E. Captivo and M. V. Pato, “Planning elective surgeries in a portuguese hospital: Study of different mutation rules for a genetic heuristic,” Lect Notes Management Science, Netherlands, 2012, pp. 238–243.
• [12] M. Khambhammettu and M. Persson, “Analyzing a decision support system for resource planning and surgery scheduling,” Procedia Computer Science, vol. 100, pp. 532–538, 2016.
• [13] J. M. Molina-Pariente, E. W. Hans and J. M. Framinan, “New heuristics for planning operating rooms,” Computer & Industrial Engineering, vol. 90, pp. 429–443, 2015.
• [14] G. Rosita and D. Conforti, “A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem,” Computer Operation Research, vol. 87, pp. 270–282, 2017.
• [15] W. Xiang, J. Yin and G. Lim, “An ant colony optimization approach for solving an operating room surgery scheduling problem,” Computer & Industrial Engineering, vol. 85, pp. 335–345, 2015.
• [16] G. Latorre-Nunez, A. Lüer-Villagra, V. Mairanov, C. Obreque, F. Ramis and L. Neriz, “Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries,” Computer & Industrial Engineering,vol. 97, pp. 248–257, 2016.
• [17] A. Bouguerra, C. Sauvey and N. Sauer, “Mathematical model for maximizing operating rooms utilization,” IFAC-PapersOnLine, vol. 48, no 3, pp. 118–123, 2015.
• [18] H. Saadouli, B. Jerbi, A. Dammak, L. Masmoudi and A. Bouaziz, “A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department,” Computer & Industrial Engineering, vol. 80, pp. 72–79, 2015.
• [19] W. Xiang, J. Yin and G. Lim, “A short-term operating room surgery scheduling problem integrating multiple nurses roster constraints,” Artificial Intelligence in Medicine, vol. 63, no 2, pp. 91–106, 2015.
• [20] L. Paolo, R. Aringhieri, S. Patrick, T. Elena and T. Angela, “A hybrid optimization algorithm for surgeries scheduling,” Operational Research for Health Care, vol. 8, pp. 103–114, 2016.
• [21] J. Razmi, M. S. Yousefi and M. Barati, “A stochastic model for operating room unique equipment planning under uncertainty,” IFAC-PapersOnLine, vol. 48, no 3, pp. 1796–1801, 2015.
• [22] T. Wang, N. Meskens and D. Duvivier, “Scheduling operating theatres: Mixed integer programming vs. constraint programming,” Europian Journal of Operational Research, vol. 247, no 2, pp. 401–413, 2015.
• [23] A. Riise, C. Mannino and E. K. Burke, “Modelling and solving generalised operational surgery scheduling problems,” Computers & Operations Research, vol. 66, pp. 1–11, 2016.
• [24] M. Dios, J. M. Molina-Pariente, V. Fernandez-Viagas, J. L. Andrade-Pineda and J. M. Framinan, “A decision support system for operating room scheduling,” Computer & Industrial Engineering, vol. 88, pp. 430–443, 2015.
• [25] A. W. Murray, S. T. Beaman, C. W. Kampik and J. J. Quinlan, “Simulation in the operating room,” Best Practice & Research Clinical Anaesthesiology, vol. 29, no 1, pp. 41–50, 2015.
• [26] P. M. Castro and I. Marques, “Operating room scheduling with generalized disjunctive programming,” Computers & Operations Research, vol. 64, pp. 262–273, 2015.
• [27] A. Abedini, H. Ye and W. Li, “Operating room planning under surgery type and priority constraints,” Procedia Manufacturing, vol. 5, pp. 15–25, 2016.
• [28] B. Beroule, O. Grunder, O. Barakat, O. Aujoulat and H. Lustig, “Operating room scheduling including medical devices sterilization: towards a transverse logistic,” IFAC-PapersOnLine, vol. 49, no 12, pp. 1146–1151, 2016.
• [29] L.E.M. Alameda and A. Macario, “Advances in operating room management, the role of operating room director,” Revista Espanola de Anestesiologia y Reanimacion (English Ed), vol. 64, no 3, pp. 121–124, 2017.
• [30] E. van Veen-Berkx, S. G. Elkhuizen, B. Kuijper and G. Kazemier, “Dedicated operating room for emergency surgery generates more utilization, less overtime, and less cancellations,” The American Journal of Surgery, vol. 211, no 1, pp. 122–128, 2016.
• [31] C. V. Riet and E. Demeulemeester, “Trade-offs in operating room planning for electives and emergencies: A review,” Operational Research for Health Care, vol. 7, pp. 52–69, 2015.
• [32] C. L. Siqueira, E. F. Arruda, L. Bahiense, G. L. Bahr and G. R. Motta, “Long-term integrated surgery room optimization and recovery ward planning, with a case study in the Brazilian National Institute of Traumatology and Orthopedics (INTO),” Europian Journal of Operational Research, vol. 264, no 3, pp. 870–883, 2018.
• [33] V. Roshanaei, C. Luong, D. M. Aleman and D. Urbach, “Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling,” Europian Journal of Operational Research, vol. 257, no 2, pp. 439–455, 2017.
• [34] R. Aringhieri, P. Landa, P. Soriano, E. Taffani and A. Testi, “A two level metaheuristic for the operating room scheduling and assignment problem,” Computers & Operations Research, vol. 54, pp. 21–34, 2015.
• [35] G. Xiao, W. van Jaarsveld, M. Dong and J. van De Klundert, “Stochastic programming analysis and solutions to schedule overcrowded operating rooms in China,” Computers & Operations Research, vol. 74, pp. 78–91, 2016.
• [36] A. Jebali and A. Diabat, “A chance-constrained operating room planning with elective and emergency cases under downstream capacity constraints,” Computer & Industrial Engineering, vol. 114, pp. 329–344, 2017.
• [37] H. John Henry, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Oxford, England: U Michigan Press, 1975.
• [38] D. E. Golberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Boston, MA: Addison-Wesley Longman, 1989.
• [39] J. R.Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA : MIT Press, 1992.
• [40] T. Timucin and S. Birogul, “Implementation of Operating Room Scheduling with Genetic Algorithm and the Importance of Repair Operator,” 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), IEEE, 2018, pp. 1-6.
• [41] T. Timucin and S. Birogul, “Effect the Number of Reservations on Implementation of Operating Room Scheduling with Genetic Algorithm” Artificial Intelligence and Applied Mathematics in Engineering (ICAIAME), Springer, Cham, 2019, pp. 252-265.