Abstract
The Master Surgery Scheduling problem consists of finding a suitable allocation of operating resources to surgical groups. A myriad of variants of the problem has been addressed in literature. Here we focus on two major variants, arising during a cooperation with Sykehuset Asker og Bærum HF, a large hospital in the city of Oslo. The first variant asks for balancing patient queue lengths among different specialties, whereas the second for minimizing resort to overtime. To cope with these problems we introduce a new mixed integer linear formulation and show its beneficial properties. Both problems require the estimation of demand levels. As such estimation is affected by uncertainty, we also develop a light robustness approach to the second variant. Finally we present computational results on a number of real-world instances provided by our reference hospital.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
In this case, r∈R is actually a pair (a,b), where a is an equipped room and b is a surgical team which may operate in room a.
This drawback could be overcome by a slightly more complicating model, but this is out of the paper’s scope.
A clique C is maximal if no larger clique contains C.
References
Adan, I., & Vissers, J. (2002). Patient mix optimisation in hospital admission planning: a case study. International Journal of Operations & Production Management, 22(4), 445–461.
Beliën, J., Demeleulemeester, E., & Cardoen, B. (2009). A decision support system for cyclic master surgery scheduling with multiple objectives. Journal of Scheduling, 12, 147–161. doi:10.1007/s10951-008-0086-4.
Beliën, J., & Demeulemeester, E. (2007). Building cyclic master surgery schedules with leveled resulting bed occupancy. European Journal of Operational Research, 176(2), 1185–1204.
Beliën, J., Demeulemeester, E., & Cardoen, B. (2006). Visualizing the demand for various resources as a function of the master surgery schedule: a case study. Journal of Medical Systems, 30, 343–350.
Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization methodology and applications. Mathematical Programming, 92(3), 453–480.
Blake, J. T., Dexter, F., & Donald, J. (2002). Operating room managers’ use of integer programming for assigning block time to surgical groups: a case study. Anesthesia and Analgesia, 94(1), 143–148.
Blake, J. T., & Donald, J. (2002). Mount Sinai hospital uses integer programming to allocate operating room time. Interfaces, 32(2), 63–73.
Cardoen, B., Demeulemeester, E., & Beliën, J. (2010). Operating room planning and scheduling: a literature review. European Journal of Operational Research, 201, 921–932.
de Werra, D., Asratian, A. S., & Durand, S. (2002). Complexity of some special types of timetabling problems. Journal of Scheduling, 5, 171–183.
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52, 35–53.
Burke, E., Curtois, T., Nordlander, T. E., & Riise, A. (2010). In Handbook of Healthcare Delivery Systems (p. 840). Boca Raton: CRC Press.
Fischetti, M., & Monaci, M. (2009). Light Robustness. In R. K. Ahuja, R. Moehring, & C. Zaroliagis (Eds.), Lecture Notes in Computer Science: Vol. 5868. Robust and Online Large-Scale Optimization (pp. 61–84). Berlin: Springer.
Fischetti, M., Salvagnin, D., & Zanette, A. (2009). Fast approaches to improve the robustness of a railway timetable. Transportation Science, 43(3), 321–335.
Hans, E., Wullink, G., van Houdenhovenand, M., & Kazemier, G. (2008). Robust surgery loading. Central European Journal of Operations Research, 185, 1038–1050.
Macario, A., Vitez, T. S., Dunn, B., & McDonald, T. (1995). Where are the costs in perioperative care? Analysis of hospital costs and charges for inpatient surgical care. Anesthesiology, 83(6), 1138–1144.
Mannino, C., Nilssen, E. J., & Nordlander, T. E. (2010). Sintef ict: Mss-adjusts surgery data. [WWW] Available from: http://www.comihc.org/index.php/Test-Bed/3-yearsof-surgery-data-at-sab.html.
Marler, T. R., & Arora, J. S. (2004). Survey of multi-objective optimization methods for engineering. Structural and Multidisciplinary Optimization, 26(6), 369–395.
Oostrum, J. M., van Houdenhoven, M., Hurink, J. L., Hans, E. W., Wullink, G., & Kazemier, G. (2008). A master surgical scheduling approach for cyclic scheduling in operating room departments. OR-Spektrum, 30(2), 355–374.
Santibanez, P., Begen, M., & Atkins, D. (2007). Surgical block scheduling in a system of hospitals: an application to resource and wait list management in a British Columbia health authority. Health Care Management Science, 10(3), 269–282.
Soyster, J. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21, 1154–1157.
Acknowledgements
The authors wish to thank Tone Jensen and Anne Dorthe Røsvik from the hospital ’Sykehuset Asker og Bærum HF’ for providing us with data and their precious comments and suggestions throughout our research. We also thank the anonymous referees for their comments.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
The block-assignment formulation
A natural formulation which extends the one presented in Beliën et al. (2009) is sketched in the sequel. We introduce, for each g∈G, each day d∈D, each surgical resource r∈R and each block length l∈L an integer variable y gdrl representing the number of blocks of length l of resource r assigned to g in day d. Clearly, \(\sum _{d\in D,r\in R} y_{gdrl} \leq b_{g}^{l}\) for all groups g and all block lengths l. Also, for each group g, the corresponding queue is represented by a non-negative real variable \(q^{y}_{g}\).
If we denote by CAP dr the number of slots available on day d for resource r, then the following constraints ensure that the daily capacity is not exceeded:
Then the queue \(q^{y}_{g}\) for each group g∈G can be defined very similarly to (4) as
Finally the cost function f is the one introduced in the pattern formulation (5), i.e. we want to find y and q y so that \(\sum_{g\in G} f(q^{y}_{g})\) is minimized.
Again, other constraints and objectives may be considered. We show now that the pattern formulation is stronger than the block-assignment formulation, in that it may provide larger bounds (when the LP relaxation is solved to optimality), which in turn can imply smaller branching trees when applying a Branch&Cut approach. To this end we will show that every feasible solution to (5) can be converted to a feasible solution to the block-assignment formulation of equal value. We will also show that the converse is not true. In the following, S(p) is the set of feasible solution to the LP relaxation of the pattern formulation, whereas S(b) is the set of feasible solution to the block-assignment formulation.
Let \(\bar{x}\) denote a fractional solution to the LP relaxation of (5) and let \(q(\bar{x})\) be the associated queues. Denote by P(g,r,d,l)⊆P the set of patterns of length l available for group g on day d and for resource r. Also, for all g∈G, r∈R, d∈D and l∈L let \(\bar{y}_{grdl} = \sum_{p\in P(g,r,d,l)} \bar{x}_{gp}\). Denote by \(q^{y}(\bar{y})\) the queues associated with \(\bar{y}\) by equality (9) in the block-assignment. Then it is straightforward to see that \(q(\bar{x}) = q^{y}(\bar{y})\), which implies that min{f(q y):(y,q y)∈S(b)}≤min{f(q):(x,q)∈S(p)}, and the block formulation is no stronger than the pattern one.
To show that the converse does not hold in general, consider a very simple instance, with |G|=|D|=|R|=|L|=1, and suppose L={3} and the daily capacity of the single resource is CAP=4 (e.g. the four 2-hour slots from 8:00 to 16:00). That is, we have only patterns of length 3 and the number of available slots per day and per surgical resource is 4. Given that we only have one unit of surgical resource, we have exactly two 3-patterns, namely the pattern composed by the first three slots (e.g. from 8:00 to 14:00) and the one composed by the next three slots (e.g. from 10:00 to 16:00). Also, we suppose that the demand of 3-blocks for the unique group equals 2. Denote by y the unique integer variable associated with this instance in the block-assignment formulation, and q y the single queue variable. Then it is not difficult to see that, if we let \(\bar{y} = 4/3\) and \(\bar{q}^{y} = 2-4/3 = 2/3\), then \((\bar{y}, \bar{q})\in S(b)\), that is, the point is feasible for the LP relaxation of the block-assignment formulation.
Concerning the pattern formulation, it contains only two 0, 1 variables and one real (queue) variable. On the other hand, denote by x 1 and x 2 the pattern variables associated with the two available patterns of length 3 in the pattern formulation, and let q be the unique queue variable. It is not difficult to see that q≥1 in every feasible solution, because x 1+x 2≤1. Now, because the cost function f is non-decreasing, we have f(2/3)≤f(1), and we can easily define f in such a way that inequality holds strictly.
Rights and permissions
About this article
Cite this article
Mannino, C., Nilssen, E.J. & Nordlander, T.E. A pattern based, robust approach to cyclic master surgery scheduling. J Sched 15, 553–563 (2012). https://doi.org/10.1007/s10951-012-0275-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-012-0275-z