Keywords

1 Introduction

Hospital management is critical to improving the quality of service to patients [19]. Surgeries account for most of the hospital revenue and expenditure [15, 18]. Efficient surgical management is required to achieve optimal hospital management. By clarifying the cost structure underlying operating room time, Dexter and Macario revealed that improved operating room scheduling can effectively reduce costs [8]. Creating a robust operating room schedule is effective in managing the operating room.

In the flow of the operating room scheduling, the surgeon and patient decide the surgery date through mutual agreement. The surgeon then reports the surgery date and estimated duration of surgery to the operating room manager. The manager decides when and in which operating room to perform the surgery based on information such as the estimated duration of surgery and department.

It is the issue of operating room management that surgery is often not performed according to the schedule. The quality of service to patients is affected because of the waiting time occurrence owing to the delay from the scheduled end time of surgery. Surgical duration is uncertain, influenced by the patient’s condition, lack of information on the preoperative diagnosis, and the surgeon’s skill. The challenge is to cope with the uncertainty of the surgical duration.

The manager desires to avoid a risk of delay, with surgery being delayed significantly from the scheduled end time. Long delays lead to increased overtime for surgical staff, not only increasing costs, but also reducing staff satisfaction. In operating room scheduling, it is necessary to consider decision-making to avoid the risk of delay.

In this study, we propose a robust optimization model that considers surgical procedures and minimizes delay from the regular opening time of the operating room. After calculating the delay for uncertain surgical duration parameter sets in the numerical analysis and comparing the performance of the proposed model to those of the stochastic programming model, we verify whether risk avoidance tendencies are reflected in schedules. In the proposed model, we consider multiple operating rooms that could not be considered in Namba et al. [14].

From the numerical results, three important points are obtained as follows:

  • Robust optimization tends to avoid long delays.

  • Robust optimization, which has only information on the 10th and 90th percentile duration of the scenario, exhibits the same performance as stochastic programming, which has complete information on the scenario in specific control conservative.

  • Robust optimization obtains a solution faster than stochastic programming because the number of variables and constraints in robust optimization is smaller than in stochastic programming.

The remainder of the paper is organized as follows: Sect. 2 provides a literature review. Section 3 introduces the problem setting and robust optimization model of operating room scheduling. In Sect. 4, we describe the data used in the study and report the results of our numerical experiments. We conclude the paper in Sect. 5 with comments regarding matters for future exploration.

2 Literature Review

Operating room scheduling has been studied extensively [5, 10, 20]. A few studies have proposed a stochastic model for operating room scheduling [2, 9, 17]. Batun et al. [4] presented a two-stage stochastic mixed-integer programming model with uncertain surgical duration. Addis et al. [1] proposed the operating room rescheduling with uncertain patient arrival and surgical duration. Kamran et al. [16] approached the operating room scheduling problem with different formulations of stochastic programming. Ito et al. [11, 12] proposed a stochastic programming model for scheduling an operating room using the conditional value-at-risk (CVaR). The CVaR expresses the risk-aversion of the manager towards the risk that the surgical duration estimated by the surgeon could be significantly delayed. Another technique that reflects delayed risk aversion is robust optimization. Bandi and Gupta [3] developed a new criterion and a robust optimization approach for staffing and operating room scheduling problems under uncertain case mix and case lengths. Denton et al. [6] proposed an operating room scheduling model with robust optimization to address the uncertain surgical duration.

Our work is somewhat related to Denton et al. [6], but is particularly different in that their study did not address the sequence of surgeries in the operating room. It is important to consider the sequence of surgeries within the operating room [7]. The manager is making efforts regarding the order of surgeries, e.g., surgeries belonging to the same department consecutively perform when arranging surgical equipment and adjusting schedules.

3 Operating Room Scheduling

3.1 Robust Optimization

We propose a robust optimization model for the operating room scheduling problem under uncertain parameter sets; the worst-case that results in maximum total surgical duration. The operating room scheduling determines the allocations to an operating room and surgery procedures.

Surgeries are limited to elective surgeries with prior consent between the patient and surgeon; thus, we did not consider the interruption of emergency surgery. In addition, all operating rooms are treated with the same function. We define surgical duration as the difference between a patient’s entry times and when the patient leaves the operating room.

The formulation of the maximum surgical duration problem, which is considered the main problem, is presented in Sect. 3.2. The formulation of the operating room scheduling problem is shown as follows:

Notation

Index sets.

  • J: Set of surgeries.

  • D: Set of departments.

  • \(E_d\) (\(d \in D\)): Set of surgeries belonging to the department d.

  • M: Set of operating rooms.

Parameters.

  • \(d_{m} (m \in M)\): Regular opening time of the operating room.

  • \(n_{d} (d \in D)\): Number of surgeries in department d, \(n_{d}=|E_d|\).

  • \(\overline{p_j}, \underline{p_j} (j \in J)\): Upper and lower bounds on the duration for surgery j.

  • \(\tau \): Control conservative. Set how conservatively you want to control the worst-case scenario from the decision-maker’s perspective. This represents the number of surgeries for which the upper bound of the surgical duration is reached.

Variables.

  • \(p_j (j \in J)\): Duration of surgery j.

  • \(c_j (j \in J)\): Finishing time of surgery j.

  • \(t_m (m \in M)\): Delay from the regular opening time of the operating room.

  • \(z_{ij} (i, j \in J, i \ne j)\): Binary variable for surgery precedence, where \(z_{ij}=1\) if surgery i is processed before surgery j, \(z_{ij}=0\) otherwise.

  • \(x_{mj} (m \in M, j \in J)\): Binary variable for surgery assignment to the operating room, where \(x_{mj}=1\) if in operating room m, surgery j is assigned, \(x_{mj}=0\) otherwise.

  • \(\gamma _{mij} (m \in M, i, j \in J, i \ne j)\): Linearized binary variables, where \(\gamma _{mij}=1\) if in operating room m, surgery i precedes surgery j, \(\gamma _{mij}=0\) otherwise.

  • \(\theta _{m} (m \in M)\): Linearized binary variables, where \(\theta _{m}=1\) if surgeries l and k in the department d perform in operating room m, \(\theta _{m}=0\) otherwise.

  • \(\alpha , \beta _{j} (j \in J)\): Dual variables. Formulation Minimize

    $$\begin{aligned} \sum _{m \in M}t_{m} \end{aligned}$$
    (1)

    subject to

    $$\begin{aligned} \sum _{i \in J}p_{j}x_{mj} \le d_{m}+t_m, \quad \forall m \in M, \end{aligned}$$
    (2)
    $$\begin{aligned} \sum _{m \in M}x_{mj} =1, \quad \forall j \in J, \end{aligned}$$
    (3)
    $$\begin{aligned} z_{ij}+z_{ji} =1, \quad i \ne j, \forall i, j \in J, \end{aligned}$$
    (4)
    $$\begin{aligned} z_{ij}+z_{jk} + z_{ki} \le 2, \quad i \ne j, j \ne k, k \ne i, \forall i, j, k \in J, \end{aligned}$$
    (5)
    $$\begin{aligned} \sum _{j \in J}jx_{(m-1)j} \ge \sum _{j \in J}jx_{mj}, \quad m =2, ..., |M|, \end{aligned}$$
    (6)
    $$\begin{aligned} \sum _{m \in M}mx_{mi}-\sum _{m \in M}mx_{mj}=(|M|-1)z_{ji}, \quad i \ne j, \forall i, j \in J, \end{aligned}$$
    (7)
    $$\begin{aligned} \sum _{i \in E_d}\sum _{j \in J}z_{ij}=\frac{n_d(n_d+1)}{2}, \quad \forall d \in D, \end{aligned}$$
    (8)
    $$\begin{aligned} \sum _{m \in M}\theta _m \ge 1, \end{aligned}$$
    (9)
    $$\begin{aligned} \sum _{j \in J}(p_{j}-\underline{p_{j}}) \ge \alpha \tau +\sum _{j \in J}(\overline{p_{j}}-\underline{p_{j}})\beta _j, \end{aligned}$$
    (10)
    $$\begin{aligned} \frac{1}{\overline{p_{j}}-\underline{p_{j}}}\alpha +\beta _j \ge 1, \quad \forall j \in J, \end{aligned}$$
    (11)
    $$\begin{aligned} \underline{p_{j}} \le p_{j} \le \overline{p_{j}}, \quad \forall j \in J, \end{aligned}$$
    (12)
    $$\begin{aligned} \gamma _{mij}+1 \ge z_{ji}+x_{mi}, \quad \forall m \in M, i \ne j, \forall i, j \in J, \end{aligned}$$
    (13)
    $$\begin{aligned} 1-x_{ml}-x_{mk}-\theta _m \ge 0, \quad \forall l, k \in E_d, \forall m \in M, \forall d \in D, \end{aligned}$$
    (14)
    $$\begin{aligned} x_{ml}-\theta _m \ge 0, \quad \forall l \in E_d, \forall m \in M, \forall d \in D, \end{aligned}$$
    (15)
    $$\begin{aligned} t_m \ge 0, \quad \forall m \in M, \end{aligned}$$
    (16)
    $$\begin{aligned} \alpha \ge 0, \end{aligned}$$
    (17)
    $$\begin{aligned} \beta _j \ge 0, \quad \forall j \in J, \end{aligned}$$
    (18)
    $$\begin{aligned} z_{ij} \in \{0, 1\}, \quad i \ne j, \forall i, j \in J, \end{aligned}$$
    (19)
    $$\begin{aligned} x_{mj} \in \{0, 1\}, \quad \forall m \in M, \forall j \in J, \end{aligned}$$
    (20)
    $$\begin{aligned} \gamma _{mij} \in \{0, 1\}, \quad \forall m \in M, i \ne j, \forall i, j \in J, \end{aligned}$$
    (21)
    $$\begin{aligned} \theta _{m} \in \{0, 1\}, \quad \forall m \in M. \end{aligned}$$
    (22)

    In the above formulation, the objective function (1) minimizes the total delay from the regular closing time of the operating room. Constraint (2) determines delay based upon the surgical duration and regular closing time of operating room m. Constraint (3) ensures that only one surgery is performed at a time. Constraints (4) and (5) are partial circuit constraints for surgery assignments. Constraints (6) and (7) prevent symmetry in surgery assignments. Constraint (8) ensures that surgeries in the same department are performed in succession. Note that the constraint has a hidden constraint; surgeries in the same department are assigned last of the operating room. Constraint (9) ensures that surgeries in the same department are performed in the same operating room. The right-hand side of constraint (10) is the objective function value of the dual problem, and constraint (11) is the constraint for the dual problem. Here, the dual problem is the complement problem of maximizing the total duration of the surgery in the next section. Constraint (12) limits the upper and lower bounds of surgical duration. Constraint (13) is a constraint on the linearization variable \(\gamma _{mij}\). Constraint (14) and (15) are constraints on the linearization variable \(\theta _m\). Constraints (16)–(18) are non-negative constraints on variables \(t_m\), \(\alpha \), \(\beta _j\). Constraints (19)–(22) are binary variable constraints on variables \(z_{ij}\), \(x_{mj}\), \(\gamma _{mij}\) and \(\theta _{m}\).

3.2 Surgical Duration Uncertainty

Real-world surgical durations are often subject to uncertainties. A robust optimization model with uncertainty may be more suitable and reasonable for decision-making. We assume that the uncertain surgical duration \(\tilde{q}_j\) for surgery j is with respect to the uncertainty set, without assumptions on distribution. This assumption eliminates the need for accurate distribution information and enables the scheduling using only limited information, such as the average, minimum, and maximum values of data. Variable \(\tilde{q_j}\) is defined \(\tilde{q_j}=p_j-\overline{p_j}\), \(\forall j \in J\). The formulations are as follows:

Maximize

$$\begin{aligned} \sum _{j \in J}\tilde{q}_j \end{aligned}$$
(23)

subject to

$$\begin{aligned} \sum _{j \in J}\left( \frac{\tilde{q_j}}{\overline{p_j}-\underline{p_j}}\right) \le \tau , \end{aligned}$$
(24)
$$\begin{aligned} 0 \le \tilde{q_j} \le \overline{p_j}-\underline{p_j}, \quad \quad \quad \quad \quad \quad \forall j \in J. \end{aligned}$$
(25)

The objective function (23) maximizes the total surgical duration. Constraint (24) limits worst-case scenarios by conservative \(\tau \). Worst-case scenarios represent the number of surgeries for which the upper bound of the surgical duration is reached. Constraint (25) defines the possible range of uncertain surgical duration \(\tilde{q_j}\).

4 Numerical Analysis

4.1 Data

In the following analysis, we used a dataset based on Ito et al. [13]. We solved the scheduling problem of five operating rooms and eleven surgeries using Gurobi 9.5.1. We compared the schedule created using the robust optimization model with that created using the stochastic programming model. The computational equipment is an Intel(R) Core (TM) i7-7500U CPU 2.90 GHz 8.00 GB.

The time from the operating room opening to the time when surgery j should be completed, \(d_m\) is 8 h or 480 min. It is desirable that all surgeries be completed within the regular opening time \(d_m\). There are ten departments, i.e., \(|D|=10\). Surgeries 1 and 2 were in the same department. Table 1 shows the expected value \(\mathbb {E}_j[p_j]\) and standard deviation \(\sigma _j\) of the duration of surgery j. The upper \(\overline{p_j}\) and lower \(\underline{p_j}\) bounds on the surgical duration used in robust optimization were the 10th and 90th percentiles of the duration in surgical scenarios. The conservative \(\tau \) varied from 0 to 10 with 1. We assumed that the occurrence probability of the 1000 scenarios used in the stochastic programming model followed a uniform distribution, and the surgical duration in each scenario followed a log-normal distribution. We used the stochastic programming model proposed by Ito et al. [12].

Table 1. Expected value and standard deviation of surgical duration (min).
Full size table

4.2 Results

Figure 1 shows the results of total delay under different \(\tau \) of robust optimization. The total delay of the stochastic programming is shorter than that of the robust optimization for all control conservatives because the surgical scenarios in the stochastic programming are used. The surgical scenario refers to a combined set of the duration of surgery. From Fig. 1, when the control conservative \(\tau \) is 6, the total delay of the robust optimization shows a value equivalent to that of the stochastic programming. Figure 2 shows the number of schedule scenarios with an excessive delay of 1000 min or more. From Fig. 2, when the control conservative \(\tau \) is 6, the number of schedule scenarios with an excessive delay also shows an equivalent value in robust optimization and stochastic programming. In the above results, the robust optimization, which has only information on the 10th and 90th percentile duration of the scenario, exhibits the same performance as the stochastic programming, which has complete information on the scenario in specific control conservative. The robust optimization does not require the estimation of accurate distribution.

Fig. 1.
figure 1

Results of total delay.

Full size image
Fig. 2.
figure 2

Number of schedule scenarios with an excessive delay of 1000 min or more, ‘-’: result obtained by stochastic programming.

Full size image

Table 2 provides the CPU times required to obtain robust optimization and stochastic programming solutions for a single instance as the constant control conservative varies. From Table 2, the CPU time of the robust optimization is shorter than that of the stochastic programming in all cases. From the above results, robust optimization can obtain a solution faster than stochastic programming because the number of variables and constraints in robust optimization is smaller than in stochastic programming. The robust optimization involves 1,311 constraints and 759 variables, while the stochastic programming comprises 11,271 constraints and 5,742 variables.

Table 2. CPU times for robust optimization and stochastic programming solutions (seconds).
Full size table

5 Conclusion

In this study, we proposed a robust optimization model that minimizes the delay from the regular closing time of the operating room. The proposed model considers multiple operating rooms and surgical procedures. We also verified whether the risk-averse tendency is reflected in the schedule. The numerical analysis suggests that robust optimization models tend to avoid long delays. From the numerical analysis, robust optimization exhibits the same performance as stochastic programming, which has complete information on the scenario in specific control conservative. Robust optimization obtains a solution faster than stochastic programming because the number of variables and constraints in robust optimization is smaller than in stochastic programming. The robust optimization model is more effective for operating room managers who desire to obtain an accurate solution quickly.

In future work, we will clarify the effect of optimizing the surgical sequence on delay reduction. For this purpose, we define delay from the planned surgery end time and modify a part of the proposed model.