This paper addresses an operating room planning problem with surgical demands from both the elective patients and the non-elective ones. A dynamic waiting list is established to prioritize and manage the patients according to their urgency levels and waiting times. In every decision period, sequential decisions are taken by selecting high-priority patients from the waiting list to be scheduled. With consideration of random arrivals of new patients and uncertain surgery durations, the studied problem is formulated as a novel Markov decision process model with dead ends. The objective is to optimize a combinatorial cost function involving patient waiting times and operating room over-utilizations. Considering that the conventional dynamic programming algorithms have difficulties in coping with large-scale problems, we apply several adapted real-time dynamic programming algorithms to solve the proposed model. In numerical experiments, we firstly apply different algorithms to solve the same instance and compare the computational efficiencies. Then, to evaluate the effects of dead ends on the policy and the computation, we conduct simulations for multiple instances with the same problem scale but different dead ends. Experimental results indicate that incorporating dead ends into the model helps to significantly shorten the patient waiting times and improve the computational efficiency.
Accepté le :
DOI : 10.1051/ro/2018110
Mots-clés : Operating room planning, Markov decision process, dead end, real-time dynamic programming
@article{RO_2019__53_5_1819_0,
author = {Zhang, Jian and Dridi, Mahjoub and El Moudni, Abdellah},
title = {A {Markov} decision model with dead ends for operating room planning considering dynamic patient priority},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1819--1841},
publisher = {EDP-Sciences},
volume = {53},
number = {5},
year = {2019},
doi = {10.1051/ro/2018110},
mrnumber = {4018323},
zbl = {1430.90555},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2018110/}
}
TY - JOUR AU - Zhang, Jian AU - Dridi, Mahjoub AU - El Moudni, Abdellah TI - A Markov decision model with dead ends for operating room planning considering dynamic patient priority JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1819 EP - 1841 VL - 53 IS - 5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018110/ DO - 10.1051/ro/2018110 LA - en ID - RO_2019__53_5_1819_0 ER -
%0 Journal Article %A Zhang, Jian %A Dridi, Mahjoub %A El Moudni, Abdellah %T A Markov decision model with dead ends for operating room planning considering dynamic patient priority %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1819-1841 %V 53 %N 5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018110/ %R 10.1051/ro/2018110 %G en %F RO_2019__53_5_1819_0
Zhang, Jian; Dridi, Mahjoub; El Moudni, Abdellah. A Markov decision model with dead ends for operating room planning considering dynamic patient priority. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1819-1841. doi : 10.1051/ro/2018110. http://www.numdam.org/articles/10.1051/ro/2018110/
, , , and , An intelligent decision support system for the operating theater: a case study. IEEE Trans. Autom. Sci. Eng. 11 (2014) 265–273. | DOI
, , and , Particle swarm optimization-based planning and scheduling for a laminar-flow operating room with downstream resources. Soft Comput. 19 (2015) 2913–2926. | DOI
, , , and , A two level metaheuristic for the operating room scheduling and assignment problem. Comput. Oper. Res. 54 (2015) 21–34. | DOI | MR | Zbl
and , Trade-offs in operating room planning for electives and emergencies: a review. Oper. Res. Health Care 7 (2015) 52–69. | DOI
, , , and , Operating room planning and surgical case scheduling: a review of literature. J. Comb. Optim. 1–49 (2018). | MR
and , An elective surgery scheduling problem considering patient priority. Comput. Oper. Res. 37 (2010) 1091–1099. | DOI | Zbl
, , and , Operating room scheduling and rescheduling: a rolling horizon approach. Flexible Serv. Manuf. J. 28 (2016) 206–232. | DOI
, , , , and , Scheduling operating rooms: achievements, challenges and pitfalls. J. Scheduling 19 (2016) 493–525. | DOI | MR | Zbl
, , and , A stochastic model for operating room planning with elective and emergency demand for surgery. Eur. J. Oper. Res. 185 (2008) 1026–1037. | DOI | MR | Zbl
, and , Comparing two operating-room-allocation policies for elective and emergency surgeries. In: Proceedings of the 2010 Winter Simulation Conference. IEEE (2010) 2364–2374. | DOI
, and , Operating room planning and scheduling: a literature review. Eur. J. Oper. Res. 201 (2010) 921–932. | DOI | Zbl
and , Operational research in the management of the operating theatre: a survey. Health Care Manage. Sci. 14 (2011) 89–114. | DOI
and , Managing a patient waiting list with time-dependent priority and adverse events. RAIRO: OR 48 (2014) 53–74. | DOI | Numdam | MR | Zbl
, Optimal advance scheduling. Manage. Sci. 61 (2015) 1584–1597. | DOI
, , , and , A stochastic optimization and simulation approach for scheduling operating rooms and recovery beds in an orthopedic surgery department. Comput. Ind. Eng. 80 (2015) 72–79. | DOI
and , Different stakeholders’ perspectives for a surgical case assignment problem: deterministic and robust approaches. Eur. J. Oper. Res. 261 (2017) 260–278. | DOI | MR | Zbl
and , An integrated approach for scheduling health care activities in a hospital. Eur. J. Oper. Res. 264 (2018) 756–773. | DOI | MR | Zbl
, , , , and , Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries. Comput. Ind. Eng. 97 (2016) 248–257. | DOI
and , Predictive/reactive planning and scheduling of a surgical suite with emergency patient arrival. J. Med. Syst. 40 (2016) 30. | DOI
, and , A column-generation-based heuristic algorithm for solving operating theater planning problem under stochastic demand and surgery cancellation risk. Int. J. Prod. Econ. 158 (2014) 28–36. | DOI
, and , A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling. INFORMS J. Comput. 28 (2016) 432–448. | DOI | MR | Zbl
, , , and , A hybrid optimization algorithm for surgeries scheduling. Oper. Res. Health Care 8 (2016) 103–114. | DOI
and , Two-stage robust optimization approach to elective surgery and downstream capacity planning. Eur. J. Oper. Res. 260 (2017) 21–40. | DOI | MR | Zbl
, and , Dynamic multipriority patient scheduling for a diagnostic resource. Oper. Res. 56 (2008) 1507–1525. | DOI | MR | Zbl
, , and , Planning and scheduling of semi-urgent surgeries. Health Care Manage. Sci. 13 (2010) 256–267. | DOI
and , Evaluation of optimal scheduling policy for accommodating elective and non-elective surgery via simulation. In: Proceedings of the 2014 Winter Simulation Conference. IEEE Press (2014) 1377–1386. | DOI
and , A simulation based approximate dynamic programming approach to multi-class, multi-resource surgical scheduling. Eur. J. Oper. Res. 245 (2015) 309–319. | DOI | MR | Zbl
, and , A theory of goal-oriented MDPs with dead ends. In: Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence. UAI’12 (2012) 438–447.
, and , Stochastic shortest path MDPs with dead ends. In: ICAPS Heuristics and Search for Domain Independent Planning (HSDIP) Workshop (2012).
and , Dedicated operating room for emergency surgery improves access and efficiency. Can. J. Surgery 56 (2013) 167. | DOI
and , A traffic-light coding system to organize emergency surgery across surgical disciplines. Br. J. Surgery 101 (2014) e134–e140. | DOI
, , , and , Improving operational effectiveness of tactical master plans for emergency and elective patients under stochastic demand and capacitated resources. Eur. J. Oper. Res. 213 (2011) 290–308. | DOI | MR
, , and , Minimizing the waiting time for emergency surgery. Oper. Res. Health Care 1 (2012) 34–44. | DOI
, , and , Assessing the impact of stochasticity for operating theater sizing. Decis. Support Syst. 55 (2013) 616–628. | DOI
, , , and , Prioritizing surgical waiting lists. J. Eval. Clin. Pract. 14 (2008) 59–64. | DOI
, , , , , , , and , A model to prioritize access to elective surgery on the basis of clinical urgency and waiting time. BMC Health Serv. Res. 9 (2009) 1. | DOI
and , Scheduling elective surgery under uncertainty and downstream capacity constraints. Eur. J. Oper. Res. 206 (2010) 642–652. | DOI | MR | Zbl
, and , Modelling and solving generalised operational surgery scheduling problems. Comput. Oper. Res. 66 (2016) 1–11. | DOI | MR | Zbl
, and , Stochastic programming for nurse assignment. Comput. Optim. App. 40 (2008) 321–349. | DOI | MR | Zbl
and , The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care. Eur. J. Oper. Res. 226 (2013) 551–559. | DOI | MR | Zbl
, and , Learning to act using real-time dynamic programming. Artif. Intell. 72 (1995) 81–138. | DOI
and , Labeled RTDP: improving the convergence of real-time dynamic programming. In: Proceedings of Thirteenth International Conference on Automated Planning and Scheduling 3 (2003) 12–21.
, and , Bounded real-time dynamic programming: RTDP with monotone upper bounds and performance guarantees. In: Proceedings of the 22nd International Conference on Machine Learning. ACM (2005) 569–576.
and , Focused real-time dynamic programming for MDPs: squeezing more out of a heuristic. In: Proceedings of the 21st National Conference on Artificial Intelligence. AAAI’06 2 (2006) 1227–1232.
, , and , Bayesian real-time dynamic programming. Proceedings of the 21st International Joint Conference on Artifical Intelligence. IJCAI’09 (2009) 1784–1789.
, and , A stochastic shortest-path MDP model with dead ends for operating rooms planning. In: 2017 23rd International Conference on Automation and Computing (ICAC). IEEE (2017) 1–6.
, , , and , Estimating times of surgeries with two component procedures: comparison of the lognormal and normal models. Anesthesiol. J. Am. Soc. Anesthesiologists 98 (2003) 232–240.
, , and , Stochastic programming analysis and solutions to schedule overcrowded operating rooms in china. Comput. Oper. Res. 74 (2016) 78–91. | DOI | MR | Zbl
and , Planning with Markov decision processes: an AI perspective. Synth. Lect. Artif. Intel. Mach. Learn. 6 (2012) 1–210. | Zbl
, and , Column generation approach to operating theater planning with elective and emergency patients. IIE Trans. 40 (2008) 838–852. | DOI
, , and , Optimal distribution of operating hours over operating rooms using probabilities. Eur. J. Oper. Res. 267 (2018) 1156–1171. | DOI | MR | Zbl
, and , Structural estimation of the newsvendor model: an application to reserving operating room time. Manage. Sci. 54 (2008) 41–55. | DOI
Cité par Sources :
