Abstract
We allocate surgery blocks to operating rooms (ORs) under random surgery durations. Given unknown distribution of the duration of each block, we investigate distributionally robust (DR) variants of two types of stochastic programming models using a moment-based ambiguous set. We minimize the total cost of opening ORs and allocating surgery blocks, while constraining OR overtime via chance constraints and via an expected penalty cost in the objective function, respectively in the two types of models. Following conic duality, we build equivalent 0–1 semidefinite programming (SDP) reformulations of the DR models and solve them using cutting-plane algorithms. For the DR chance-constrained model, we also derive a 0–1 second-order conic programming approximation to obtain less conservative solutions. We compare different models and solution methods by testing randomly generated instances. Our results show that the DR chance-constrained model better controls average and worst-case OR overtime, as compared to the stochastic programming and DR expected-penalty-based models. Our cutting-plane algorithms also outperform standard optimization solvers and efficiently solve 0–1 SDP formulations.
Similar content being viewed by others
References
Berg, B.P., Denton, B.T., Erdogan, S.A., Rohleder, T., Huschka, T.R.: Optimal booking and scheduling in outpatient procedure centers. Comput. Oper. Res. 50, 24–37 (2014)
Bertsimas, D., Doan, X.V., Natarajan, K., Teo, C.-P.: Models for minimax stochastic linear optimization problems with risk aversion. Math. Oper. Res. 35(3), 580–602 (2010)
Cardoen, B., Demeulemeester, E., Beliën, J.: Operating room planning and scheduling: a literature review. Eur. J. Oper. Res. 201(3), 921–932 (2010)
Chaabane, S., Meskens, N., Guinet, A., Laurent, M.: Comparison of two methods of operating theatre planning: application in belgian hospital. J. Syst. Sci. Syst. Eng. 17(2), 171–186 (2008)
Delage, E., Ye, Y.: Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3), 595–612 (2010)
Deng, Y., Shen, S., Denton, B.T.: Chance-constrained surgery planning under conditions of limited and ambiguous data. Available at SSRN https://doi.org/10.2139/ssrn.2432375 (2016)
Denton, B.T., Miller, A.J., Balasubramanian, H.J., Huschka, T.R.: Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4), 802–816 (2010)
Erdogan, S.A., Denton, B.T.: Surgery planning and scheduling. In: Cochran, J., Cox, L., Keskinocak, P., Kharoufeh, J., Smith, J. (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley Online Library, New York (2011)
Herring, W.L., Herrmann, J.W.: The single-day surgery scheduling problem: sequential decision-making and threshold-based heuristics. OR Spectr. 34(2), 429–459 (2012)
Jiang, R., Guan, Y.: Data-driven chance constrained stochastic program. Math. Program. Ser. A 158(1), 291–327 (2016)
Marques, I., Captivo, M.E., Pato, M.V.: An integer programming approach to elective surgery scheduling. OR Spectr. 34(2), 407–427 (2012)
Shapiro, A. (2000). On duality theory of conic linear problems. In: Semi-Infinite Programming, pp. 135–165. Kluwer Academic Publishers
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, vol. 9. SIAM, Philadelphia (2009)
Shylo, O.V., Prokopyev, O.A., Schaefer, A.J.: Stochastic operating room scheduling for high-volume specialties under block booking. INFORMS J. Comput. 25(4), 682–692 (2012)
Testi, A., Tanfani, E., Torre, G.: A three-phase approach for operating theatre schedules. Health Care Manag. Sci. 10(2), 163–172 (2007)
Todd, M.J.: Semidefinite optimization. Acta Numer. 2001(10), 515–560 (2001)
Wagner, M.: Stochastic 0–1 linear programming under limited distributional information. Oper. Res. Lett. 36(2), 150–156 (2008)
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix A: Proof of Theorem 1
Proof
Define dual variables \(r_i\) for (3b), \(\begin{bmatrix} H_i&p_i\\ p_i^{\mathsf {T}}&q_i\end{bmatrix}\in {\mathbb {S}}_+^{(|J|+1)\times (|J|+1)}\) for (3c), and \(G_i\in {\mathbb {S}}_+^{|J|\times |J|}\) for (3d). The conic dual problem of (3) is
As strong duality holds for the primal and dual problems [12], satisfying the DR chance constraints (1e) with the ambiguity set \({\mathcal {D}}_i^M\), is equivalent to having solutions with objective value \( \ge 1-\alpha _i\), \(i\in I\). After applying Lemma 1 in Jiang and Guan [10], the dual problem (29), where its objective function is written as a constraint such that it is no less than \(1-\alpha _i\), is equivalent to SDP(\({\hat{y}}_i, {\hat{z}}_i\)), after replacing the semi-infinite constraints (29b) with finite number of SDP constraints. The proof completes. \(\square \)
Appendix B: Cutting-plane algorithm for optimizing 0–1 SDP reformulations
Rights and permissions
About this article
Cite this article
Zhang, Y., Shen, S. & Erdogan, S.A. Solving 0–1 semidefinite programs for distributionally robust allocation of surgery blocks. Optim Lett 12, 1503–1521 (2018). https://doi.org/10.1007/s11590-018-1255-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-018-1255-9