A pattern based, robust approach to cyclic master surgery scheduling

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.

1. 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.

2. This drawback could be overcome by a slightly more complicating model, but this is out of the paper’s scope.

3. A clique C is maximal if no larger clique contains C.

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.

Authors and Affiliations

1. Department of Computer and System Sciences, Sapienza University of Rome, Rome, Italy

   Carlo Mannino

2. Department of Applied Mathematics, SINTEF ICT, P.O. Box 124, Blindern, 0314, Oslo, Norway

   Eivind J. Nilssen & Tomas Eric Nordlander

Corresponding author

Correspondence to Carlo Mannino.

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 ₁ and x ₂ 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 ₁+x ₂≤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.

Reprints and permissions