An efficient computational method for large scale surgery scheduling problems with chance constraints

Abstract

We propose an efficient solution method based on a decomposition of set-partitioning formulation of an integrated surgery planning and scheduling problem with chance constraints. The studied problem is characterized by a set of identical operating rooms (ORs), a set of surgeries with uncertain durations, a set of surgeons, and surgery dependent turnover times. The decision variables include the number of ORs to open, assignments of surgeries and surgeons to ORs in admissible periods, and the sequence of surgeries to be performed in a period. The objective is to minimize the cost of opening ORs and the penalties associated with turnover times.In the proposed formulation, the column generation subproblem is decomposed over ORs and time periods. The structure of the subproblem is further exploited and transformed to a shortest path problem. A search algorithm has been devised to efficiently solve the resulting subproblem, subject to some optimality and feasibility conditions. The proposed computational method outperforms the standard chance constrained model and reduces the solution time significantly. Furthermore, extensive simulation experiments have been carried out to compare the performance of three variants of the underlying formulations and evaluate the sensitivity of the decisions to the probability of exceeding a session length.

1 Introduction

Studying surgery planning and scheduling problems is motivated by their significant contributions to hospitals revenue. Surgical services account for more than 40% of hospitals revenue and cost and this figure is expected to grow in near future [10]. Therefore, maximizing operating rooms utilizations and reducing the cost of surgery operations has gain considerable attention in recent years.

A surgery planning problem may be considered as a composition of two phases: (a) an assignment phase which consists of assigning patients and surgeons to operating rooms (ORs) in certain time periods (e.g., days or shifts), and (b) a scheduling phase that is to find the best sequence of surgeries for each OR in the time period determined in the assignment phase. Due to the complexity of integrating these two phases, a majority of studies have considered them separately [5]. A common approach is to assign surgeries based on a block surgery policy. In this policy, each OR available time is divided into a certain number of blocks. Each block is then allocated to one surgery type. Once the block allocations are determined, surgeries of each type are assigned to the allotted blocks. Despite the efficiency of disaggregating the two problems, which allows one to solve larger instances, the solutions are not guaranteed to be optimal and may in fact lead to hospital operational inefficiency [29]. Therefore, our motivation is to integrate both phases and solve a large scale surgery planning and scheduling problem together.

Historically, the main focus of the literature has been on deterministic OR scheduling problems [22] while assumptions on parameters with random nature such as surgery durations have a significant impact on both availability and quality of services. For example, when the uncertain nature of surgery duration is ignored, the patients’ and surgeons’ waiting time and OR overtime may increase. Stochastic OR scheduling problems are commonly studied by considering two sources of uncertainty: in parameters related to duration (e.g., surgery duration) and in patient’s arrival time. Stochastic optimization and robust optimization methods [16, 19] have been used to deal with the pertinent uncertainty in surgery scheduling problems. We present a brief review on some relevant studies next. Cardoen et al. [5] and Erdogan and Denton [9] provide extensive reviews on different aspects of OR planning and scheduling problems.

Zhang and Xie [30] studied a dynamic OR assignment problem in which surgery durations were uncertain and surgeons were assigned to available ORs on a first-come first-serve basis. They used a simulation-based optimization approach to solve the problem.

Neyshabouri and Berg [19] address a surgery scheduling problem where elective surgeries are assigned to a set of available surgery blocks. They also include downstream decisions (post-operation care) in their formulation. They assume that surgery durations and lengths of stay are uncertain, and use a column generation method to solve their proposed model. Denton et al. [8] propose a two-stage robust optimization model for a surgery problem in which the overtime is penalized. They find bounds for the number of ORs and the number of uncertain parameters i.e., surgery durations that can reach their upper bounds.

Gul et al. [12] study a surgery allocation problem under uncertainty over a finite planning horizon. Their objective function is to minimize cancellation, waiting, and overtime costs. Using a progressive hedging algorithm for their multi-stage stochastic mixed-integer formulation, they can solve relatively large instances (up to 50 surgeries and 10 days) and find near optimal surgery schedules. In addition to robust optimization based model, Denton et al. [8] consider a surgery block assignment problem with uncertain surgery durations to minimize OR opening and overtime costs. They propose a two-stage stochastic optimization formulation as well as a robust optimization formulation and solve the resulting problems using a cutting plane method and some heuristics. Wang et al. [28] extend [8] by considering a sample average approximation method to transform a two-stage stochastic model to a deterministic model for the surgery planning problem. They solve the resulting problem using a column generation method. Batun et al. [4] also propose a two-stage mixed integer stochastic model for a surgery assignment problem to minimize ORs opening and overtime costs. They aim to find the optimal assignment of pairs of surgery-surgeon to ORs on a daily basis. Shylo et al. [25] study a batch scheduling problem within a block booking policy and maximize the expected utilization of ORs while some probabilistic capacity constraints are imposed over ORs’ availablity time.

Due to the complexity of OR scheduling problems, the majority of the literature focuses on only one of the two phases (e.g., the block surgery policy) with relatively restrictive settings such as a single-period problems or ignoring surgeons in OR scheduling. The surgery planning and scheduling problems with random parameters may be formulated as stochastic integer programs (SIPs) which are among the most challenging problems in operations research [24]. The efficiency of solution algorithms for this class of problems highly depends on clever application of integer programming methods to solve SIP. To this end, one could study the possibility of taking advantage of the problem structure to develop a tailor-made algorithm which has not been well investigated for SIP in the literature. In particular, Chance Constrained Programming (CCP) is still computationally challenging [14] although its development dates back to the 1960s. There exist two main approaches to invoking uncertainty in an integer chance constrained program: a discrete approximation of uncertainty by scenarios [14] or a continuous approximation of the distribution functions of uncertain parameters [18]. Song et al. [26] provide a thorough discussion on the challenges and limitations of these two formulations. The former results in a huge number of binary variables and the latter leads to a non-linear integer program that is only tractable when random parameters follow a normal distribution. Assuming normal distribution would resolve the nonconvexity of chance constrains and makes the continuous approximation tractable. However, there are many situations where surgery durations are not normally distributed. In such situations, one could resort to discrete approximation. Here, we solve the problem using both approaches to show the impact of such approximations on the final variables.

In the literature of SIP, branch-and-cut methods are widely used to solve SIP [1, 23]. Although branch-and-price methods are among efficient and popular methods for integer programs [2, 3], very few papers have investigated solving SIP using branch-and-price methods. Lulli and Sen [15] use a set-partitioning formulation and a branch-and-price method for a chance constrained formulation of a batch sizing problem. Their proposed method could not outperform the branch-and-cut method in many instances due to the complexity of solving the subproblems. Therefore, an interesting research question arises that whether SIPs can be efficiently solved using a branch-and-price method.

In this paper, we address this research question by focusing on a multi-attribute chance constrained formulation of an integrated surgery planning and scheduling problem. We use a set-partitioning formulation of the problem, and extend the branch-and-price method in [20] to efficiently solve it. The problem is characterized by a set of identical operating rooms (ORs), a set of surgeries with uncertain surgery durations, a set of surgeons, and surgery dependent turnover times. The here-and-now decisions include the number of ORs to open, assignments of surgeries and surgeons to ORs in some admissible (preferred) time periods, and the sequence of surgeries to be performed in a period. We do not consider emergency surgeries. The turnover time is penalized in order to increase OR utilization and control/reduce surgeons waiting times. The objective function is to minimize the cost of opening ORs and the penalties associated with turnover times.

Four additional realistic conditions are taken into account. (1) The number of available ORs in each period is limited. (2) Each surgeon has his/her own surgery list. As a result, we assume that each surgeon can be assigned to only one OR in any time period. (3) Each surgery has a set of pre-defined admissible or preferred periods and cannot be scheduled in other time periods. This is a common practice in hospital management and is due to the availability of surgeons or preferences of the patients. (4) We consider surgery dependent turnover time that consists of the time required for post-surgery activities (including cleaning) and setting up the room for next surgery. We assume that induction surgical and awakening activities are included in surgery duration. However, one could model these activities differently. The turnover time could depend on the preceding surgery or the position of a surgery in the sequence. For example, after a patient’s surgery with a transmissible disease, the OR must be carefully cleaned up before the next surgery could be performed in that room. Note that our focus in this research is on assigning surgeons and surgery sessions to ORs and time periods. Additional resources such as anaesthetists and nurses have not been taken into consideration.

The contributions of this paper is summarized as follows:

• We propose an efficient solution method for an integrated surgery planning and scheduling problem with uncertain surgery durations. The proposed method can also be adapted for other general SIPs. The problem is formulated as a set-partitioning model and solved using a customized branch-and-price method.

• The column generation subproblem is decomposed over ORs and time periods. We exploit the structure of the column generation subproblem and reformulate it as a shortest path problem. The resulting shortest path is then solved using a search algorithm satisfying optimality and feasibility conditions. The proposed method leads to a significant reduction in solution time comparing with that of the standard chance constrained model. In comparison to the largest problems reported in the literature, we have solved relatively larger instances (up to 60 surgeries, 5 periods, 10 ORs and 13 surgeons) with the above realistic assumptions to optimality.

• The chance constrained formulation of OR session lengths are written for two types of uncertainties represented by: (a) a set of discrete scenarios and (b) the probability density function of the uncertain parameters.

• We have also carried out an extensive simulation to study the impact of the probability of exceeding OR session length on the decision variables and the objective function. This analysis helps hospitals’ management to decide on a proper service level for ORs session lengths and provides them with useful managerial insights.

The remainder of the paper is structured as follows. We introduce the set-partitioning model and the column generation subproblem in Sect. 2. The column generation subproblem is reformulated in Sect. 3. We outline the steps of the proposed search algorithm in Sect. 4. Computational results and sensitivity analysis are presented in Sect. 5. Some concluding remarks and future research are given in Sect. 6.

2 The set-partitioning model

We propose a set-partitioning formulation for the described integrated surgery planning and scheduling problem. We use chance constrained programming to handle uncertainty i.e., the total surgery time (including the turnover time) of an assignment must be within the OR session length with a pre-specified probability ($1-\epsilon$).

Let I, K and R be the sets of surgeries, surgeons and identical ORs. The surgery list of surgeon k, denoted by $I_k$, defines the set of surgeries to be performed by the surgeon on the planning horizon (T). We consider a set of admissible periods for each surgery ($T_i, \ i \in I$). Also let L be the normal session length. The uncertain duration of surgery i and its mean are denoted by $\tilde{d}_i$ and $\bar{d}_i$, respectively. The uncertainty of surgery durations is presented by either a set of scenarios ($\mathcal {S}$) where $p_s$ is the probability assigned to scenario s, or by distribution functions $\mathcal {D}(\bar{d}_i,\sigma ^2_i)$ where $\sigma ^2_i$ is the variance of surgery i.

Let $v_{it}$ be a binary variable that takes a value of 1 if surgery i is assigned to an OR in period t, and zero otherwise. A sequence is defined as an ordered subset of surgeries ($I_s$) assigned to an OR in a period and is considered feasible if

• (a) its total time satisfies the chance constraint condition,

• (b) it is assigned to a time period which belongs to the intersection of the admissible periods of all surgeries in that sequence ($t\in \{\cap _{i\in I_s} T_i\}$),

• (c) there is no gap between two consecutive surgeries in the sequence, i.e., ORs are not left idle.

We denote sequence s by binary variable $u_{s}$. It takes a value of 1 if it is chosen in the optimal solution. The cost of sequence s is denoted by $c_{s}$ and consists of the fixed opening cost and the penalized turnover time for all surgeries in the sequence. Also, $S_t$ and $S_t(i)$ in a time period $t\in T$ are the sets of all feasible sequences, and the set of all feasible sequences that include surgery i ($S_t(i)=\{s\in S_t| i\in I_s\}$), respectively. The set of feasible sequences at period t in which surgeon k has at least one surgery is denoted by $S^k_t$.

The surgery duration is assumed to follow a known distribution function (continuous or discrete). W.L.O.G., we can assume the duration of the pre-surgery ($pre_i$) and the post-surgery ($post_i$) activities are not included in the surgery duration and are separately considered in the model. As these activities are common, and the variance of their durations (individually) are very small, we can assume $pre_i$ and $post_i$ are exactly known in advance. Furthermore in real cases, the pre-surgery and post-surgery time may depend on the previous surgery and/or the next surgery. To simplify the notation, we summarize them in a square matrix and denote its elements by $\tau _{ij}, i,j\in I$ which is the duration of activities required for switching from surgery i to surgery j i.e., $\tau _{ij}=post_{ij}+pre_{ij}$. The entries on the diagonal of the matrix are the duration of the pre-surgery time if surgery i is the first surgery in the sequence. The post-surgery time of surgery i is denoted by $\bar{\tau }_{i}$ when it is the last surgery of the sequence which could include a complete cleaning. It is clear that one can include the preparation activities in the surgery duration. We also assume that surgeons are not assigned to next surgeries during the turnover time.

The set-partitioning model for the surgery scheduling problem is then formulated as:

$$\begin{aligned}&\text {P: }\min \sum _{t\in T}\sum _{s\in S_t}c_{s}u_{s}\end{aligned}$$

(1a)

$$\begin{aligned}&\text {s.t.}\sum _{t\in T_i}v_{it}=1, \forall i \in I\end{aligned}$$

(1b)

$$\begin{aligned}&v_{it} -\sum _{s\in S_t(i)}u_{s}\le 0, \forall t\in T_i, \forall i \in I\end{aligned}$$

(1c)

$$\begin{aligned}&\sum _{s\in S^k_t}u_{s}\le 1, \ \forall k \in K, \forall t\in T\end{aligned}$$

(1d)

$$\begin{aligned}&\sum _{s\in S_t}u_{s}\le m, \ \forall t\in T\end{aligned}$$

(1e)

$$\begin{aligned}&u_{s}\in \{0,1\},\ \forall s\in S_t, \forall t\in T\end{aligned}$$

(1f)

$$\begin{aligned}&v_{it}\in \{0,1\}, \ \forall i \in I, \forall t\in T. \end{aligned}$$

(1g)

The objective function computes the total cost including the fixed opening cost and the penalty associated with the turnover time between surgeries i.e., $c_{s}=c_R+\sum _{i,j\in I_s}c_{ij}\tau _{ij}+c_{i}\bar{\tau }_i$ where $c_R$, $c_{ij}$ and $c_{j}$ are the fixed opening cost, the unit penalty cost of turnover time of switching from surgery i to surgery j and surgery i to the end of session, respectively. Constraint (1b) ensures that each surgery is assigned to one period of its admissible periods. Constraint (1c) guarantees that at least one schedule contains surgery i for an admissible period. Constraint (1d) makes sure that a surgeon can be assigned to at most one OR in each period. Constraint (1e) enforces the limitation on the number of available ORs in each period such that $m=|R|$. Constraints (1f–1g) present the integrality conditions on variables.

It is impractical to include all feasible sequences in the beginning to P. We adopt the following policy which was successfully used by [11, 21]. Starting with a problem called the Restricted Master Problem (RMP), a subset of feasible sequences is considered in the beginning. Feasible sequences which improve the current solution are iteratively identified and added to RMP. This policy is implemented within a branch-and-bound algorithm which leads to a branch-and-price method. The subproblem which identifies feasible and improving sequences is known as the column generation subproblem or pricing subproblem. The column generation subproblem is constructed based on the dual problem of the linear relaxation of the master problem as follows.

Let $\beta _i$, $\alpha _{it}$, $\gamma _{kt}$ and $\lambda _t$ be the dual variables associated with constraints (1b–1e) in the linear relaxation of the master problem. The dual problem is formulated by

$$\begin{aligned}&\text {DP: }\max \sum _{i\in I} \beta _i-\sum _{t\in T}\sum _{k\in K}\gamma _{kt}-m\sum _{t\in T}\lambda _t \end{aligned}$$

(2)

$$\begin{aligned}&\quad \text {s.t.}\sum _{i\in I_{s}}\alpha _{it}-\sum _{k\in K_{s}}\gamma _{kt}-\lambda _t\le c_{s}, \ \forall s\in S_t, \forall t\in T\end{aligned}$$

(3)

$$\begin{aligned}&\quad \beta _i-\alpha _{it}\le 0, \ \forall t\in T_i,\ \forall i\in I\end{aligned}$$

(4)

$$\begin{aligned}&\quad \beta _i \text { free } ,\ \alpha _{it}\ge 0,\ \gamma _{kt}\ge 0 \text { and } \lambda _t\ge 0, \ \ \forall i\in I,\ \forall t\in T, k\in K \end{aligned}$$

(5)

where $K_{s}$ is the set of surgeons assigned to sequence s at time period t, respectively. Improving sequences are those that violate constraint (3). As constraint set (3) suggests, the column generation subproblem is decomposed for each period and forms a sequence which can be assigned to an OR. In order to model the column generation subproblem for each sequence, we define the following binary decision variables for $r\in R$ and $t\in T$:

$$\begin{aligned}&x_{il}^{rt}=1 \text { if } i\in I \text{ is } \text{ assigned } \text{ to } \text{ lth } \text{ position } \text{ of } \text{ a } \text{ sequence, } \text{ and } \text{ zero } \text{ otherwise, }\\&y_{ij}^{l}= 1 \text { if } i\in I \text{ precedes } j\in I \text{ in } \text{ lth } \text{ position } \text{ of } \text{ a } \text{ sequence, } \text{ and } \text{ zero } \text{ otherwise, }\\&w_{i}^{rt}= 1 \text { if } i\in I \text{ is } \text{ the } \text{ last } \text{ surgery } \text{ of } \text{ a } \text{ sequence, } \text{ and } \text{ zero } \text{ otherwise, }\\&q_{k}^{rt}= 1 \text { if surgeon } k\in K \text{ is } \text{ assigned } \text{ a } \text{ surgery } \text{ from } \text{ its } \text{ surgery } \text{ list, } \text{ and } \text{ zero } \text{ otherwise, }\\&\pi _\varsigma ^{rt}=1 \text { if the constraint associated with scenario } \varsigma \in \mathcal {S} \text { is satisfied, and zero otherwise.} \end{aligned}$$

Here, we assume that the uncertainty of the surgery duration is presented by a set of scenarios $\mathcal {S}$. The column generation subproblem for $t\in T$ and $r\in R$ is as follows:

$$\begin{aligned}&z= \min \ \ c_{R}+\sum _{i,j,l\in I}c_{ij}\tau _{ij}y_{ij}^l+\sum _{i\in I}c_{i} \bar{\tau }_{i}w_i^{rt}-\sum _{i,l\in I}\alpha _{it}x_{il}^{rt}+\sum _{k\in K}\gamma _{kt}q_k^{rt}+\lambda _t \nonumber \\&{\quad }\text {s.t.: }\sum _{i\in I}x_{il}^{rt}\ge \sum _{i\in I}x_{i,l+1}^{rt}, \ \forall l\in I \end{aligned}$$

(6a)

$$\begin{aligned}&{\qquad }x_{il}^{rt}\le \sum _{j\in I}x_{j,l+1}^{rt}+w_i^{rt},\ \forall i,l\in I \end{aligned}$$

(6b)

$$\begin{aligned}&{\qquad }w_{i}^{rt}\le \sum _{l\in I}x_{il}^{rt},\ \forall i\in I \end{aligned}$$

(6c)

$$\begin{aligned}&{\qquad }x_{il}^{rt}+x_{j,l+1}^{rt}-1\le y_{ij}^l,\ \forall i,j,l\in I \text { and } i\ne j \end{aligned}$$

(6d)

$$\begin{aligned}&{\qquad }\sum _{i\in I_k}\sum _{l\in I}x_{il}^{rt}\le |I|q_k^{rt},\ \forall k\in K \end{aligned}$$

(6e)

$$\begin{aligned}&{\qquad }\sum _{i,l\in I}d_i^\varsigma x_{il}^{rt}+\sum _{i,j,l\in I}\tau _{ij}y_{ij}^l+\sum _{i\in I}\bar{\tau }_{i}w_i^{rt}\le L+M(1-\pi _\varsigma ^{rt}),\ \forall \varsigma \in \mathcal {S} \end{aligned}$$

(6f)

$$\begin{aligned}&{\qquad }\sum _{\varsigma \in \mathcal {S} }p_\varsigma \pi _\varsigma ^{rt}\ge 1-\epsilon \end{aligned}$$

(6g)

$$\begin{aligned}&{\qquad }x_{il}^{rt},y_{ij}^{l}, w_i^{rt},q_{k}^{rt},\pi _\varsigma ^{rt}: \text {Binary}\ \forall i,l, j\in I, \varsigma \in \mathcal {S} \end{aligned}$$

(6h)

where $d_i^s$ is the durion of surgery i in scenario s. The objective function is the reduced cost of a sequence consisting of the fixed opening cost, the turnover penalty and the dual variables. Constraint (6a) forbids assigning surgeries to position $l+1$ when no surgery is allocated to position l. Constraints (6b and 6c) ensure that $w_i^{rt}$ takes a value of 1 if surgery i is the last surgery in the sequence. If surgery i precedes surgery j in lth position of the sequence, $y_{ij}^l$ takes a value of 1. This is enforced by constraint (6d). Constraint (6e) states that if a surgery of surgeon k is selected, then $q_k^{rt}=1$. Note that at most |I| surgeries can be assigned to an OR. Constraints (6f and 6g) impose the probability condition using the big M method. The former constraint computes the duration of the sequence consisting of the surgery durations and the surgery turnover times for each scenario. Note that M is a big positive number. The latter ensures that the total probability of the scenario constraints satisfied, is at least $1-\epsilon$.

The feasibility conditions are fulfilled for a sequence if it satisfies the constraints above. The optimality condition is achieved if there exists no sequence with negative reduced cost on the entire branch-and-bound tree of the branch-and-price algorithm.

3 Reformulating the column generation subproblem

Although solving the above integer problem in each iteration is doable, it is not computationally very efficient. Since the aim is to generate a sequence of surgeries that violates (3), we reformulate the column generation subproblem by a shortest path problem on a graph where a sequence corresponds with a path on the graph. In order to guarantee the optimality of the solution, the optimality and feasibility conditions will be defined.

Let us assume that each surgery uniquely corresponds to one node of Graph G(I, E) where E is the set of arcs connecting nodes (surgeries). There exists an arc between node i and node j if they have at least one admissible period in common. Following constraint (3), we define the reduced cost of a sequence and the reduced cost of arc (i, j) by

$$\begin{aligned} \bar{ c}_{s}= & {} c_{s}-\sum _{i\in I_{s_t}}\alpha _{it}+\sum _{k\in K_{s}}\gamma _{k,t}+\lambda _t,\end{aligned}$$

(7)

$$\begin{aligned} \bar{c}_{ij}= & {} c_{ij}\frac{\tau _{ij}}{2}-\frac{\alpha _{it}}{2} -\frac{\alpha _{jt}}{2}+\gamma _{k(j)t}\mathbb {I}_{ks} \end{aligned}$$

(8)

where $\mathbb {I}_{k}$ is an indicator function with value of 1 if the surgeon k is scheduled in the sequence for the first time by surgery j.

Optimality conditions Finding a sequence of surgeries which violates constraint (3) is the same as finding a path with negative length between any pair of nodes in Graph G i.e.,

$$\begin{aligned} \bar{c}_{s}=\sum _{i,j\in I_s}\bar{c}_{ij}+\lambda _t+c_R<0. \end{aligned}$$

If such a path is identified, it will be an improving sequance.

Constrained shortest path problem is a NP-complete problem [27]. Similar shortest path problems can be found in variants of vehicle routing problems. Labelling algorithms such as Bellman-Ford algorithm and Dijkstra’s algorithm can be adopted to search the space and find improving sequences. Following the approach applied in [20] instead of one label, we use a set of labels for each node and define dominating rules to keep only a subset of labels.

Feasibility conditions Feasibility condition (a) states that a sequence is feasible if the sum of the surgery duration and the turnover time is less than or equal to the OR session length (L) with a pre-specified probability ($1- \epsilon$). Mathematically speaking:

$$\begin{aligned} \Pr \left( \sum _{i\in I_{s}}\tilde{d}_i +\sum _{i,j\in I_{s}}\tau _{ij}+ \bar{\tau }_{i^*}\le L\right) \ge 1-\epsilon \end{aligned}$$

(9)

where $i^*$ is the last surgery on the sequence. The closed form of the left-hand side of (9) can be written for distribution functions with the accumulative property such as normal distribution functions. A distribution function has the accumulative property if $\tilde{d}_i, \tilde{d}_j\sim \mathcal {D}$, then $\tilde{d}_i+ \tilde{d}_j\sim \mathcal {D}$. Moreover, the above probability constraint can be verified for the scenario-based case. In all cases, the complexity of the problem remains tractable.

In our search algorithm, this condition can be checked for each sequence in each step. If the feasibility condition is not met, the label associated with the sequence will be omitted from the label set of that surgery even if it is not dominated. It is trivial that an infeasible sequence cannot turn into a feasible sequence in latter iterations, when new surgeries are added to the label set. This condition only prohibits infeasible sequences and does not affect the optimality condition.

Feasibility condition (b) is satisfied when the search algorithm is restricted to induced subgraph $G_t(I_t, E_t)$ whose nodes are admissible in period t i.e., $I_t=\{i| t\in T_i\}$. The resulting induced subgraph for time period t is a complete graph (a clique). Feasibility condition (c) is fulfilled by the search algorithm construction.

The optimality and feasibility conditions at each node of branch-and-bound tree is achieved when no feasible path between any pair of surgeries can be found for which total reduced cost is negative i.e., $\bar{ c}_{s}<0$.

4 The search algorithm

Here, we describe the search algorithm designed based on Dijkstra’s shortest path algorithm to solve the reformulated column generation subproblem. Let $\mathrm{L}(i)$ be a set containing the labels of node i. The $\kappa$th label of node i, denoted by $\mathrm{L}_{\kappa }(i)$, is associated with a path to node i and consists of five components: the total reduced cost ($\bar{c}_{\kappa }(i)$), the expected duration ($\mathrm{d}_{\kappa }(i)$), the period ($\mathrm{t}_{\kappa }(i)$), the operating room ($\mathrm{r}_{\kappa }(i)$), the nodes on the path leading to node i ($\mathrm{p}_{\kappa }(i)$) i.e., ${\small \mathrm{L}_{\kappa }(i)\leftarrow \left( \bar{c}_{\kappa }(i), \mathrm{d}_{\kappa }(i), \mathrm{t}_{\kappa }(i),\mathrm{r}_{\kappa }(i),\mathrm{p}_{\kappa }(i)\right) }$. We denote the ordered list of all the labels by Q. Set Q is arranged on an ascending order based on the labels components respectively.

The introduction of dominating rules depends on the type and the distribution function of uncertain durations. We use the dominating rules introduced in [20]. For instance, when the random surgery duration follows a normal distribution, at each node of the graph, label A dominates label B if (i) the expected duration of the total duration of path A is less than or equal to that of path B, (ii) the variance of the total duration of path A is less than or equal to that of path B and (iii) the reduced cost of path A is at most equal to the reduced cost of path B. These conditions guarantee that label A dominates label B. The dominated labels will be removed from the label set of the node and list Q. The idea is that the dominated path is less likely to become an improving path.

The steps of our search algorithm are outlined below and presented in a pseudo code format in Algorithm 1. The algorithm starts with assigning a label to node i for each feasible OR-period pair. At the beginning, each node has $|T_i|$ labels. Then, the first label in Q is selected and extended for each neighbour of the last node in the given sequence. Surgery j is called a neighbour of surgery i at period t if period t belongs to their admissible time periods, i.e., $\mathcal {N}_t(i)=\{j\in I| t\in T_j\}$. Once a label is selected from Q, we delete it from Q.

We also use a s-cycle-free rule to avoid the negative cycles of size s or less. If the feasibility condition (9) and the s-cycle free condition are held, then the dominating rules are checked. If all conditions are satisfied, a new label associated with the new node is created and saved in the node’s label set and set Q. When the total reduced cost of a sequence/path is negative, we stop and add the sequence to RMP. If no path between each pair of nodes was found, we branch on another variable on the branch-and-bound tree.

5 Computational experiments

In this section, we investigate the efficiency of the proposed method and also the impact of two key features of the underlying problem, namely, uncertain parameters and the objective function. Moreover, using sensitivity analysis and Monte-Carlo simulation, we study the impact of the variation of reliability level ($\epsilon$) on decision variables and objective function.

In order to demonstrate the computational efficiency of the proposed method, we formulate and use a standard chance constrained model for the underlying problem presented in the appendix. The latter model is in fact an integration of Problem (6) over all time periods and ORs with binding constraints. In the standard CCP, the uncertainty is handled by a discrete approximation of random durations.

Due to complexity of handling some distribution functions such as log-normal distribution in chance constrained models, discrete and/or continuous approximations of the distribution function are commonly used in the literature [6]. It is known that surgery duration follows Log-Normal distribution [17] which is not a well-behaved distribution function. In addition to a discrete approximation of Log-Normal distribution function, we use normal distribution as the continuous approximation of distribution function of surgery duration, and then compare the results for both cases.

In terms of the objective function, two types of objective functions have been considered in the literature [7]. The first type minimizes the number of ORs to be opened while the second one takes into account some undesirable operational costs where other performance measures can be controlled. Here we study both types.

In summary, we study three cases of problems:

• 1. Discrete approximation of the random surgery duration with a cost based objective function,

• 2. Continuous approximation of the random surgery duration with a cost based objective function, and

• 3. Continuous approximation of the random surgery duration with an OR based objective function.

5.1 Data set

We used the statistical data provided by Min and Yih [17] which is obtained from an analysis of a real life data. According to our modelling requirements, some adjustments had to be made to the instances as follows. In their data set, surgeons are not included. Therefore, a set of surgeons in proportion to the number of surgeries was defined and surgeries were randomly assigned to them. We assume that each surgery appears only on one surgery list. Also, the set of admissible periods in which a surgery could be performed, was randomly generated. Min and Yih did not report the pre-surgery and post-surgery time. We used the following function to estimate the turnover time between two surgeries: $\tau _{ij}=0.05\bar{d}_i+0.05\bar{d}_j+a,$ where $a=15$ if surgery i and surgery j are performed by the same surgeon i.e., $i,j\in \mathcal {L}_k$ for $k\in K$, and $a=20$ otherwise. We would add 20 minutes to the turnover time for an extra cleaning if the preceding patient had some infectious disease. The penalty cost for every minute of turnover time was considered to be 1, i.e., $c_{\omega }=1$. In our experiment, the probability of exceeding session length was set to 0.10 i.e., $1-\epsilon =0.90$. We chose the rest of parameters as in [17]: $L=480, \ c_R=6240, \ T=480 \text { minutes}$ and the number of available ORs was set to 10. Note that such parameter settings are not restrictive for our method and can be changed in other realistic situations.

In Case 1, we consider 100 scenarios of surgery durations randomly generated based on the Log-normal distribution of the surgery duration presented in [17]. For Case 2, we assume that a surgery duration follows a normal distribution with the mean and standard deviation reported in [17].

The test problems are categorized in three groups “small”, “medium” and “large” and labelled by the number of the surgeries followed by the number of surgeons e.g., $\mathtt {s15-g7}$ consists of 15 surgeries and 7 surgeons. We generated 10 test instances for each size of problems.

When the random surgery durations are modelled by a finite set of discrete approximations (i.e., scenarios) $\mathcal {S}$ where the probability of realizing scenario $\varsigma$ is $p_\varsigma$, then the chance constraint (9) is written by $\Pr (\sum _{\varsigma \in {\mathcal {S}}}p_\varsigma \mathbb {I}{I}_\varsigma )\ge 1-\epsilon$ where $\mathbb {I}{I}_\varsigma$ is an indicator function and is equal 1 if for scenario $\varsigma$,

$$\begin{aligned} \sum _{i\in I_s}d_i^\varsigma +\sum _{i,j\in I_{s}}\tau _{ij}+\bar{\tau }_{i^*}\le L. \end{aligned}$$

For cases 2 and 3, we assume that the durations follow normal distributions i.e., $\tilde{d}_i\sim \mathcal {N}(\mu _i, \sigma ^2_i)$ where $\mu _i$ and $\sigma ^2_i$ are the mean and the variance of the duration of surgery i. The corresponding chance constraint is then reformulated by

$$\begin{aligned} \Pr \left( \frac{\sum _{i\in I_s}(\tilde{d}_i-\mu _i)}{\sum _{i\in I_s}\sigma _i}\le \frac{\bar{L}-\sum _{i\in I_s}\mu _i}{\sum _{i\in I_s}\sigma _i}\right) =\Pr \left( \mathcal {Z}\le \frac{\bar{L}-\sum _{i\in I_s}\mu _i}{\sum _{i\in I_s}\sigma _i}\right) \ge 1-\epsilon \end{aligned}$$

where $\bar{L}=L-\sum _{i,j\in I_{s}}\tau _{ij}-\bar{\tau }_{i^*}$ and $\mathcal {Z}$ is the standard normal distribution random variable.

5.2 Numerical results

In this section, we compare in total nine performance measures categorized into two types: optimization and simulation related measures for our proposed branch-and-price method denoted by proposed method, and the standard formulation of CCP presented by (10) denoted by CPLEX. The optimization related measures investigate the efficiency of the proposed framework and the quality of the optimal solution. Here, we consider six measures in this category as follows: (1) solution time, (2) the integrality gap after 7200 s, (3) the number of variables (sequences) generated during the solution procedure, (4) the number of ORs opened, (5) the objective function value denoted ($z^*$) and (6) the surgeon waiting time denoted by “Srgn. wait” (minutes). The surgeon waiting time reports the expected time a surgeon must wait between two surgeries of his/her surgery list in a time period.

In the second category, we carry out a Monte Carlo Simulation to evaluate the obtained optimal solution of an instance. To this end, 10,000 scenario realizations based on the surgery duration distribution function are generated. Then for the solution obtained by solving the model and for each scenario, the following performance measures are computed. Finally, the average values of these measures are calculated and reported in the tables. The performance measures are (1) the average reliability of the solution for exceeding the session length ($\frac{\sum _{r=1}^{m'}(\sum _{s\in \mathcal {S}} p_s|\tilde{D}_r>L)}{m'}$), denoted by “Prob. Exceed.”, (2) the average expected time of exceeding session length for open ORs i.e., $\frac{\sum _{r=1}^{m'}{{\mathrm{\mathbb {E}}}}[\tilde{D}_r-L]^+}{m'}$ in minutes, denoted by “Overtime”, and (3) the average of the expected time of unused session length i.e., $\frac{\sum _{r=1}^{m'}{{\mathrm{\mathbb {E}}}}[L-\tilde{D}_r]^+}{m'}$ in minutes, denoted by “Unus. Cap.” where $m'$ is the total number of final sequences,¹ $[a]^+=\max (a,0)$ and $\tilde{D}_r$ is the total duration of surgeries assigned to OR r.

We implement the set-partitioning based models in SCIP (Solving Constraint Integer Programming) software. To demonstrate the computational efficiency of the proposed method, we implement the standard CCP model is in ILOG IBM CPLEX 12.51 since this software is commonly used and also is known to be a very powerful branch-and-cut solver. The models are run on a OSX with 3.1 GHz Intel Core i5 and 8 GB of memory. We give another advantage to the standard CCP model by letting ILOG IBM CPLEX to use its parallel computing feature, while SCIP can only use one processor during solving the instances. Finally, we set 7200-s limitation of the solution time.

5.2.1 Efficiency of the method

In order to demonstrate the efficiency of the proposed approach, we compare our results firstly with those of related works in the literature, and secondly with those obtained from solving the same instances by the standard chance constraint model using ILOG IBM CPLEX. The latter also demonstrates the correctness of our approach.

Neyshabouri and Berg [19] use the same data set i.e., [17]. They applied robust optimization to their problem and were able to solve up to 40 surgeries. Although they consider downstream activities, they do not take into account surgeons and turnover time. In another related paper, Batun et al. [4] formulated their problem by a two-stage stochastic integer model. The largest instances that they were able to solve, consist of 11 surgeries, 3 surgeons, and 6 ORs in a surgical day. A set of 500 scenarios is used to represent the uncertainty. Using a progressive hedging algorithm, Gul et al. [12] found near optimal solutions for instances up to 50 surgeries for a planning period of 10 days. They do not consider surgeons in their problem, but they include cancelation cost.

We solve instances of Case 1 using the proposed method by SCIP and the standard CCP model by ILOG IBM CPLEX 1251. ILOG IBM CPLEX solved $\mathtt {s4-g4}$ with 100 scenarios in 7.10 s, but it was unable to solve or find an integer solution for any other instances. These cases are indicated by “NS” (Not Solved) in Table 1. This table and Table 2 report the results of Case 1 and the standard model. As the results present, the proposed method was able to solve all instances to optimality except the last one for which the integrality gap was 1 percent. Table 2 provides more details of Case 1 including solution time and integrality gap. Linear programming (LP) relaxation of the instances is solved to find a lower bound and the LP relaxation gap for the standard model. We use the optimal solution obtained by the proposed method to compute the LP relaxation gap. As expected, LP relaxation provides a poor lower bound for this class of problem. The solution time for the LP relaxation of the instances reported are considerably high such that instance $\mathtt {s51-g13}$ was solved in over 5 h and the model for the last instance ($\mathtt {s60-g13}$) was not even constructed after 2 h of time limit so the lower bound for this case was not available (indicated by “NA”). In contrast with the standard model which generated a large number of binary variables in the beginning, the proposed method was able to solve the instances to optimality with much fewer variables. The number of variables for the standard model presented in the table, is the number of variables in the reduced problem provided by ILOG IBM CPLEX pre-solution procedure which reduces the problem size prior to passing to its optimizer. As the results suggests, our proposed method was significantly faster to solve the instance and lead to the same solution and the same objective function value of the standard model.

Table 1 The average performance measures for verifying the correctness of the proposed method against the standard CCP model

Table 2 The average performance measures of the proposed method for 10 test problems of each instance size for Cases 1 and 2

Table 2 reports the average results of solving Cases 1 and 2 for the following performance measures: the solution time, the integrality gap (percent) after 7200 s and the number of variables added to the master problem. As the table shows, the proposed method was very quick to solve small and medium instances. The solutions obtained for the large instances were very close to the optimality with maximum 2% gap on average for the test instances of $\mathtt {s60-g13}$. The solution time and the number of sequences (variables) added to the problems were considerably higher in Case 1 in comparison with Case 2. The reason is that the continuous approximation is more conservative and a sequence which is feasible under the assumption of Case 1 may not be feasible under the assumption of Case 2. Therefore, the search space is more limited in Case 2. In the next sections, in order to be able to compare the results of cases, the result of only one test problem is reported for each instance.

5.2.2 Case 1 versus case 2

It is common to use the discrete scenario approximation of uncertain parameters in stochastic programming, however, its accuracy highly depends on the size of scenario set which usually affects the solution quality and the computational efficiency. The larger of scenario set, the better solution quality and the poorer computational efficiency. In Table 3, we investigate the quality of the solution for Case 1 and case 2. While the number of the ORs opened and the objective function value are higher in Case 2, the expected probability of failure obtained by Monte Carlo simulation, is considerably lower in Case 1. Column “Prob. Exceed” and also the “Average” row show that Case 1 does not hold the probabilistic constraint of the session length i.e., the solutions do not meet constraint (9) requirements. As a result, the expected exceeding time and its average are larger in Case 1. Smaller unused capacity is preferred only when constraint (9) is held, which is not the case in Case 1. The conclusion is that when we can incorporate the distribution function or a relatively good continuous approximation for the chance constraints, there may be no gain in terms of the solution quality and the computational efficiency to use the discrete approximation of the original distribution function specially since the scenario generation itself is a complicated task. Furthermore as the integrality gap suggests, the continuous approximation of the surgery duration did not increase the complexity of the resulting problem and all instances were solved to optimality in the time limit.

Table 3 The comparison of the performance measures for Case 1 and Case 2

5.2.3 Case 2 versus case 3

Here, we compare two types of the objective functions. As mentioned earlier, Case 3 is similar to Case 2 except in its objective function in which only ORs’ opening cost is minimized i.e., $\min \sum _{t\in T}\sum _{s\in S_t}c_{s}u_{s}$ where $c_s=c_R$. Including turnover penalty in the objective function has two consequences. First, it is highly possible to have multiple optimal solutions in Case 3 that results in opening the same number of ORs with different assignments. In the presence of the turnover penalty, those solutions with the minimum total duration is chosen. As reported in Table 4, the number of ORs opened in all the instances for the both models are the same while the overtime and the unused capacity of Case 2 are in all the cases smaller (except two cases) and bigger than those of Case 3, respectively.

Table 4 The comparison of the performance measures for Case 2 and Case3

Secondly, a proper choice of turnover penalty could reduce the surgeons’ waiting time or could result in a desired arrangement for surgeons. As mentioned in the data set explanation, the turnover time between two surgeries is less if the two surgeries are performed by the same surgeon. Therefore, by assigning higher penalty to turnover times in the objective function, the model tends to put all the surgeries assigned to a surgeon in a row if it is feasible to do so. As a result, the surgeon waiting time is minimized indirectly. This is achieved without changing our model or increasing the computational complexity. Figure 1 illustrates an example for two sequences of the optimal solution for Instance $\mathtt {s51-g13}$ based on Case 3. In this figure, the empty red boxes present the turnover time and the numbers in and above the blue boxes indicates the surgeries’ and the surgeons’ codes, respectively. As can be seen, there is a gap between two surgeries of surgeon 5 and surgeon 7. Therefore, they will have to wait to perform their next surgeries. Considering positive turnover penalty cost can avoid the waiting time by rearranging the surgeries while the total number of in-service ORs are kept at the same level. This issue has been mainly neglected in the literature.

Column “Srgn. waiting” in Table 4 reports the surgeon waiting time and the average for all the instances. In Case 3 surgeons have to wait up to 180 min while with the same number of in-service ORs, the surgeon’s waiting time is zero in Case 2.

5.3 Sensitivity analysis

Choosing input parameter $\epsilon$ has a significant impact on the decision variables and the objective function value. In addition to OR opening cost and turnover penalties, there exist two other costs associated with violating session lengths and unused capacity in ORs opened. Due to randomness of the surgery durations, the OR session length is either violated or left unused for each value of $\epsilon$. The both situations result in costs and may not be desirable for the hospital management. The amount of overtime is in conflict with the unused capacity in opened ORs. The hospital management would like to choose a value for $\epsilon$ in which the total cost consisting of the objective function and the costs associated with overtime and unused capacity, are minimum. This trade-off has been mainly neglected in the literature. Including these two in the formulation phase makes the problem more difficult to model and solve. Although in theory this integration can be done within the two-stage chance constrained programming framework, only very small instances under a limited setting can be solved [13]. Instead, the sensitivity analysis for $\epsilon$ provides us with useful information to choose the right value of $\epsilon$ for which the total cost is minimized.

Fig. 1

Schedules of instance $\mathtt {s51-g13}$ illustrating the gaps between surgeries of a surgeon in the optimal solution of Case 3

Table 5 The sensitivity of the solution to variations in $\epsilon$

In this section, we study the impact of $\epsilon$ on the total cost defined above. We focus on the sensitivity of four measures including the number of OR opened, the objective function and the average of the expected values of the overtime and the unused capacity, with respect to the variation of $\epsilon$. In addition to $\epsilon =0.10$, six other values for $\epsilon$ i.e., $\epsilon \in \{0.01, 0.05, 0.15,0.20.0.25,0.30\}$ are chosen.

Due to lower semi-contnuity of the objective function with respect to $\epsilon$, an increase (or decrease) in $\epsilon$ does not necessarily lead to an increase (or decrease) in the objective function and the number of the ORs opened. As reported in Table 5, the results show that the number of ORs opened is less sensitive to the variations in $\epsilon$ than the objective function value. This observation suggests that in order to achieve a more reliable solution, we do not always need to increase the number of in-service ORs but it can be done by improving the assignment of surgeries to the ORs.

The chance constraint (9) is directly connected to the overtime; therefore although not continuously, the overtime increases by $\epsilon$. This trend can be seen in our results, see Column “Overtime” of Table 5. An opposite behaviour is expected for the unused capacity. However, our results shows that the behaviour of the unused capacity cannot be linearly predicted since it has not been explicitly considered in the problem.

Table 6 The sensitivity analysis for Instance $\mathtt {s60-g13}$

We further extend our experiment for $\mathtt {s60-g13}$ and solve the instance for $\epsilon =0.35, 0.40, 0.45$ and 0.50. We compute four measures: the mean, standard deviation, 95% quantile and worst case values of the simulation experiment for the overtime and unused capacity. The results are reported in Table 6. The objective function and the number of ORs opened decrease as $\epsilon$ increases. Figure 2 illustrates the trend of changing the distribution for the overtime and unused capacity when $\epsilon$ changes. The upper bound of the interval is 95% quantile and its lower bound is $\bar{x}-(q-\bar{x})$ if it is not negative and otherwise zero, where $\bar{x}$ and q are the mean and 95% quantile of overtime or unused capacity. Note that in the figure the cost functions are not continuous as presented. For the sake of presentation, the segments between the points are drawn.

The results suggests that although very small values of $\epsilon$ result in very small overtime, they lead to very high unused capacity and impose unnecessary costs. Given the above information and the hospital’s strategy, hospital managers can choose a right value for $\epsilon$ to male a reasonable trade-off between their operation cost.

Fig. 2

Sensitivity analysis for Instance $\mathtt {s60-g13}$. The intervals show the 95 quantile and illustrate the trend of changing the distribution for the overtime and unused capacity when $\epsilon$ changes

6 Conclusion

We have studied an integrated surgery scheduling and planning problem with uncertain surgery durations. The uncertainty in OR capacity constraints is treated by chance constrained programming. The resulting problem is challenging due to its structure which is a combination of stochastic optimization and integer programming. We propose a set-partitioning formulation for the underlying problem. The associated column generation subproblem is decomposed over ORs and time periods. The subproblem is then reformulated as a shortest path problem for which a search algorithm has been devised using the optimality and feasibility conditions. This reformulation allows incorporating distribution functions as well as scenario representation of surgery durations into the chance constraints while keeping the complexity of the problem tractable. A significant reduction in solution time has been achieved due to efficiently solving the resulting shortest path problem. Computational results show that the proposed method is able to solve larger instances of the problem than those previously reported for a similar setting.

An extensive simulation study has been performed to assess the quality of optimal solutions. Several performance measures including the surgeons’ waiting time, expected probability of exceeding OR session length, expected overtime and unused capacity have been evaluated. In comparison with discrete scenarios, working with a continuous approximation of distribution functions for surgery durations lead to reduction of the expected probability of exceeding OR session length and overtime. However, the unused capacity would be increased. Our computational results suggest that adding a proper turnover penalty cost to the objective function would reduce the surgeons’ waiting time while the number of in-service ORs, overtime and unused capacity would change slightly.

A sensitive analysis has been carried out to investigate the impact of the probability of exceeding OR session length on the number of opened ORs, OR overtime and unused capacity. We conclude that a high reliability level for holding OR session length constraint is not always the best choice as it may impose unnecessary costs.

The performance of the proposed method highly depends on the search space of the column generation subproblem and efficiency of the employed branch-and-bound method. The size of search space increases with the number of surgeons, number of planning horizon and number of surgeries. We used a modified dynamic programming search algorithm to solve the reformulated subproblem. The efficiency of the proposed method could be improved by running faster algorithms such as meta heuristics.

To extend this work, one could solve a more practical problem by taking OR downstream activities into account. The proposed method may also be applied to other situations where probabilistic bin packing constraints exist.

Appendix: Standard chance constrained model for the stochastic surgery scheduling problem

Here, we present the standard chance constrained equivalent model using the popular scenario based chance constrained programming [14]. The notation for column generation (6) are used to define the standard model. The additional binary variables $z_r^t$ and $q_k^{r,t}$ indicate if OR r is used in period t, and if surgeon k is allocated to OR r in period t.

$$\begin{aligned}&\min \sum _{r\in R}\sum _{t\in T}c_Rz_r^t+\sum _{i\in S}\sum _{j\in I}\sum _{l\in I}c_{ij}\tau _{ij}y^l_{ij}+\sum _{i\in I}\sum _{t\in T_i}\sum _{r\in R}c_{i}\bar{\tau }_iw_i^{rt} \end{aligned}$$

(10a)

$$\begin{aligned}&\text {s.t.: }\sum _{l\in I}\sum _{r\in R}\sum _{t\in T_i}x_{i,l}^{r,t}=1, \ \forall i\in I \end{aligned}$$

(10b)

$$\begin{aligned}&{\qquad }\sum _{l\in I}x_{il}^{rt}\le z_r^t,\ \forall i\in l\in I, r\in R,t\in T \end{aligned}$$

(10c)

$$\begin{aligned}&{\qquad }\sum _{i\in I_k}\sum _{l\in I}x_{il}^{rt}\le Mq_k^{rt},\ \forall k\in K, \ r\in R, t\in T \end{aligned}$$

(10d)

$$\begin{aligned}&{\qquad }\sum _{r\in R}q_{k}^{rt}\le 1,\ \forall k\in K, \ t\in T \end{aligned}$$

(10e)

$$\begin{aligned}&{\qquad }\sum _{i\in I}x_{il}^{rt}\ge \sum _{i\in I}x_{i,l+1}^{rt},\ \forall l\in I, \ r\in R, \ t\in T \end{aligned}$$

(10f)

$$\begin{aligned}&{\qquad }x_{il}^{rt}\le \sum _{j\in I}x_{j,l+1}^{rt}+w_i^{rt},\ \forall i, l\in I, \ r\in R, \ t\in T \end{aligned}$$

(10g)

$$\begin{aligned}&{\qquad }w_{i}^{rt}\le \sum _{l\in I}x_{il}^{rt},\ \forall i\in I, \ r\in R, \ t\in T \end{aligned}$$

(10h)

$$\begin{aligned}&{\qquad }\sum _{t\in T}x_{il}^{rt}+\sum _{t\in T}x_{j,l+1}^{rt}-1\le y_{ij}^l\ \forall i, l\in I, \ r\in R, \ t\in T \end{aligned}$$

(10i)

$$\begin{aligned}&{\qquad }y_{ii}\ge x_{i0}^{rt}\ \forall i\in I, \ r\in R, \ t\in T \end{aligned}$$

(10j)

$$\begin{aligned}&{\qquad }\sum _{i,l\in I}d_i^\varsigma x_{il}^{rt}+\sum _{i,j\in I}\tau _{ij}y_{ij}^l+\sum _{i\in I}\bar{\tau }_{i}\delta _i^{rt}\le \text {L}+M(1-\pi _\varsigma ^{rt}),\ \forall r\in R,\ t\in T,\varsigma \in \mathcal {S} \end{aligned}$$

(10k)

$$\begin{aligned}&{\qquad }\sum _{\varsigma \in \mathcal {S}}p_\varsigma \pi _\varsigma ^{rt}\ge 1-\alpha , \ \forall r\in R,\ t\in T \end{aligned}$$

(10l)

$$\begin{aligned}&{\qquad }\sum _{r=1}^{\min \{k,|R|\}}q_k^{r,t}\le \sum _{r=1}^{\min \{k,|R|\}}z_r^{t}, \ \forall k\in K, \ t\in T \end{aligned}$$

(10m)

$$\begin{aligned}&{\qquad }x_{il}^{rt},y_{ij}^{l}, z_r^t,w_i^{rt},q_{k}^{rt},\pi _\varsigma ^{rt}: \text {Binary}\ \forall i,l, j\in I, \varsigma \in \mathcal {S}, r\in R,\ t\in T . \end{aligned}$$

(10n)

The objective function computes the opening cost and the penalty cost. Constraint (10b) corresponds with the first constraint of SP ensuring every surgery is assigned to a OR at some period. Note that $v_{it}=\sum _{l\in I}\sum _{r\in R}x_{i,l}^{r,t}$. Constraint (10c) enforces the limitation of the available ORs at each period i.e., $z_r^t$ to take a value of 1 if at least one surgery is assigned to OR r in period t. This constraint is associated with constraint (1e). Constraints (10d and 10e) are related to constraint (6e) forbidding the assignment of a surgeon to more than one OR in each period. Constraints (10f–10j) determine the arrangement of each sequence. In SP, this is presented by variable $u_{s_t}$ through the column generation problem. Finally, constraint (10k–10l) impose the probabilistic condition on the OR available length via a scenario-based chance constraint. These constraints are equivalents of the column generation feasibility condition (9). Constraint (10m) is a symmetry breaking constraint and implies that surgeon 1 is assigned to OR 1, surgeon 2 can be assigned to OR 1 and OR 2 and so on. Finally, Constraints (10n) enforce the integrality conditions on the decision variables.