# Operating room scheduling and rescheduling: a rolling horizon approach

Bernardetta Addis, Giuliana Carello, Andrea Grosso, Elena Tànfani

► To cite this version:

Bernardetta Addis, Giuliana Carello, Andrea Grosso, Elena Tànfani. Operating room scheduling and rescheduling: a rolling horizon approach. Flexible Services and Manufacturing Journal, 2016, 28, pp.206-232. 10.1007/s10696-015-9213-7. hal-01247520

HAL Id: hal-01247520

https://inria.hal.science/hal-01247520v1

Submitted on 9 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
AperTO - Archivio Istituzionale Open Access dell'Università di Torino

**Operating room scheduling and rescheduling: a rolling horizon approach.**

**This is the author's manuscript**

*Original Citation:*

*Availability:*

This version is available http://hdl.handle.net/2318/1572632 since 2016-06-27T12:34:25Z

*Published version:*

DOI:10.1007/s10696-015-9213-7

*Terms of use:*

Open Access

Anyone can freely access the full text of works made available as "Open Access". Works made available under a Creative Commons license can be used according to the terms and conditions of said license. Use of all other works requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law.

(Article begins on next page)
This is the author's final version of the contribution published as:

Addis, Bernardetta; Carello, Giuliana; Grosso, Andrea; Tànfani, Elena.
Operating room scheduling and rescheduling: a rolling horizon approach..
FLEXIBLE SERVICES AND MANUFACTURING JOURNAL. 28 (1) pp:
206-232.
DOI: 10.1007/s10696-015-9213-7

The publisher's version is available at:

http://link.springer.com/content/pdf/10.1007/s10696-015-9213-7

When citing, please refer to the published version.

Link to this full text:

http://hdl.handle.net/None
# A rolling horizon framework for the OR planning under uncertain surgery duration: deterministic versus robust approach

Bernardetta Addis<sup>a,*</sup>, Giuliana Carello<sup>b</sup>, Andrea Grosso<sup>c</sup>, Elena Tànfani<sup>d</sup>

<sup>a</sup>LORIA, Université de Lorraine, CNRS, INRIA, 615 rue du Jardin Botanique, Vandœuvre lès Nancy,
France

<sup>b</sup>Dipartimento di Elettronica, Informatica e Bioingegneria, Politecnico di Milano, via Ponzio 34, Milano,
Italy

<sup>c</sup>Dipartimento di Informatica, Università di Torino, corso Svizzera 185, Torino, Italy

<sup>d</sup>Dipartimento di Economia, Università di Genova, via Vivaldi 5, Genova, Italy

## Abstract

The Surgical Case Assignment Problem (SCAP) is a key problem in managing Operating Room and surgery wards. In the considered SCAP problem a set of patients and the related surgery waiting list are given, together with a set of Operating Room (OR) blocks and a planning horizon. The problem asks to determine the subset of patients to be scheduled in the considered time horizon and their assignment to the available OR blocks. The aim is to minimize a penalty associated to waiting time, urgency and tardiness of patients. However, when the obtained solution is applied, unpredictable extensions of surgeries may reduce the available time and thus may prevent to operate all the scheduled patients. As a consequence, some of the patients must be rescheduled in the following days, and the overall solution must be updated in order to manage them. Therefore, we propose an approach combining offline and online decisions. The offline solutions are applied and modified online so as to manage patients who have been cancelled and must be rescheduled and newly patient arrivals. Uncertainty in surgery duration must be considered in the offline step, so as to reduce the number of cancelled patients: we apply a cardinality-constrained robust optimization approach to model the off-line scheduling problem. Tests on a set of real-based instances are carried on. We apply the proposed two-step approach on a set of randomly generated scenarios in order to assess its behavior in managing patients to be rescheduled and new arrivals. Beside, we evaluate the benefit of applying a robust solution rather than a non-robust one in the off-line step.

<footnote>*corresponding author</footnote>

<footnote>Email addresses: bernardetta.addis@loria.fr (Bernardetta Addis), giuliana.carello@polimi.it (Giuliana Carello), andrea.grosso@unito.it (Andrea Grosso), etanfani@economia.unige.it (Elena Tànfani)</footnote>
# 1. Introduction and problem addressed

In recent years, hospital organizations have been facing a strong pressure to improve the health care delivery processes and to increase their productivity and operational efficiency. In the majority of the hospitals, surgical departments contribute significantly to the total expenditure; besides, they have a great impact on services demands and patient waiting times. The crucial role of surgery departments and their management within hospitals results in an increasing number of research studies aimed at planning Operating Rooms (ORs). Recent literature reviews on operating room planning and scheduling are reported in [7] and [14], where the authors analyze into detail different topics related to the problem settings and summarize significant trends in actual research and possible areas for the future one. Due to the many features that can or cannot be taken into account, several different versions of the OR problem have been considered in literature [8].

OR planning and scheduling problems may be classified according to the scheduling strategy used, i.e. block scheduling, open scheduling, and modified block scheduling. In the block scheduling, each specialty receives a number of OR blocks (usually half-day or full day length) in a given planning period, into which it can arrange its surgical cases [30]. Instead, in the open scheduling, operating rooms are not reserved to a specialty: open scheduling allows surgical cases to be assigned to any operating room available at the convenience of the surgeons or surgical specialties [3]. Modified block scheduling strategy is a mix of the two previous strategies, which can increase the flexibility of the pure block scheduling approach [13].

In this paper we focus on the OR planning and scheduling problem assuming a block scheduling strategy. Within this framework, the problem is usually decomposed into three main phases [28]. Firstly, the number, type and opening hours of the ORs are fixed at a strategic level. Second, the OR capacity is divided among surgical groups or specialties and a cyclic timetable, denoted as *Master Surgical Schedule*, is built on a medium term stand point to account for the tactical assignment of specialties to the OR blocks during the planning horizon. The last phase, referred as *Surgery Process Scheduling*, is divided into two sub-problems: *Advance Scheduling* and *Allocation scheduling* [20, 5]. The Advance Scheduling Problem (ASP) assigns a surgery date and OR to the each scheduled patient, afterwards the allocation scheduling problem determines the sequence of surgeries in each OR block.

We set our analysis at an operational level and we focus our attention on the ASP also known as surgical case assignment, surgery scheduling, surgery admission or surgery loading problem.

Integer and mixed integer linear programming models have been developed for the ASP assuming deterministic surgery times: langragian relaxation approaches [2], branch and price algorithms [6, 12], heuristics [21, 19, 26, 17] and metaeuristics algorithms [24, 16] have been recently proposed.

The OR planning and scheduling problem is further complicated by the inherent variability of the surgical cases durations, which forces the planners to over-conservative scheduling, thus reducing the OR utilization level [29]. Modeling the stochasticity of
operating times is a crucial factor in real life planning and scheduling systems, and differ-
ent assumptions on surgery duration distributions have high impact on the resulting OR
overtime and idle time [9].

Fewer papers have been published that propose methods to solve the surgery process scheduling taking into account surgery durations uncertainty. The approaches can be roughly classified into stochastic programming and robust optimization methods. In [11] an advance scheduling problem is considered and uncertainty is managed using a two-stage stochastic model with recourse. The objective function includes the patient waiting times and the OR idle and overtime. The authors compare different heuristics. Furthermore, they also analyze the influence of patient sequencing inside the OR blocks. In [22] a stochastic programming model with recourse is presented. A sample average approximation method to obtain an optimal surgery schedule with the aim of minimizing patient costs and OR overtime costs is used. In [31] a mathematical program considering probabilistic constraints to represent the uncertain duration of surgery procedures is proposed. The proposed model tries to optimize OR utilization without increasing overtime and cancellations. In [10] two models aimed at minimizing the overall OR cost including a fixed cost of opening ORs and a variable cost of overtime are compared. The first is a two-stage stochastic linear model with binary decision variables in the first stage and simple recourse in the second stage. The second is its robust counterpart, in which the objective is to minimize the maximum cost associated with an uncertainty set for surgery durations. They show that the robust method is much faster than solving the stochastic recourse model, and has the benefit of limiting the worst-case outcome of the recourse problem. In [15] different heuristics for the robust surgery loading problem are proposed, with the aim of maximizing the utilization of operating theatre and minimizing the overtime risk by introducing planned slack times. In [27] a two-level framework is proposed. In the first level, a MIP model finds a deterministic solution for the OR planning problem. In the second level, the variability of surgery duration is taken into account by means of individual chance constraints for each OR block and a robust solution is achieved by iteratively adding safety slacks to the first level deterministic model solutions.

Simulation based approaches are also proposed in literature. Some authors use simu-
lation to compare different scheduling strategies and test the solution robustness against
the randomness of surgery duration [23, 28, 25]. Although the majority of the authors re-
stricts their analysis to the evaluation of alternative scenarios, advanced simulation-based
optimization approaches have been proposed combining simulation with other solution
techniques [4, 18].

In this paper we focus our attention on the advance scheduling problem problem in-
cluding uncertainty in surgery duration and combining offline and online decisions. The
offline step determines, for a given planning horizon, the set of patients to be scheduled in
each OR and day. In the offline step the initial waiting list at beginning of the planning
horizon, the inter-arrival times of new elective patients as well as emergent cases during the
planning horizon, are assumed to be known in advance. Offline solutions are based on the
results of our previous work on robust scheduling, where surgical durations are assumed
lognormally distributed. The benefit of applying a robust solution rather than a non-robust
one in the off-line step should be evaluated. When the offline solutions are applied unpre-
dictable extensions of surgeries and/or emergent patient arrivals (anche se non lo facciamo
va detto che potrebber esserci arrivi emergenti imprevisti) may prevent to operate all the
scheduled patients thus disrupting the overall schedule. The offline scheduling is used
as a baseline schedule for online scheduling which is used to repair the baseline schedule
in order to manage patients who have been cancelled and must be rescheduled and new
patient arrivals to be planned. A rolling horizon based approach is used to solve the online
schedule. In particular, a scheduling model is applied at the end of each sub-period (for
example one week or two weeks) to re-schedule the patient cancelled in the sub-period,
re-optimize the assignment of patients to OR blocks for the next planning period while
"minimize" cancellations of pre-planned patients.

## 2. Optimization-re-optimization framework

Spiegare l'idea generale della struttura. Diciamo che per i sottoproblemi vengono usati
dei modelli, per la loro descrizione si rimanda alla relativa sezione

<figure><img src="image_2.png" /></figure>

## 3. Models

In the ASP a set of elective patients *I* is given to be scheduled in a planning horizon. Let *D* be the length in days of the planning horizon. We assume a block scheduling approach and focus on a single surgical specialty, but the approach can be easily adapted to take into account more than one specialty. A set *J* of OR blocks assigned to the specialty and
their schedule during a week are given. Each block is described by an operating room and a week day. The planning horizon is then represented by a sequence of repetitions of the same group of blocks in a set of weeks K. The available total time of a time block j in week k, i.e. the OR block length, is denoted as $\gamma_{jk}$.

The patients in the set I belong to a waiting list, where patients are registered at the moment they arrive at the service. For each patient i, let $w_i$ denote the number of days which the patient has already spent in the waiting list at the beginning of the planning horizon. Moreover, a maximum waiting time $l_i$ and a corresponding urgency parameter $u_i$ are given for each patient i. If the patient has spent $w_i$ days in the waiting list, he/she must receive surgery before a due date $dd_i = l_i - w_i$, otherwise he/she is considered tardy. According to the block weekly based pattern, if a patient is scheduled in block $j \in J$ and week $k \in K$, he/she waits a total number of days $d_{jk} = 7(k - 1) + j$. The surgery time $\tilde{t}_i$ for each patient i is considered to follow a given probability distribution.

The Stochastic Advanced Scheduling (SAS) problem can be defined: select a subset of patients to be operated on in the considered planning horizon and assign them to weeks and OR blocks, while guaranteeing that the capacity of each block is not exceeded. The objective function aims at minimizing an overall penalty due to delay in serving the patients. As proposed in [26] it takes into account both the urgency and waiting time of scheduled and not scheduled patients. Besides, a penalty for due date violation and patient tardiness is also considered ([1]).

The set of weeks in which a patient p can be rescheduled is denoted as $K_f \subset K$. For each patient i belonging to the set I of patients to be scheduled in the online step, let introduce the parameter $r_i$ which is equal to 1 if patient i must be rescheduled in the next weeks $k \in K_f$ and 0 otherwise.

To limit the impact of rescheduled patients and newly arriving ones, we accept a limited number of disruption in the first weeks on the rolling period. Let us denote with $E_K$ the first week set.

The problem can be formulated using the following set of binary variables

* $x_{ij}^k$, such that $x_{ij}^k = 1$ if patient i is assigned to block j in week $k \in K$, and zero otherwise.

* $z_i^s$ number of cancellations of pre-planned patients

* $y_i^s$ number of patients added to the schedule and not previously pre-planned to be operated on

The objective function is formulated as follows:

$$ \min \quad \sum_{i \in I} \left\{ \sum_{j \in J} \sum_{k \in K} [d_{jk} + (w_i + d_{jk} - l_i)^+] u_i x_{ij}^k + [(w_i + D + 1) + (w_i + D + 1 - l_i)^+] u_i \left(1 - \sum_{j \in J} \sum_{k \in K} x_{ij}^k\right) \right\}, \quad (1) $$
where $(w_i + d_{jk} - l_i)^+ = \max\{w_i + d_{jk} - l_i, 0\}$ is the patient tardiness, that is the number of days waited after the due date. The first term represents the penalty for the scheduled patients. For each scheduled patient $i$ the penalty is composed by two parts: the number of days $d_{jk}$ spent before receiving surgery in the planning horizon and the tardiness $(w_i + d_{jk} - l_i)^+$ of the patient. The term is weighted by the patient urgency parameter $u_i$, in order to give priority to the most urgent patients. The second term is associated with the penalty of the unscheduled patients. It is the sum of the tardiness and the overall days spent waiting for surgery before and after the beginning of the planning horizon, while for the scheduled patients, the waiting days term consider also the days after the beginning of the planning horizon. As real tardiness and waiting days cannot be computed for unscheduled patients (we do not know when there will be scheduled), we use a lower bound to take them into account, which is calculated assuming that all the remaining patients are scheduled the first day after the planning horizon ($D+1$). Also for the unscheduled patients the waiting time and the tardiness are weighted by the urgency parameter $u_i$.

The set of constraints is the following:

$$ \sum_{j \in J} \sum_{k \in K} x_{ij}^k \leq 1 \qquad \forall i \in I : r_i = 0 \qquad (2) $$

$$ \sum_{j \in J} \sum_{k \in K_f} x_{ij}^k = 1 \qquad \forall i \in I : r_i = 1 \qquad (3) $$

$$ \sum_{i \in I} \tilde{t}_i x_{ij}^k \leq \gamma_{jk} \qquad \forall j \in J, \forall k \in K \qquad (4) $$

$$ \sum_{i \in I} \sum_{j \in J} \tilde{t}_i x_{ij}^k \leq \alpha_k \sum_{j \in J} \gamma_j \qquad \forall k \in K \qquad (5) $$

$$ z_i^k \geq 1 - \sum_{j \in J} x_{ij}^k \qquad \forall i \in I, k \in K_p : \sum_j \tilde{x}_{ij}^k = 1 \qquad (6) $$

$$ y_i^k \geq \sum_{j \in J} x_{ij}^k - 1 \qquad \forall i \in I, k \in K_p : \sum_j \tilde{x}_{ij}^k = 0 \qquad (7) $$

$$ \sum_{i \in I} z_i^k + \sum_{i \in I : r_i = 0} y_i^k \leq \delta_k \qquad \forall k \in E_K \qquad (8) $$

Constraints (2) ensure that each patient is operated at most once, while constraints (3) ensure that each patient cancelled must be scheduled in one block belonging to week $k \in K_f$. Constraints (4) are the stochastic capacity constraints for each block forcing the total time in block $j$ of week $k$ to be lesser than or equal to the maximum available time $\gamma_{jk}$. Constraints (5) are the week utilization constraints which bounds the total occupation of blocks for week $k$ to be less than the occupation parameter $\alpha_k$. Note that the value of $\alpha_k$ is equal to 1 for the first week of the planning horizon and decreases for the following weeks in order to leave increasing slack capacity to manage new patient arrivals and emergency cases in the future. Constraints (6) and Constraints (7) compute the number of cancellations of pre-planned patients not yet scheduled and of new patients included in the schedule and not previously scheduled, respectively. Constraints (8) and Constraints (??) bound the
total number of disruptions between pre and post optimization to the value $\delta_k$, a priori
determined, respectively, for the set of next weeks $K_f$ and the following ones.

[1] B. Addis, G. Carello, and E. Tànfani. A robust optimization approach for the op-
erating room planning problem with uncertain surgery durations. In *International
Conference on Health Care Systems Engineering*, 2013.

[2] V. Augusto, X. Xie, and V. Perdomo. Operating theatre scheduling using lagrangian relaxation. *European Journal of Industrial Engineering*, 2(2):172–189, 2008.

[3] V. Augusto, X. Xie, and V. Perdomo. Operating theatre scheduling with patient recovery in both operating rooms and recovery beds. *Computer & Industrial Engineering*, 58(2):231–238, 2010.

[4] C. Banditori, P. Cappanera, and F. Visintin. A combined optimizationsimulation approach to the master surgical scheduling problem. *Journal of Management Mathematics*, 24:155–187, 2013.

[5] J. Blake and M. Carter. Surgical process scheduling: a structured review. *Journal of the Society for Health Systems*, 5(3):17–30, 1997.

[6] B. Cardoen, E. Demeulemeester, and J. Beliën. Sequencing surgical cases in a day-care environment: An exact branch-and-price approach. *Computers & Operations Research*, 36(9):2660–2669, 2009.

[7] B. Cardoen, E. Demeulemeester, and J. Beliën. Operating room planning and schedul-
ing: A literature review. *European Journal of Operational Research*, 201:921–932,
2010.

[8] B. Cardoen, E. Demeulemeester, and J. Beliën. Operating room planning and schedul-
ing problems: A classification scheme. *International Journal of Health Management
and Information*, 1(1):71–83, 2010.

[9] S. Choi and W. Wilhelm. An analysis of sequencing surgeries with durations that follow the lognormal, gamma, or normal distribution. *IIE Transactions on Healthcare Systems Engineering*, 2:156–171, 2012.

[10] B. Denton, J. Miller, H. Balasubramanian, and T. Huschka. Optimal allocation of surgery blocks to operating rooms under uncertainty. *Operations Research*, 58:802–816, 2010.

[11] B. Denton, J. Viapiano, and A. Vogl. Optimization of surgery sequencing and schedul-
ing decisions under uncertainty. *Health Care Management Science*, 10:13–24, 2007.

[12] H. Fei, C. Chu, N. Meskens, and A. Artiba. Solving surgical cases assignment problem by a branch-and-price approach. *International Journal of Production Economics*, 112:96–108, 2008.
[13] H. Fei, N. Meskens, and C. Chu. A planning and scheduling problem for an operating theatre using an open scheduling strategy. *Computer & Industrial Engineering*, 58(2):221-230, 2010.

[14] F. Guerriero and R. Guido. Operational research in the management of the operating theatre: a survey. *Health Care Management Science*, 14:89-114, 2011.

[15] E. Hans, G. Wullink, M. van Houdenhoven, and G. Kamezier. Robust surgery loading. *European Journal of Operational Research*, 185:1038-1050, 2008.

[16] W. Herring and J. Herrmann. Local search for the surgery admission planning problem. *Journal of Heuristics*, 17:389-414, 2011.

[17] W. Herring and J. Herrmann. The single-day surgery scheduling problem: sequential decision-making and threshold-based heuristics. *OR Spectrum*, 34:429-459, 2012.

[18] M. Lamiri, X. Xie, A. Dolgui, and F. Grimaud. A stochastic model for operating room planning with elective and emergency demand for surgery. *Journal of Operational Research Society*, 185:1026-1037, 2008.

[19] Y. Liu, C. Chu, and K. Wang. A new heuristic algorithm for the operating room scheduling problem. *Computers & Industrial Engineering*, 61:865-871, 2011.

[20] J. Magerlein and J. Martin. Surgical demand scheduling: A review. *Health Services Research*, 13:418-433, 1978.

[21] I. Marques, M. Captivo, and M. Pato. An integer programming approach to elective surgery scheduling. *OR Spectrum*, 34:407-427, 2012.

[22] D. Min and Y. Yih. Scheduling elective surgery under uncertainty and downstream capacity constraints. *European Journal of Operational Research*, 206:642-652, 2010.

[23] M. Persson and J. Persson. Analysing management policies for operating room planning using simulation. *Health Care Management Science*, 13:182-191, 2010.

[24] C. Rizk and J. Arnaout. Aco for the surgical cases assignment problem. *Journal of Medical Systems*, 36:1191-1199, 2012.

[25] B. Sobolev, V. Sanchez, and C. Vasilakis. Systematic review of the use of computer simulation modeling of patient flow in surgical care. *Journal of Medical Systems*, 35:1-16, 2011.

[26] E. Tànfani and A. Testi. A pre-assignment heuristic algorithm for the master surgical schedule problem (mssp). *Annals of Operations Research*, 178(1):105-119, 2010.

[27] E. Tànfani, A. Testi, and R. Alvarez. Operating room planning considering stochastic surgery durations. *International Journal of Health Management and Information*, 1(2):167-183, 2010.
[28] A. Testi, E. Tànfani, and G. Torre. A three-phase approach for operating theatre schedules. *Health Care Management Science*, 10:163–172, 2007.

[29] D. Tyler, C. Pasquariello, and C. Chen. Determining optimum operating room utilization. *Anesthesia and Analgesia*, 96(4):1114–1121, 2003.

[30] J. van Oostrum, E. Bredenhoff, and E. Hans. Suitability and managerial implications of a master surgical scheduling approach. *Annals of Operations Research*, 178(1):91–104, 2010.

[31] J. van Oostrum, M. van Houdenhoven, J. Hurink, E. Hans, G. Wullink, and G. Kazemier. A master surgical scheduling approach for cyclic scheduling in operating room departments. *OR Spectrum*, 30:355–374, 2008.