یک الگوریتم تجزیه Benders برای مسأله یکپارچه‌ی برنامه‌ریزی و زمان‌بندی اتاق عمل با درنظر گرفتن چند شیفت و زمان آماده‌سازی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکترای بهینه‌سازی سیستم‌ها، گروه مهندسی صنایع، دانشکدۀ مهندسی صنایع، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران

2 استادیار گروه سیستم‌های اقتصادی اجتماعی، دانشکدۀ مهندسی صنایع، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران

چکیده

مسأله­‌ی یکپارچه‌­ی برنامه‌­ریزی و زمان‌بندی اتاق عمل یکی از مهم­ترین مسائل بهینه‌­سازی در حوزه‌­ی سلامت می­‌باشد که اخیراً نیز مورد توجه مدیران بیمارستان‌ها قرار گرفته است. در این مقاله مدل برنامه‌ریزی و زمان‌بندی باهدف افزایش درآمد و کاهش هزینه‌­های جاری اتاق عمل و بافرض محدودیت منابع انسانی شامل جراحان و پرستاران و زمان دردسترس برای جراحان پیشنهاد می‌­شود. در این مدل برای استفاده‌ بهینه از ظرفیت اتاق عمل امکان برنامه‌ریزی در طی چند شیفت میسر شده و هزینه‌های جراحی و کادر درمان در هر شیفت لحاظ شده است. همچنین به‌دلیل تنوع در جراحی‌ها و نیاز به آماده‌سازی اتاق عمل‌ زمان آماده‌­سازی اتاق عمل نیز جهت برنامه‌‌ریزی دقیق‌تر درنظر گرفته شده است. به‌دلیل وجود متغیرهای سخت مدل با الگوریتم تجزیه Benders و با نرم‌افزار GAMS برای اندازه‌­های مختلف حل شده است. درنظر گرفتن چند شیفت امکان برنامه‌­ریزی برای تعداد بالای جراحی را فراهم کرده است. نتایج محاسباتی نشان می‌­دهد به‌دلیل میسر بودن امکان برنامه‌­ریزی در چند شیفت میزان تابع هدف مسأله با استفاده از الگوریتم تجزیه Benders نسبت به نرم‌افزار GAMS برای مسائل با اندازه بزرگتر بهبودیافته و منجربه جواب بهینه با درآمد بیشتر و برنامه‌­­ریزی کارآمدتر اتاق عمل شده است. ازطرفی زمان حل نیز با الگوریتم تجزیه Benders کاهش یافته است. 

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

A Benders Decomposition Algorithm for Integrated Operating Room Planning and Scheduling Problem by Considering Multiple Shifts and Preparation Time

نویسندگان [English]

  • Elham Abutalebi 1
  • Seyed Javad Hosseininezhad 2
1 Phd student of Systems Optimization, Industrial Engineering Group, Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran
2 . Assistant Professor, Social Economic Systems Group, Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran
چکیده [English]

The integrated operating room planning and scheduling problem is one of the most important optimization problems in the field of health, which has recently attracted the attention of hospital managers. In this article, a planning and scheduling model is proposed with the aim of increasing revenue and reducing current costs of the operating room and considering human resources including surgeons and nurses and available time for surgeons. In this model, for the optimal use of the capacity of the operating room, it is possible to plan during several shifts, and the costs of surgery and staffs are included in each shift. Also, due to the variety of surgeries and the need to prepare the operating room, the preparation time of the operating room is also considered for more accurate planning. Due to the complicating variables, the model has been solved by Benders decomposition algorithm and with GAMS software for different sizes. Considering multiple shifts has made it to plan for a high number of surgeries. On the one hand, because of planning in several shifts, the results show that the amount of the objective function has been improved by using the Benders decomposition compared to the GAMS software for larger size problems and has led to an optimal solution with more income and more efficient planning of the operating room. On the other hand, the solution time is reduced by this algorithm.

کلیدواژه‌ها [English]

  • The Integrated Operating Room Planning and Scheduling Problem
  • Benders Decomposition
  • Preparation Time

مراجع

  •  

    • Doulabi, S., L.-M. Rousseau, and G. Pesant, A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling. INFORMS Journal on Computing, 2016. 28: p. 432-448. https://doi.org/10.1287/ijoc.2015.0686
    • Molina-Pariente, J.M., V. Fernandez-Viagas, and J. Framinan, Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations. Computers & Industrial Engineering, 2015. 82: p. 8-20. https://doi.org/10.1016/j.cie.2015.01.006
    • Latorre-Núñez, G., et al., Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries. Computers & Industrial Engineering, 2016. 97. https://doi.org/10.1016/j.cie.2016.05.016
    • Guerriero, F. and R. Guido, Operational research in the management of the operating theatre: A survey. Health care management science, 2011. 14: p. 89-114. https://doi.org/10.1007/s10729-010-9143-6
    • Gabel, R.A., Operating Room Management. 1999: Elsevier - Health Sciences Division.
    • Cardoen, B., E. Demeulemeester, and J. Beliën, Operating room planning and scheduling: A literature review. European Journal of Operational Research, 2010. 201(3): p. 921-932. https://doi.org/10.1016/j.ejor.2009.04.011
    • Blake, J., F. Dexter, and J. Donald, Operating Room Managers??? Use of Integer Programming for Assigning Block Time to Surgical Groups: A Case Study. Anesthesia and analgesia, 2002. 94: p. 143-8, table of contents. https://doi.org/10.1097/00000539-200201000-00027
    • Fei, H., N. Meskens, and C. Chu, A planning and scheduling problem for an operating theatre using an open scheduling strategy. Computers & Industrial Engineering, 2010. 58(2): p. 221-230. https://doi.org/10.1016/j.cie.2009.02.012
    • Younespour, M., et al., Using mixed integer programming and constraint programming for operating rooms scheduling with modified block strategy. Operations Research for Health Care, 2019. 23. https://doi.org/10.1016/j.orhc.2019.100220
    • Bargetto, R., T. Garaix, and X. Xie, A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints. Computers & Operations Research, 2023. 152: p. 106136. https://doi.org/10.1016/j.cor.2022.106136
    • Roland, B., C.d. Martinelly, and F. Riane. Operating Theatre Optimization : A Resource-Constrained Based Solving Approach. in 2006 International Conference on Service Systems and Service Management. 2006. https://doi.org/10.1109/ICSSSM.2006.320503
    • Roland, B., et al., Scheduling an operating theatre under human resource constraints. Computers & Industrial Engineering, 2010. 58: p. 212-220. https://doi.org/10.1016/j.cie.2009.01.005
    • Marques, I., M.E. Captivo, and M. Vaz Pato, An integer programming approach to elective surgery scheduling. OR Spectrum, 2012. 34(2): p. 407-427. https://doi.org/10.1007/s00291-011-0279-7
    • Marques, I., M.E. Captivo, and M. Vaz Pato, Scheduling elective surgeries in a Portuguese hospital using a genetic heuristic. Operations Research for Health Care, 2014. 3(2): p. 59-72. ttps://doi.org/10.1016/j.orhc.2013.12.001
    • Guido, R. and D. Conforti, A hybrid genetic approach for solving an integrated multi-objective operating room planning and scheduling problem. Computers & Operations Research, 2017. 87: p. 270-282. https://doi.org/10.1016/j.cor.2016.11.009
    • Akbarzadeh, B., et al., A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering. Journal of Scheduling, 2020. 23(2): p. 265-288. https://doi.org/10.1007/s10951-020-00639-6
    • Breuer, D.J., et al., Robust combined operating room planning and personnel scheduling under uncertainty. Operations Research for Health Care, 2020. 27: p. 100276. https://doi.org/10.1016/j.orhc.2020.100276
    • Mancilla, C. and R.H. Storer, Stochastic sequencing and scheduling of an operating room. Theses and Dissertations, Lehigh University, Department of Industrial and Systems Engineering (November 14, 2009), 2009.
    • Roshanaei, V., et al., Collaborative operating room planning and scheduling. INFORMS Journal on Computing, 2017. 29(3): p. 558-580. https://doi.org/10.1287/ijoc.2017.0745
    • Kamran, M.A., B. Karimi, and N. Dellaert, Uncertainty in advance scheduling problem in operating room planning. Computers & Industrial Engineering, 2018. 126: p. 252-268. https://doi.org/10.1016/j.cie.2018.09.030
    • Kamran, M.A., B. Karimi, and N. Dellaert, A column-generation-heuristic-based benders’ decomposition for solving adaptive allocation scheduling of patients in operating rooms. Computers & Industrial Engineering, 2020. 148: p. 106698. https://doi.org/10.1016/j.cie.2020.106698
    • Ghandehari, N. and K. Kianfar, Mixed-integer linear programming, constraint programming and column generation approaches for operating room planning under block strategy. Applied Mathematical Modelling, 2022. 105: p. 438-453. https://doi.org/10.1016/j.apm.2022.01.001
    • Gür, Ş., et al., Operating room scheduling with surgical team: a new approach with constraint programming and goal programming. Central European Journal of Operations Research, 2023. 31(4): p. 1061-1085. https://doi.org/10.1007/s10100-022-00835-z
    • Tayyab, A., S. Ullah, and M.F. Baki, An outer approximation method for scheduling elective surgeries with sequence dependent setup times to multiple operating rooms. Mathematics, 2023. 11(11): p. 2441. https://doi.org/10.3390/math11112441
    • Karimi, N. and H. Davoudpour, A Benders decomposition algorithm for multi-factory scheduling problem with batch delivery. Scientia Iranica, 2017. 24(2): p. 823-833 https://doi.org/10.24200/sci.2017.4064
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 12، شماره 24
شهریور 1403
صفحه 49-61

فایل ها

هم رسانی

ارجاع به این مقاله

آمار