×

Integrated multiresource capacity planning and multitype patient scheduling. (English) Zbl 1492.90063

Summary: The joint optimization problem of multiresource capacity planning and multitype patient scheduling under uncertain demands and random capacity consumption poses a significant computational challenge. The common practice in solving this problem is to first identify capacity levels and then determine patient scheduling decisions separately, which typically leads to suboptimal decisions that often result in ineffective outcomes of care. In order to overcome these inefficiencies, in this paper, we propose a novel two-stage stochastic optimization model that integrates these two decisions, which can lower costs by exploring the coupling relationship between patient scheduling and capacity configuration. The patient scheduling problem is modeled as a Markov decision process. We first analyze the properties for the multitype patient case under specific assumptions and then establish structural properties of the optimal scheduling policy for the one-type patient case. Based on these findings, we propose optimal solution algorithms to solve the joint optimization problem for this special case. Because it is intractable to solve the original two-stage problem for a general multitype system with large state space, we propose a heuristic policy and a two-stage stochastic mixed-integer programming model solved by the Benders decomposition algorithm, which is further improved by combining an approximate linear program and the look-ahead strategy. To illustrate the efficiency of our approaches and draw managerial insights, we apply our solutions to a data set from the day surgery center of a large public hospital in Shanghai, China. The results show that the joint optimization of capacity planning and patient scheduling could significantly improve the performance. Furthermore, our model can be applied to a rolling-horizon framework to optimize dynamic patient scheduling decisions. Through extensive numerical analyses, we demonstrate that our approaches yield good performances, as measured by the gap against an upper bound, and that these approaches outperform several benchmark policies.
Summary of contribution: First, this paper investigates the joint optimization problem of multiresource capacity planning and multitype patient scheduling under uncertain demands and random capacity consumption, which poses a significant computational challenge. It belongs to the scope of computing and operations research. Second, this paper formulates a mathematical model, establishes optimality properties, proposes solution algorithms, and performs extensive numerical experiments using real-world data. This work includes aspects of dynamic stochastic control, computing algorithms, and experiments. Moreover, this paper is motivated by a practical problem (joint management of capacity planning and patient scheduling in the day surgery center) in our cooperative hospital, which is also key to numerous other applications, for example, the make-to-order manufacturing systems and computing facility systems. By using the optimality properties, solution algorithms, and management insights derived in this paper, the practitioners can be equipped with a decision support tool for efficient and effective operation decisions.

MSC:

90B35 Deterministic scheduling theory in operations research
90C15 Stochastic programming
90C40 Markov and semi-Markov decision processes
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi-Javid A, Jalali Z, Klassen KJ (2017) Outpatient appointment systems in healthcare: A review of optimization studies. Eur. J. Oper. Res. 258(1):3-34.Crossref, Google Scholar · Zbl 1380.90106 · doi:10.1016/j.ejor.2016.06.064
[2] Ahmed S (2010) Two-Stage Stochastic Integer Programming: A Brief Introduction, Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Google Scholar
[3] Akcali E, Côté MJ, Lin C (2006) A network flow approach to optimizing hospital bed capacity decisions. Health Care Management Sci. 9(4):391-404.Crossref, Google Scholar · doi:10.1007/s10729-006-0002-4
[4] Alfonso E, Xie X, Augusto V (2015) A simulation-optimization approach for capacity planning and appointment scheduling of blood donors based on mathematical programming representation of event dynamics. 2015 IEEE Internat. Conf. Automation Sci. Engrg (CASE) (IEEE Press, New York), 728-733.Google Scholar
[5] Asamov T, Powell WB (2018) Regularized decomposition of high-dimensional multistage stochastic programs with Markov uncertainty. SIAM J. Optim. 28(1):575-595.Crossref, Google Scholar · Zbl 1395.90190 · doi:10.1137/16M1072231
[6] Ayvaz N, Huh WT (2010) Allocation of hospital capacity to multiple types of patients. J. Revenue Pricing Management 9(5):386-398.Crossref, Google Scholar · doi:10.1057/rpm.2010.30
[7] Barz C, Rajaram K (2015) Elective patient admission and scheduling under multiple resource constraints. Production Oper. Management 24(12):1907-1930.Crossref, Google Scholar · doi:10.1111/poms.12395
[8] Bassamboo A, Harrison JM, Zeevi A (2006) Design and control of a large call center: Asymptotic analysis of an lp-based method. Oper. Res. 54(3):419-435.Link, Google Scholar · Zbl 1167.90528
[9] Ben Abdelaziz F, Masmoudi M (2012) A multiobjective stochastic program for hospital bed planning. J. Oper. Res. Soc. 63(4):530-538.Crossref, Google Scholar · doi:10.1057/jors.2011.39
[10] Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[11] Bodur M, Luedtke JR (2016) Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Management. Sci. 63(7):2073-2091.Link, Google Scholar
[12] Brailsford S, Vissers J (2011) Or in healthcare: A European perspective. Eur. J. Oper. Res. 212(2):223-234.Crossref, Google Scholar · doi:10.1016/j.ejor.2010.10.026
[13] Bretthauer KM, Heese HS, Pun H, Coe E (2011) Blocking in healthcare operations: A new heuristic and an application. Production Oper. Management 20(3):375-391.Crossref, Google Scholar · doi:10.1111/j.1937-5956.2011.01230.x
[14] Carø ECC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1-2):37-45.Crossref, Google Scholar · Zbl 1063.90037 · doi:10.1016/S0167-6377(98)00050-9
[15] Cayirli T, Veral E (2003) Outpatient scheduling in healthcare: A review of literature. Production Oper. Management 12(4):519-549.Crossref, Google Scholar · doi:10.1111/j.1937-5956.2003.tb00218.x
[16] Chao X, Chen H, Zheng S (2009) Dynamic capacity expansion for a service firm with capacity deterioration and supply uncertainty. Oper. Res. 57(1):82-93.Link, Google Scholar · Zbl 1181.90174
[17] Chen X, Pang Z, Pan L (2014) Coordinating inventory control and pricing strategies for perishable products. Oper. Res. 62(2):284-300.Link, Google Scholar · Zbl 1302.91097
[18] Cho E, Lee NJ, Kim EY, Kim S, Lee K, Park KO, Sung YH (2016) Nurse staffing level and overtime associated with patient safety, quality of care, and care left undone in hospitals: A cross-sectional study. Internat. J. Nursing Stud. 60:263-271.Crossref, Google Scholar · doi:10.1016/j.ijnurstu.2016.05.009
[19] Dai J, Shi P (2019) Inpatient overflow: An approximate dynamic programming approach. Manufacturing Service Oper. Management 21(4):894-911.Link, Google Scholar
[20] Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4-part-1):802-816.Google Scholar · Zbl 1228.90065
[21] Diamant A, Milner J, Quereshy F (2018) Dynamic patient scheduling for multi-appointment healthcare programs. Production Oper. Management 27(1):58-79.Crossref, Google Scholar · doi:10.1111/poms.12783
[22] Doulabi SHH (2017) Decomposition-based integer programming, stochastic programming, and robust optimization methods for healthcare planning, scheduling, and routing problems. PhD thesis, Ecole Polytechnique, Montreal.Google Scholar
[23] Easton FF, Rossin DF (1996) A stochastic goal program for employee scheduling. Decision Sci. 27(3):541-568.Crossref, Google Scholar · doi:10.1111/j.1540-5915.1996.tb01825.x
[24] Erdogan SA, Denton B (2013) Dynamic appointment scheduling of a stochastic server with uncertain demand. INFORMS J. Comput. 25(1):116-132.Link, Google Scholar
[25] Feldman J, Liu N, Topaloglu H, Ziya S (2014) Appointment scheduling under patient preference and no-show behavior. Oper. Res. 62(4):794-811.Link, Google Scholar · Zbl 1302.90096
[26] Fu J, Sun W, Wang Y, Yang X, Wang L (2013) Improving job satisfaction of Chinese doctors: The positive effects of perceived organizational support and psychological capital. Public Health 127(10):946-951.Crossref, Google Scholar · doi:10.1016/j.puhe.2012.12.017
[27] Geng N, Xie X (2016) Optimal dynamic outpatient scheduling for a diagnostic facility with two waiting time targets. IEEE Trans. Automatic Control 61(12):3725-3739.Crossref, Google Scholar · Zbl 1359.90042 · doi:10.1109/TAC.2016.2523882
[28] Gerchak Y, Gupta D, Henig M (1996) Reservation planning for elective surgery under uncertain demand for emergency surgery. Management Sci. 42(3):321-334.Link, Google Scholar · Zbl 0884.90106
[29] Green LV (2005) Capacity planning and management in hospitals. Brandeau ML, Sainfort F, Pierskalla WP, eds. Operations Research and Health Care, International Series in Operations Research & Management Science, vol. 70 (Springer, Boston), 15-41.Google Scholar
[30] Green LV, Kolesar PJ, Whitt W (2007) Coping with time-varying demand when setting staffing requirements for a service system. Production Oper. Management 16(1):13-39.Crossref, Google Scholar · doi:10.1111/j.1937-5956.2007.tb00164.x
[31] Green LV, Savin S, Wang B (2006) Managing patient service in a diagnostic medical facility. Oper. Res. 54(1):11-25.Link, Google Scholar · Zbl 1167.90562
[32] Griffiths JD, Price-Lloyd N, Smithies M, Williams JE (2005) Modelling the requirement for supplementary nurses in an intensive care unit. J. Oper. Res. Soc. 56(2):126-133.Crossref, Google Scholar · Zbl 1089.90512 · doi:10.1057/palgrave.jors.2601882
[33] Griffiths P, Dall’Ora C, Simon M, Ball J, Lindqvist R, Rafferty AM, Schoonhoven L, Tishelman C, Aiken LH (2014) Nurses’ shift length and overtime working in 12 European countries: The association with perceived quality of care and patient safety. Medical Care 52(11):975.Crossref, Google Scholar · doi:10.1097/MLR.0000000000000233
[34] Gupta D, Denton B (2008) Appointment scheduling in healthcare: Challenges and opportunities. IIE Trans. 40(9):800-819.Crossref, Google Scholar · doi:10.1080/07408170802165880
[35] Harper PR, Shahani A (2002) Modelling for the planning and management of bed capacities in hospitals. J. Oper. Res. Soc. 53(1):11-18.Crossref, Google Scholar · Zbl 1138.90415 · doi:10.1057/palgrave/jors/2601278
[36] Helm JE, AhmadBeygi S, Van Oyen MP (2011) Design and analysis of hospital admission control for operational effectiveness. Production Oper. Management 20(3):359-374.Crossref, Google Scholar · doi:10.1111/j.1937-5956.2011.01231.x
[37] Higle JL, Sen S (1991) Stochastic decomposition: An algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16(3):650-669.Link, Google Scholar · Zbl 0746.90045
[38] Huh WT, Janakiraman G (2010) On the optimal policy structure in serial inventory systems with lost sales. Oper. Res. 58(2):486-491.Link, Google Scholar · Zbl 1226.90012
[39] Huh WT, Liu N, Truong VA (2013) Multiresource allocation scheduling in dynamic environments. Manufacturing Service Oper. Management 15(2):280-291.Link, Google Scholar
[40] Izady N (2019) An integrated approach to demand and capacity planning in outpatient clinics. Eur. J. Oper. Res. 279(2):645-656.Crossref, Google Scholar · Zbl 1430.90194 · doi:10.1016/j.ejor.2019.06.001
[41] Jiang R, Shen S, Zhang Y (2017) Integer programming approaches for appointment scheduling with random no-shows and service durations. Oper. Res. 65(6):1638-1656.Link, Google Scholar · Zbl 1382.90042
[42] Kang K, Shanthikumar JG, Altinkemer K (2016) Postponable acceptance and assignment: A stochastic dynamic programming approach. Manufacturing Service Oper. Management 18(4):493-508.Link, Google Scholar
[43] Kao EPC, Queyranne M (1985) Budgeting costs of nursing in a hospital. Management Sci. 31(5):608-621.Link, Google Scholar
[44] Kim K, Mehrotra S (2015) A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management. Oper. Res. 63(6):1431-1451.Link, Google Scholar · Zbl 1334.90092
[45] Kleywegt AJ, Shapiro A, Homem-De-Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479-502.Crossref, Google Scholar · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[46] Li Q, Yu P (2014) Multimodularity and its applications in three stochastic dynamic inventory problems. Manufacturing Service Oper. Management 16(3):455-463.Link, Google Scholar
[47] Li N, Zhao M, Zhang Y, Luo CZ, Chen, LH, Zhang H, Ma J (2009) Deviation between cost and government mandated price in bed utilization in public hospitals and corresponding strategy. J. Shanghai Jiaotong Univ. (Medical Sci.) 29(3):264-267.Google Scholar
[48] Liu N, Ziya S, Kulkarni VG (2010) Dynamic scheduling of outpatient appointments under patient no-shows and cancellations. Manufacturing Service Oper. Management 12(2):347-364.Link, Google Scholar
[49] Liu N, Truong VA, Wang X, Anderson BR (2019) Integrated scheduling and capacity planning with considerations for patients’ length-of-stays. Production Oper. Management 28(7):1735-1756.Crossref, Google Scholar · doi:10.1111/poms.13012
[50] Lu M, Chen Z, Shen S (2017) Optimizing the profitability and quality of service in carshare systems under demand uncertainty. Manufacturing Service Oper. Management 20(2):162-180.Link, Google Scholar
[51] Maenhout B, Vanhoucke M (2013) An integrated nurse staffing and scheduling analysis for longer-term nursing staff allocation problems. Omega 41(2):485-499.Crossref, Google Scholar · doi:10.1016/j.omega.2012.01.002
[52] Mak HY, Rong Y, Zhang J (2014) Appointment scheduling with limited distributional information. Management Sci. 61(2):316-334.Link, Google Scholar
[53] Min D, Yih Y (2010a) An elective surgery scheduling problem considering patient priority. Comput. Oper. Res. 37(6):1091-1099.Crossref, Google Scholar · Zbl 1178.90158 · doi:10.1016/j.cor.2009.09.016
[54] Min D, Yih Y (2014) Managing a patient waiting list with time-dependent priority and adverse events. RAIRO Oper. Res. 48(1):53-74.Crossref, Google Scholar · Zbl 1288.90121 · doi:10.1051/ro/2013047
[55] Min D, Yih Y (2010b) Scheduling elective surgery under uncertainty and downstream capacity constraints. Eur. J. Oper. Res. 206(3):642-652.Crossref, Google Scholar · Zbl 1188.90158 · doi:10.1016/j.ejor.2010.03.014
[56] Nunes LGN, de Carvalho SV, Rodrigues Rd CM (2009) Markov decision process applied to the control of hospital elective admissions. Artificial Intelligence Medicine 47(2):159-171.Crossref, Google Scholar · doi:10.1016/j.artmed.2009.07.003
[57] Organization for Economic Cooperation and Development (2019) OECD health statistics 2019. Accessed October 10, 2019, http://www.oecd.org/health/health-data.htm.Google Scholar
[58] Patrick J (2012) A Markov decision model for determining optimal outpatient scheduling. Health Care Management Sci. 15(2):91-102.Crossref, Google Scholar · doi:10.1007/s10729-011-9185-4
[59] Patrick J, Puterman ML, Queyranne M (2008) Dynamic multipriority patient scheduling for a diagnostic resource. Oper. Res. 56(6):1507-1525.Link, Google Scholar · Zbl 1167.90675
[60] Pereira MV, Pinto LM (1991) Multi-stage stochastic optimization applied to energy planning. Math. Programming 52(1-3):359-375.Crossref, Google Scholar · Zbl 0749.90057 · doi:10.1007/BF01582895
[61] Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar · Zbl 1156.90021 · doi:10.1002/9780470182963
[62] Powell WB (2014) Clearing the jungle of stochastic optimization. Newman A, Leung A, eds. Bridging Data and Decisions, INFORMS Tutorials in Operations Research (INFORMS, Catonsville, MD), 109-137.Google Scholar
[63] Punnakitikashem P, Rosenberber JM, Buckley-Behan DF (2013) A stochastic programming approach for integrated nurse staffing and assignment. IIE Trans. 45(10):1059-1076.Crossref, Google Scholar · doi:10.1080/0740817X.2012.763002
[64] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, Hoboken, NJ).Google Scholar
[65] Rais A, Viana A (2011) Operations research in healthcare: A survey. Internat. Trans. Oper. Res. 18(1):1-31.Crossref, Google Scholar · doi:10.1111/j.1475-3995.2010.00767.x
[66] Samiedaluie S, Kucukyazici B, Verter V, Zhang D (2017) Managing patient admissions in a neurology ward. Oper. Res. 65(3):635-656.Link, Google Scholar · Zbl 1387.90269
[67] Saure A, Patrick J, Tyldesley S, Puterman ML (2012) Dynamic multi-appointment patient scheduling for radiation therapy. Eur. J. Oper. Res. 223(2):573-584.Crossref, Google Scholar · Zbl 1292.90133 · doi:10.1016/j.ejor.2012.06.046
[68] Sen S (2005) Algorithms for stochastic mixed-integer programming models. Handbook Oper. Res. Management Sci. 12:515-558.Google Scholar · Zbl 1172.90457
[69] Sen S, Zhou Z (2014) Multistage stochastic decomposition: A bridge between stochastic programming and approximate dynamic programming. SIAM J. Optim. 24(1):127-153.Crossref, Google Scholar · Zbl 1291.90153 · doi:10.1137/120864854
[70] Simchi-Levi D, Chen X, Julien B (2014) The Logic of Logistics Theory, Algorithms, and Applications for Logistics Management (Springer Science & Business Media, New York).Google Scholar · Zbl 1327.90020
[71] Topkis DM (1998) Supermodularity and Complementarity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · doi:10.1515/9781400822539
[72] Truong VA (2015) Optimal advance scheduling. Management Sci. 61(7):1584-1597.Link, Google Scholar
[73] Van Mieghem JA (1995) Dynamic scheduling with convex delay costs: The generalized cμ rule. Ann. Appl. Probab. 5(3):809-833.Crossref, Google Scholar · Zbl 0843.90047 · doi:10.1214/aoap/1177004706
[74] Vengerov D (2007) A reinforcement learning approach to dynamic resource allocation. Engrg. Appl. Artificial Intelligence 20(3):383-390.Crossref, Google Scholar · doi:10.1016/j.engappai.2006.06.019
[75] Véricourt Fd, Jennings OB (2011) Nurse staffing in medical units: A queueing perspective. Oper. Res. 59(6):1320-1331.Link, Google Scholar · Zbl 1241.90032
[76] White DL, Froehle CM, Klassen KJ (2011) The effect of integrated scheduling and capacity policies on clinical efficiency. Production Oper. Management 20(3):442-455.Crossref, Google Scholar · doi:10.1111/j.1937-5956.2011.01220.x
[77] World Health Organization (2014) Ageing and life-course. Accessed December 27, 2018, https://www.who.int/ageing/about/facts/en/.Google Scholar
[78] World Health Organization (2018) Air pollution. Accessed December 27, 2018, https://www.who.int/airpollution/en/.Google Scholar
[79] Yao DD, Zhou SX, Zhuang W (2016) Joint initial stocking and transshipment—Asymptotics and bounds. Production Oper. Management 25(2):273-289.Crossref, Google Scholar · doi:10.1111/poms.12419
[80] Yuan B, Liu R, Jiang Z (2015) A branch-and-price algorithm for the home healthcare scheduling and routing problem with stochastic service times and skill requirements. Internat. J. Production Res. 53(24):7450-7464.Crossref, Google Scholar · doi:10.1080/00207543.2015.1082041
[81] Zhang Y, Puterman ML, Nelson M, Atkins D (2012) A simulation optimization approach to long-term care capacity planning. Oper. Res. 60(2):249-261.Link, Google Scholar · Zbl 1251.90411
[82] Zhao H, Ryan JK, Deshpande V (2008) Optimal dynamic production and inventory transshipment policies for a two-location make-to-stock system. Oper. Res. 56(2):400-410.Link, Google Scholar · Zbl 1167.90365
[83] Zhu X, Sherali HD (2009) Two-stage workforce planning under demand fluctuations and uncertainty. J. Oper. Res. Soc. 60(1):94-103.Crossref, Google Scholar · Zbl 1168.90533 · doi:10.1057/palgrave.jors.2602522
[84] Zipkin P (2008) On the structure of lost-sales inventory models. Oper. Res. 56(4):937-944.Link, Google Scholar · Zbl 1167.90369
[85] Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Programming 175(1-2):461-502.Crossref, Google Scholar · Zbl 1412.90101 · doi:10.1007/s10107-018-1249-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.