1 Introduction

The utilization of operating rooms (ORs) plays a critical role in the operations of hospitals. To wit, optimizing the utilization of ORs is essential to lower the cost of operations, to ease the patient congestion and shorten the waiting time of surgical patients, and to increase the admission rate of patients (Roshanaei et al., 2017). In practice, the service capacity of ORs cannot often meet the needs of patients demand due to the low utilization of ORs. In particular, some hospitals still face the situation that ORs have not been fully utilized which is radically caused by unreasonable or inefficient scheduling (Bandi & Gupta, 2020). Based on the prevailing practice and the related data analyses in some hospitals in China and the United States, this paper will unveil that one main reason for a low ORs utilization is inefficient scheduling and non-operating occupation (e.g., anesthesia works) in ORs.

Typically, surgery process mainly includes three stages: preoperative, perioperative, and postoperative stages (Batun et al., 2011). Anesthesia, an essential process of surgery, is usually carried out in ORs by anesthesiologists, nurses, or anesthesia-related equipment, during which it makes the scarce resources such as surgeons and surgical equipment being idle (Hopp & Lovejoy, 2013). To address the issue, some hospitals have tried to improve the traditional surgery management process by process reengineering, i.e., setting up an independent anesthesia room to carry out centralized anesthesia for patients (e.g., NORA strategy) (Nagrebetsky et al., 2017). In this setting, the resources involved in the anesthesia process, such as anesthesiologists and nurses, are separated from ORs so that the anesthesia work will no longer occupy costly OR resources. Currently, most studies focus on surgery scheduling under the traditional surgery process (Hamid et al., 2019; Shehadeh & Padman, 2022; Shylo et al., 2013). Hence, existing theoretical research cannot be applied readily to the NORA setting. Furthermore, research on scheduling under non-operating room anesthesia (NORA) strategies is of scarcity. The joint scheduling problem between ORs and anesthesia rooms is more challenging compared with the problem under the traditional operating process.

Emergency arrivals add more wrinkles to surgical scheduling. One big obstacle is how to deal with the disruptions to the already-planned elective patient surgery schedule caused by emergency patient arrivals. This is critical as elective surgery is the main source of revenue to most hospitals. There are two main strategies to address emergency patients. One is to reserve a dedicated OR for emergency patients, and the other is to share ORs between emergency patients and elective patients, i.e., arrived emergency patients will be added and allocated to the upfront of the elective surgery queue. For the former strategy, some literature has mentioned that it is inefficient in the context of low emergency surgery arrival rates, resulting in an undesirable waste of OR resources (Batun et al., 2011; Hallah & Visintin, 2019; Jung et al., 2019). For the latter strategy, some studies set some constraints to make sure that emergency patients can get access to ORs timely within a limited waiting time (Freeman et al., 2016; Miao & Wang, 2021; van Essen et al., 2012). Different from the traditional surgery process, the scheduling of emergency patients under NORA setting needs to consider the occupation of anesthesia rooms and ORs simultaneously. In addition, random emergency arrivals often affect the implementation of the initial scheduling scheme of elective surgery, resulting in surgery delay or cancellation. These may reduce the efficiency of ORs and further cause considerable costs (Samudra et al., 2016). However, the existing OR scheduling studies considering the arrival of emergency patients mainly focus on how to effectively deal with emergency patients, but lack attention on their impact on the existing surgical scheduling scheme (Zhu et al., 2019). Undoubtedly, adding arrived emergency patients to the existing scheduling scheme will introduce additional costs, caused by the reallocation of resources and transfer of equipment. In this case, it is necessary to take a close consideration on the impact of emergency patient arrival on the implementation of elective surgery. Readers are referred to the literature of Dai et al. (2022), Li et al. (2021, 2022), Wang et al. (2021a, 2021b).

In this paper, a surgical scheduling model is formulated for the surgical scheduling problem under the NORA setting. Meanwhile, for the devised model, we propose a heuristic algorithm to solve the problem with efficiency. Besides, a rescheduling model is further proposed to alleviate the impact of uncertain emergency patients on elective patients. The specific process is mainly divided into two stages: initial scheduling and rescheduling. In the initial scheduling stage, the initial scheme under the NORA strategy is first curated through the model. Experiments show that the NORA strategy can significantly improve the utilization of the ORs compared with the traditional anesthesia process. In the rescheduling stage, the experimental results show that the rescheduling model can effectively address the disruptions of the random arrival of emergency patients to the initial scheduling scheme.

2 Literature review

Our study is mainly related to two streams of literature. The first stream is about how to improve the utilization rate of ORs, and the second one is about how to deal with the arrival of emergency patients.

OR scheduling (also known as surgery scheduling) typically involves multiple stages, multiple resources, and multiple participants, and a variety of uncertainties. Some research classifications can be seen in the literature review (Zhu et al., 2019). Among those relevant reference, most studies mainly focus on how to improve the utilization rate of the OR through scheduling models and algorithms (Atighehchian et al., 2020; Rachuba & Werners, 2017; Vancroonenburg et al., 2016). In an effort to improve the efficiency of ORs, some hospitals have isolated and built independent anesthesia rooms to prevent the occupation of non-operating anesthesia in ORs (Nagrebetsky et al., 2017). However, such NORA practice has brought up with new challenges to the traditional scheduling method. Specifically, the separation of the anesthesia unit and the surgical unit requires coordination and compactness between these two units as the surgery must be performed immediately after anesthesia. However, the relevant literature on scheduling pertaining to the NORA mechanism is rather scarce. This study aims to bridge the gap.

In view of the comparison as detailed in Table 1, Tsai et al. (2017) attempted to utilization of anesthesia resources without considering the operating room. Wang et al. (2021a, 2021b) and Liang (2022) only focused on elective surgery without considering the impact on emergency patients. However, the influence of emergency patients' arrival on the utilization of ORs cannot be ignored (Freeman et al., 2016), as it may preempt medical resources and further interfere with elective surgery. Our contribution by this study is to propose a model and algorithm to address the uncertainty of the arrival of emergency patients.

Table 1 Comparison of research studies on NORA strategies
Full size table

Emergency patients are different from elective patients. Their surgery type, surgery duration, arrival time, and other information cannot be perceived in advance. Accordingly, the scheduling of emergency patients often involves the uncertainty of arrival time, surgery time, and resource demand. How to effectively manage the arrivals of emergency patients is one of the difficulties in OR scheduling (Breuer et al., 2020). To solve this problem, researchers have proposed some strategies such as (1) reserving a separate OR (Wang et al., 2022), (2) leaving a time gap between adjacent surgery processes, or (3) postponing elective surgery (Moosavi & Ebrahimnejad, 2020; Xie et al., 2021; Zhu et al., 2019). The first one belongs to the OR management strategy, while the rest two are of surgery scheduling strategies. In general, there are three common OR management policies for emergency patients: dedicated policy, flexible (or shared) policy, and hybrid policy (Bovim et al., 2020; Breuer et al., 2020). This paper mainly studies the surgery scheduling problem under the shared OR strategy, namely, all ORs can be allocated to emergency patients and elective patients. For this setting, Essen et al. (2012) proposed the concept of break-in-moments (BIMS) to minimize the waiting time of emergency patients by evenly distributing the elective surgery completion time as much as possible. In this paper, we also control the overlapping time between surgery in multiple ORs so as to cope with the random arrivals of emergency patients. In addition, Kroer et al. (2018) considered the arrival of emergency patients and established a model to minimize overtime cost and the number of open ORs. Most of the existing literature focuses on how to effectively deal with emergency patients but barely considers the negative impact pertaining to the insertion of emergency patients (Miao & Wang, 2021). However, in practice, these negative effects may impose the initial elective surgery strategy no longer applicable. To address the issue, this paper aims to consider the impact of emergency patients on the initial scheduling scheme via rescheduling. Rachuba and Werners (2014) considered the objectives from multiple perspectives, including patients, doctors and management objectives. However, they mainly considered the uncertain needs of emergency patients and proposed a preventive scheduling scheme with robustness. In contrast, not only does this paper consider the preventive scheduling scheme for emergency patients, but also the rescheduling scheme after emergency patients are inserted. Concerning that the devised rescheduling model per se requires potential computational time for a solution, we propose a heuristic algorithm accordingly, and show that the algorithm can greatly reduce the solution time of the model (Lu et al., 2020; Wu et al., 2022).

3 Model formulation

This paper studies the OR scheduling problem under the shared OR strategy with independent anesthesia rooms. Typically, elective patients have low uncertainty. In this case, the elective surgery duration can be predicted according to the statistical analysis of hospital historical data or machine learning models (Al-Refaie et al., 2018; Devi et al., 2012; Schneider et al., 2020). Hence, without loss of generality, we simply assume that the elective surgery duration of patients can be determined in advance. Referring to Samudra et al. (2016), emergency patients with a tolerant waiting time are regarded as semi-emergency patients and can be treated within that time interval after arrival. Considering the urgency and health risk of emergency patients, we assume that the anesthesia work of all emergency patients can only be carried out in ORs. In contrast, elective patients are treated via following the NORA process. Under the NORA strategy, elective patients need to be anesthetized separately right prior to the surgery in an independent anesthesia room. The independent anesthesia room generally includes multiple anesthesia beds, anesthesiologists, anesthesia nurses, and anesthesia equipment (Nagrebetsky et al., 2017), which can carry out anesthesia for multiple patients at the same time.

Referring to the extant literature and the prevailing practice in hospitals, we make the following assumptions.

  1. (1)

    The surgery that has started cannot be interrupted or canceled, and all surgeries must be completed on surgery day (Hopp & Lovejoy, 2013);

  2. (2)

    In order to ensure the safety of patients and improve the utilization of the ORs, patients after anesthesia need to be transferred to an OR for surgery immediately (Macario, 2010);

  3. (3)

    The whole surgery process of emergency patients is carried out in an OR (Hopp & Lovejoy, 2013);

  4. (4)

    The opening time of the anesthesia room is earlier than that of ORs to ensure that patients can be conducted anesthesia before ORs open (Hopp & Lovejoy, 2013);

  5. (5)

    Each emergency patient has a certain waiting time threshold (Samudra et al., 2016).

In this paper, the surgery scheduling is divided into the initial scheduling stage \(P_{0}\) and the rescheduling stage \(P_{1}\), upon the arrival of emergency patients. In the \(P_{0}\) stage, the starting time and schedule of elective surgeries in the anesthesia rooms and ORs are determined with the objective of maximizing the efficiency of ORs. To ensure that the actual waiting time of emergency patients does not exceed their threshold, our model includes BIM constraints. Since any insertion of emergency patients disrupts the initial scheduling scheme made in \(P_{0}\) stage, it is necessary to adjust the initial scheduling scheme in \(P_{1}\) stage with the objective of maximizing OR utilization and minimizing surgical changes.

Before establishing the model, the main variables are summarized in Table 2 based on the above assumptions.

Table 2 Notions of parameters and variables
Full size table

3.1 Initial scheduling model under NORA

At stage \(P_{0}\), the main objective is to maximize the efficiency of ORs while the random arrival of potential emergency patients is considered by some preventive BIM constraints. We characterize the OR utilization rate through three types of cost (including overtime, idle and operating costs); cf. Jung et al. (2019). Decision variables include the OR assignment, the surgery starting time, the anesthesia room assignment, and the start time of the anesthesia for elective patients. Under the NORA setting, a mixed-integer programming model is formulated to generate an initial schedule to improve the efficiency of ORs to treat the potential arrival of emergency patients as follows:

$${\text{Min}}\;Z = \sum\limits_{i = 1}^{N} {\sum\limits_{j = 1}^{M} {\sum\limits_{t = 1}^{T} {\mathop c\nolimits_{r} \mathop x\nolimits_{ijt} } } } + \sum\limits_{j = 1}^{M} {\sum\limits_{t = 1}^{T} {\mathop c\nolimits_{l} \left( {1 - \sum\limits_{i = 1}^{N} {\mathop x\nolimits_{ijt} } } \right)} } + \sum\limits_{i = 1}^{N} {\sum\limits_{j = 1}^{M} {\sum\limits_{t = T}^{T + L} {\mathop c\nolimits_{o} \mathop x\nolimits_{ijt} } } } ,$$
(1)
$$\sum\limits_{t = 1}^{T + L} {\sum\limits_{j = 1}^{M} {y_{ijt} } } = 1,\quad i = 1,2, \ldots ,N,$$
(2)
$$\sum\limits_{i = 1}^{N} {x_{ijt} } \le 1,\quad j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L,$$
(3)
$$\sum\limits_{r = t}^{{\min \left( {t + p_{i} - 1,T + L} \right)}} {x_{ijr} } \ge p_{i} y_{ijt} ,\quad i = 1,2, \ldots ,N,\;j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L,$$
(4)
$$\sum\limits_{i = 1}^{N} {\sum\limits_{j = 1}^{M} {\mathop x\nolimits_{ijt} } } = O_{t} ,\quad t = 1,2, \ldots ,T + L,$$
(5)
$$\sum\limits_{t = k}^{k + u} {O_{t} } - \sum\limits_{i = 1}^{N} {\sum\limits_{t = k + 1}^{k + u} {\sum\limits_{j = 1}^{M} {\mathop y\nolimits_{ijt} } } } \le \left( {u + 1} \right)M - 1,\quad k = 1,2, \ldots ,T,$$
(6)
$$\sum\limits_{t = 1}^{T + L} {O_{t} } = \sum\limits_{i = 1}^{N} {\mathop p\nolimits_{i} } ,$$
(7)
$$\sum\limits_{f = 1}^{F} {\sum\limits_{t = 1}^{T + L} {\mathop a\nolimits_{ift} } \le \, 1} ,\quad i = 1,2, \ldots ,N,$$
(8)
$$\sum\limits_{i = 1}^{N} {\mathop a\nolimits_{ift} } \le Beds,\quad f = 1,2, \ldots ,F,\;t = 1,2, \ldots ,T + L,$$
(9)
$$\sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{j = 1}^{M} {\mathop {H_{t} \cdot y}\nolimits_{ijt} } } - s_{i} \sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{j = 1}^{M} {\mathop y\nolimits_{ijt} } } = \left( {H_{t} - s_{i} } \right)\sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{f = 1}^{F} {\mathop a\nolimits_{ift} } } ,\quad i = 1,2, \ldots ,N,$$
(10)
$$\begin{aligned} & x_{ijt} ,y_{ijt} ,a_{ift} \in \left\{ {0,1} \right\}, \\ & \quad i = 1,2, \ldots ,N,\;j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L, \\ & \quad f = 1,2, \ldots ,{\text{F,}} \\ \end{aligned}$$
(11)
$$O_{t} \in \left\{ {0,1, \ldots ,M} \right\},\quad t = 1,2, \ldots ,T + L.$$
(12)

In the above model, the objective given in Eq. (1) is to minimize the total cost of overtime, idleness and the operating cost of ORs. The fixed cost of ORs and other costs that are not related to OR efficiency are not considered, as the hospital’s main purpose is to increase the utilization rate of ORs. Constraint (2) indicates that each surgery can only be started once. Constraint (3) ensures that at most one surgery can be performed at any moment in each OR. Constraint (4) indicates that the ongoing surgery cannot be interrupted. Constraint (5) represents the number of all ORs occupied at a certain time. Constraint (6) indicates that the overlap duration of all surgery in ORs cannot exceed a certain threshold. Referring to the concept BIMs (van Essen et al., 2012), emergency patients can get timely access to ORs by controlling the start and end time of elective surgeries. Therefore, there may be short idleness between adjacent operations in the initial scheduling plan. This can ensure that emergency patients arriving at any time can be timely inserted into an OR within the threshold time. Constraint (7) indicates the relationship between the occupancy of ORs and the surgery duration. Constraint (8) indicates that the patient is anesthetized only once. Constraint (9) indicates that the number of patients getting anesthesia simultaneously cannot exceed the maximum number of beds. Constraint (10) means that the patient must enter the OR for surgery after anesthesia without waiting. Constraints (10) and (11) limit the range of decision variables.

3.2 Rescheduling model considering emergency patient arrivals under NORA

In the rescheduling model, three types of costs are mainly considered: overtime cost, change-related cost and balance cost. In order to clarify the concept and relationship of the objective, we give a brief example with three ORs, as depicted in Fig. 1. The upper subfigure is the initial scheduling and the lower subfigure is the rescheduling under the same condition, where \(S\) is the elective surgery, \(E\) is the emergency surgery, the arrival time and surgery duration of the emergency are 7 and 5 respectively, and the normal opening time of the OR is 16. Comparing the rescheduling plan with the initial scheduling plan, it can be seen that the total overtime of the OR is 4, the changed surgeries are \(S{2}\) and \(S3\), and the overtime of the three ORs are 0, 0, and 4 respectively. Then the balance time is \(\left[ {\left( {4 - 0} \right) + \left( {4 - 0} \right) + \left( {0 - 0} \right)} \right]\) as shown in Fig. 2. Therefore, the balance cost is \(\left[ {\left( {4 - 0} \right) + \left( {4 - 0} \right) + \left( {0 - 0} \right)} \right]*c_{p}\), and the total cost is expressed as \(Z^{\prime} = 4c_{o} + 2c_{t} + 8c_{p}\).

Fig. 1
figure 1

An example of rescheduling schedule (E1: emergency surgery)

Full size image
Fig. 2
figure 2

An example of calculating balance time

Full size image

As depicted Fig. 1, E-1 to E-6 indicate the insertion time for emergency patients because the elective surgeries that have already started cannot be stopped. The term "overlapping duration" refers to the time range in which all ORs are occupied, during which urgent patients had to wait. Emergency patients have a certain waiting time threshold \(u\) (Jung et al., 2019). Therefore, it wouldn't influence emergency patients' health as long as the \(overlapping\;duration \le u\). Note that the overlapping duration is determined by the scheduling model, while \(u\) is given by hospitals. For example, if an emergency patient arrives at time 6, the earliest time he can start surgery is between E-1 and E-3. If the time is E-3 (i.e.,7), then the waiting time is 1. In this case, S2 must be postponed, resulting in OR2 overtime. Further, it may also lead to \(overlapping\;duration \ge u\), which means the next emergency patient may wait for more than \(u\). H1 mainly aims to solve the aforementioned problems.

Rescheduling is required after each emergency patient arrives. The time of the emergency patient’s arrival and duration of the emergency patient are input. The overlap between ORs needs to be considered in order to meet the subsequent insertion of emergency patients. When adjusting the initial scheduling plan, we try to minimize the adjustment between ORs as much as possible, which is consistent with the rescheduling objective. At the same time, we also consider the unstarted surgery in the OR with overtime. The limit of OR overtime may be determined according to different actual needs.

At the rescheduling stage, changing ORs may cost a lot due to the inconvenience for the implementation of the rescheduling plan, because preoperative preparations, equipment, and other resources may need to be adjusted immediately. Besides, the OR with too much overtime will also incur additional costs (Bandi & Gupta, 2020), and this situation is undesirable. In view of the above analyses, we propose the following rescheduling model:

$${\text{Min }}Z^{{\prime }} = \sum\limits_{i = 1}^{N + 1} {\sum\limits_{j = 1}^{M} {\sum\limits_{t = T}^{T + L} {c_{o} x_{ijt} } } } + c_{t} N^{{\prime }} + c_{p} S,$$
(13)
$$N^{{\prime }} = \sum\limits_{i = 1}^{N} {\left( {1 - \sum\limits_{t = 1}^{T + L} {y_{{ij^{{\prime }} t}} } } \right)} ,\quad j^{{\prime }} = \sum\limits_{j = 1}^{M} {\sum\limits_{t = 1}^{T + L} {jy_{ijt}^{{\prime }} } } ,\quad i = 1,2, \ldots ,N,$$
(14)
$$S = \sum\limits_{j = 1}^{M} {\sum\limits_{{j^{\prime} = j}}^{M} {\left[ {\left| {\sum\limits_{i = 1}^{N + 1} {\sum\limits_{t = T + 1}^{T + L} {\left( {x_{ijt} - x_{{ij^{^{\prime}} t}} } \right)} } } \right|} \right]} }$$
(15)
$$\sum\limits_{t = 1}^{T + L} {\sum\limits_{j = 1}^{M} {y_{ijt} } } = 1,\quad i = 1,2, \ldots ,N + 1,$$
(16)
$$\sum\limits_{i = 1}^{N + 1} {x_{ijt} } \le 1,\quad j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L,$$
(17)
$$\sum\limits_{r = t}^{{\min \left( {t + p_{i} - 1,T + L} \right)}} {x_{ijr} } \ge p_{i} y_{ijt} ,\quad i = 1,2, \ldots ,N + 1,\;j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L,$$
(18)
$$\sum\limits_{i = 1}^{N + 1} {\sum\limits_{j = 1}^{M} {\mathop x\nolimits_{ijt} } } = O_{t} ,\quad t = 1,2, \ldots ,T + L,$$
(19)
$$\sum\limits_{t = k}^{k + u} {O_{t} } - \sum\limits_{i = 1}^{N} {\sum\limits_{t = k + 1}^{k + u} {\sum\limits_{j = 1}^{M} {\mathop y\nolimits_{ijt} } } } \le \left( {u + 1} \right)M - 1,\quad k = D + 1, \ldots ,T + L,$$
(20)
$$\sum\limits_{t = 1}^{T + L} {O_{t} } = \sum\limits_{i = 1}^{N + 1} {\mathop p\nolimits_{i} } ,$$
(21)
$$\sum\limits_{f = 1}^{F} {\sum\limits_{t = 1}^{T + L} {\mathop a\nolimits_{ift} } \le 1} ,\quad i = 1,2, \ldots ,N + 1,$$
(22)
$$\sum\limits_{i = 1}^{N + 1} {\mathop a\nolimits_{ift} } \le Beds,\quad f = 1,2, \ldots ,F,\;t = 1,2, \ldots ,T + L,$$
(23)
$$\sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{j = 1}^{M} {\mathop {H_{t} \cdot y}\nolimits_{ijt} } } - s_{i} \sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{j = 1}^{M} {\mathop y\nolimits_{ijt} } } = \left( {H_{t} - s_{i} } \right)\sum\limits_{{t = s_{i} + 1}}^{T + L} {\sum\limits_{f = 1}^{F} {\mathop a\nolimits_{ift} } } ,\quad i = 1,2, \ldots ,N + 1,$$
(24)
$$\begin{aligned} & x_{ijt} ,y_{ijt} ,a_{ift} \in \left\{ {0,1} \right\},\quad i = 1,2, \ldots ,N + 1,\;j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,T + L, \\ & \quad f = 1,2, \ldots ,{{F,}} \\ \end{aligned}$$
(25)
$$O_{t} { = }\left\{ {0,1, \ldots ,M} \right\},\quad t = 1,2, \ldots ,T + L,$$
(26)
$$y^{{\prime }}_{ijt} :given,\quad i = 1,2, \ldots ,N + 1,\;j = 1,2, \ldots ,M,\;t = 1,2, \ldots ,t_{u} ,$$
(27)

Some of the constraints in the rescheduling model are similar to the initial scheduling model, and we will explain the meaning of new constraints. Constraint (13) indicates that the model’s objective is composed of three parts, where \(c_{o}\), \(c_{t}\), and \(c_{p}\) are respectively the overtime, change and balance cost per unit time. The overtime cost is the same as the initial scheduling model. The change-related cost is the cost of an elective surgery switching from one OR to another. In order to prevent a certain OR from being overloaded, the balanced cost is set as the penalty caused by the excessive overtime of the surgery. Constraint (14) is the number of swaps of elective patients compared with the initial scheduling plan after emergency patients arrive. Constraint (15) represents the balance time of all ORs. In constraint (20), \(D\) is the minimum value of the emergency patient's surgery start time \(t_{r}\) and the earliest completion time of the currently undergoing elective surgery. This constraint ensures that future emergency patients can also get timely treatment after inserting one emergency patient. In constraint (27), \(t_{u}\) is the actual arrival time of the emergency patient. This constraint means that we take the solution of the initial scheduling model as the input of our rescheduling model.

The surgical scheduling problem with random arrivals of emergency patients is NP-hard when the size of the ORs exceeds 2 (Lamiri et al., 2008). For the initial scheduling model, when the size of the OR exceeds 20, the traditional solution method cannot obtain optimal solutions in a reasonable time, and the rescheduling model is more difficult to solve. In order to solve the problem effectively in a short time, it is reasonable to develop approximate algorithms. In what follows, we designed a heuristic algorithm to solve the large-scale problem and verified the performance of the algorithm in numerical experiments.

4 Solution methodologies

Two heuristic algorithms are proposed for the initial scheduling problem \(P_{0}\) and the rescheduling problem \(P_{1}\). The purpose of developing this heuristic is to provide a simple, effective and easy-to-implement method that does not rely on complex software. The algorithm is based on the rule of \(LPT - SPT\) proposed by Jung et al. (2019). In the two heuristic algorithms, the subset of surgeries is fixed, and the number of ORs \(M \ge 2\).

First of all, the heuristic algorithm \(H_{0}\) is leveraged to solve the initial scheduling problem. The algorithm is delineated as follows.

In the heuristic algorithm \(H_{0}\), we take the duration of elective surgery, the number of ORs and the number of anesthesia rooms as input, and the output is an initial scheduling plan. We schedule all surgeries with shorter duration in the same OR. These surgeries can be started and ended quickly. In other ORs surgeries with longer duration are scheduled to deal with the random arrival of emergency patients.

The cost of the OR overtime cost and idle cost is the minimal (i.e., the schedule is optimal) if either of following two conditions is satisfied. (1) If in schedule \(S\), \(\tau_{j} \le T,\;j = 1,2, \ldots ,M\). (2) If in schedule \(S\), \(\tau_{j} \ge T,\;j = 1,2, \ldots ,M\) and only surgeries with surgery duration less than two hours are assigned to \(OR_{1}\).

figure a

Remark

For (1), the fact that no ORs have overtime means that all surgeries have been scheduled. At this point, Schedule \(S^{*}\) is optimal as the sum of OR idle cost and surgery operating cost is the minimum. For (2), only the surgeries with surgery duration less than two hours are assigned to \(OR_{1}\); it means that \(OR_{1}\) has enough insert points to deal with the emergency patients. \(OR_{j} ,\;j = 2,3, \ldots ,M\) can be scheduled closely, with no idle cost and the lowest overtime cost. For other conditions, to ensure BIM constraint, in Step 4, we adjust the starting time of surgery from \(t_{i}\) to \(t_{i} + u\), which helps ease the delay of the starting time obtained in Step 3.

Next, the heuristic algorithm \({H}_{1}\) for rescheduling is introduced. The steps are shown as follows.

figure b

5 Computational studies and experiments

5.1 Experiment setup

In order to verify and analyze the effectiveness of the OR scheduling model under the independent anesthesia room and the algorithm, we designed three sets of experiments. Experiment 1, Experiment 2, and Experiment 3 respectively verify the effectiveness of the NORA strategy, the effectiveness of the proposed algorithm, and the performance of rescheduling.

We set experimental parameters by referring to literature, discussing with some practitioners, and analyzing some data as reported in Table 3. The parameter setting is as follows: the normal working time of the OR is generally no more than 8 hours (h) per day, and the maximum overtime is no more than 4 h. In the numerical experiment, we set half an hour as one time unit. The normal opening time of all ORs is set to \(T = 16\), which is 8 h. The maximum OR overtime is \(L = 8\) or 4 h. The surgery duration is between 1.5–4 h. The surgery duration follows the uniform distribution from the interval \(p_{i} \in \left[ {3,8} \right]\) and must be an integer. In order to simplify the experiment, the duration of anesthesia for the surgery is 0.5 h, that is, \(s_{i} = 1\). The number of patients that the anesthesia room can serve at the same time is 4. The maximum time that emergency patients can tolerate is 4. Referring to Zhang et al. (2014), the unit open cost \(c_{r}\), overtime cost \(c_{l}\) and idle cost \(c_{o}\) of the initial scheduling model are set to 1/unit time, 1.5/unit time and 2/unit time. At the same time, the change-related cost, overtime cost and balance cost of the rescheduling model are set to 4/unit time, 2/unit time and 0.5/unit time.

Table 3 Parameters setting
Full size table

We conduct experiments under different OR scales, and each group of experiments generates surgery duration \(p_{i}\) based on the total surgery duration \(\overline{P}\) of \(N\) surgery, \(\overline{P} = \mathop \sum \nolimits_{i = 1}^{N} p_{i}\). The \(\overline{P}\) can be used to describe a utilization situation of ORs. All codes and numerical experiments are conducted in Matlab R2014a with Gurobi 8.1.0.

5.2 Performance comparison: operating room anesthesia (ORA) versus NORA

Experiment 1 was conducted for the initial scheduling stage \(P_{0}\). Under the premise of considering emergency patients, we compared the non-OR anesthesia strategy with the traditional OR anesthesia strategy and verified the advantages of the NORA strategy under different OR scales. All solutions in Experiment 1 are obtained by Gurobi. The detailed experimental results are reported in Table 4 as below.

Table 4 Experimental comparison of ORA and NORA strategy (OB: objective value; OT: OR overtime; IT: OR idle time.)
Full size table

In view of Table 4, the objective value of the NORA strategy is better than the traditional operating room anesthesia (ORA) strategy in which a long overtime is incurred. The NORA strategy improves the turnover rate of ORs which saves a lot of resources. With the increase in the number of ORs and surgeries, NORA strategies can save more OR resources and allocate more surgery. In addition, according to related literature (Marjamaa et al., 2009), the open cost of an anesthesia room unit is far less than that of an OR resource. In addition, the NORA strategy can help reasonably allocate related resources such as anesthesiologists and anesthesia nurses, enabling a medical team to serve multiple anesthetized patients, which effectively improves resource efficiency and reduces OR opening costs.

5.3 Performance analysis of proposed heuristic algorithm

For the initial scheduling stage, we verified the effectiveness of the proposed heuristic algorithm \(H_{0}\). In this part, the scale of the OR is set to be small, medium and large, and there are 3 experimental examples under each scale. In order to show the effectiveness of the algorithm, we compared the \(H_{0}\) with the solver and genetic algorithm (GA), which has been successfully applied to the surgical scheduling model; cf. Guo et al. (2016).

The experimental results are summarized in Table 5. In a small-scale case, the solver can obtain the optimal solution in a short time. At a medium scale, the solver can also get the optimal solution in about 2 min. But when the problem scale increases, the optimal solution cannot be obtained within 8 h. In comparison, the GA algorithm is faster, but as the problem scale increases, it still takes about 5 min in order to solve the problem. This means that all patients who have not yet started surgery need to wait for several minutes to be rescheduled, which will result in a waste of time in ORs. In contrast, we found that the proposed heuristic algorithm has a very short computational time, less than 0.01 s on average, which is better than the GA algorithm. This shows that \(H_{0}\) is effective to solve the proposed model.

Table 5 Experimental comparison between the proposed algorithm and genetic algorithm
Full size table

To further verify the effectiveness of the algorithm, we use a common evaluation indicator defined as follows:

$$GAP = \frac{{(Z - Z_{best} )}}{{Z_{best} }} \times 100$$

where \(Z\) represents the objective value obtained by the current algorithm, and \(Z_{best}\) represents the optimal value of the problem.

Considering that the optimal objective value may not be obtained in large-scale cases, referring to Jung et al. (2019), we replace \(Z_{best}\) with the optimal lower bound \(LB\) of the solution. \(LB\) is the optimal objective value that can be reached under a certain scale in the ideal state where some constraints are ignored.

$$LB = c_{r} \cdot \min \left( {\overline{P} ,M \cdot T} \right) + c_{o} \cdot \max \left( {\overline{P} - M \cdot T,0} \right) + c_{l} \max \left( {M \cdot T - \overline{P} ,0} \right);$$
$$\overline{P} = \sum\limits_{i = 1}^{N} {p_{i} } ,$$

where \(M\) and \(T\) indicate the number of open ORs and the normal open time of ORs, respectively.

The experimental results are reported in Fig. 3. Compared with \(H_{0}\), GA algorithm has a compelling advantage in solving accuracy at a small scale. However, that advantage diminishes as the scale gets bigger. On the other hand, compared with GA algorithm, \(H_{0}\) shows more obvious advantage in terms of the solving speed. Especially for large-scale problems, the algorithm still leads to a short solution time. It implies that scheduling decisions can be obtained faster in response to emergent emergency patients, which is more applicable in practice. Undoubtedly, the combination of \(H_{0}\) and GA will produce a better solution accuracy without increasing the algorithm time.

Fig. 3
figure 3

Comparison between the proposed heuristic algorithm and intelligent algorithm (H0: objective function values/running time of proposed heuristic algorithm; GA: objective function values /running time of GA algorithm; GA-H: objective function values/running time of Hybrid algorithm based on GA algorithm and H0)

Full size image

5.4 Performance analysis for emergency patient arrival

In the experiment for the rescheduling stage, considering the different needs of emergency patients, we generate emergency patient arrival time and surgery duration when the number of emergency patients is 1, 2, and 3 respectively. We set a traditional complete rescheduling (CR) strategy for comparison, which is a commonly-used rescheduling scheme whose objective is to minimize the overtime cost. The proposed rescheduling is incomplete rescheduling (ICR) whose objective is to minimize changes in ORs. In the experiment, we analyze the results of the MIP model and the heuristic algorithm \(H_{1}\).

The specific experimental results are reported in Tables 6, 7 and 8 under different settings, where \(t_{u}\) is the arrival time of emergency patients, and \(p_{e}\) is the surgery duration of emergency patients. For example, \(t_{u} = \left[ {2,5} \right]\), \(p_{e} = \left[ {7,4} \right]\) indicate that the arrival time of the first emergency patient and the second emergency patient are 2 and 5 respectively, and the surgery duration of the two patients are 7 and 4 respectively. In the third experiment, the main performance indicators considered are the total cost of ORs, overtime cost, change-related cost, and the actual start time of emergency patient surgery.

Table 6 Performance of the reschedule models and algorithm with \({t}_{u}=7, {p}_{e}=5\)
Full size table
Table 7 Performance of the reschedule models and algorithm with \({t}_{u}=[\mathrm{2,5}],{p}_{e}=[\mathrm{7,4}]\)
Full size table
Table 8 Performance of the reschedule models and algorithm with \({t}_{u}=[\mathrm{4,8},9],{p}_{e}=[\mathrm{6,6},4]\)
Full size table

It can be observed from Table 6 that under the same cases, the objective value obtained by solver is better than the result of the heuristic algorithm \(H_{1}\), but when the size of the ORs and the number of patients become larger, the solver can no longer effectively cope with the decision making in a reasonable time. In addition, under the NORA strategy, the total cost of the solver and the heuristic algorithm is better than that under the CR strategy.

5.5 Sensitivity analysis

Given that the unit operating cost, OR overtime cost and idle cost of the initial scheduling model, and the emergency patient arrival time, the changed-related cost, overtime cost and balance cost of the rescheduling phase may affect the effectiveness of the model and algorithm, we conduct a sensitivity analysis.

As shown in Tables 9, 10 and 11, we first tested the impact of different unit costs on the effectiveness of the model and heuristic algorithm. It can be found that within a certain parameter value range, the change of unit cost only affects the value of the objective function, and has no effect on the utilization rate of ORs. This also shows that the initial scheduling model has good robustness. At the same time, experiments on heuristic algorithms also show that the algorithm has better robustness. Table 11 shows the experimental results of the impact of different unit cost parameters on the rescheduling model. It can be found that within a certain range, different unit costs have little impact on the rescheduling model. But if some parameter values are set to be large enough, it will certainly have an impact on the model. For example, when the unit balance cost is much greater than the unit overtime cost, the model will try to ensure the balance of the ORs, resulting in a longer OR overtime. Nevertheless, these situations are rare because they do not meet the requirements of the hospitals. Therefore, in most cases, the rescheduling model is also relatively robust.

Table 9 Performance of the initial scheduling model at different unit cost levels
Full size table
Table 10 Performance of the algorithm at different unit cost levels
Full size table
Table 11 Performance of rescheduling model at different unit cost levels
Full size table

As depicted in Fig. 4, PS indicates that the arrival of emergency patients follows a Poisson process, and NH follows a non-homogeneous process. It can be observed that at different scales, the total cost shows no significant difference in the arrival time between PS and NH, which indicates that the model can cope with the emergency patient arrivals that follow different processes as aforementioned.

Fig. 4
figure 4

Comparison between the Poisson (PS) process and the non-homogeneous (NH) process

Full size image

6 Concluding remarks

Given the low utilization rate of operating room resources, we examine the advantages of NORA strategy and explore how to improve operating room efficiency with the implementation of NORA strategy. Then, we further consider the impact of emergency patients on elective surgeries. The research is divided into two stages. First, an initial elective surgery scheduling model under the NORA strategy is established, while a prescheduling plan for emergency patients is generated based on the BIM constraints. Then, the rescheduling model is proposed to adjust the initial scheduling plan after emergency patient arrives. In this stage, the objective is to minimize the surgical changes of the elective patients and maximize the efficiency of the operating rooms. Considering the complexity of the model, we designed two heuristic algorithms to solve the initial scheduling and rescheduling models respectively. Numerical results show that the NORA strategy can save operating room resources so that more patients can be scheduled, which becomes more obvious as the size of the operating room increases. In addition, compared to the traditional procedure for surgical scheduling, the NORA strategy greatly reduces surgery-related costs. In terms of algorithms, although the optimal solution can be obtained by applying commercial solvers, the solution time is not desirable in large-scale instances. In contrast, the proposed heuristic algorithm requires less solution time on the premise of obtaining a satisfactory solution, so that the hospital administrator can respond more quickly. The comparative analysis demonstrates that the rescheduling model, taking into account the efficiency of the operating rooms and different costs, can provide a more realistic scheduling plan.

This article verifies the advantages of the NORA strategy and enriches the research of operating room scheduling under the NORA strategy. In addition, in response to the problem of random arrival of emergency patients, a more effective rescheduling plan is proposed, which provides a decision reference for hospital managers to improve the scheduling efficiency of the ORs. In practice, hospitals must make a prompt respond to their random arrival of emergency patients for surgery. To this end, hospitals usually reserve several ORs for the sake of emergency patients. However, these ORs are often idle when emergency patients do not arrive, which is an obvious waste of OR resources. To reduce the waste, we propose a model that can both cope with the uncertainty of emergency patient arrivals and improve operating room utilization.

We shall acknowledge that further studies can be done by considering more uncertainty and the availability of downstream resources: First of all, the surgery duration of elective patients may not be able to be accurately estimated. In addition, other downstream resources may also affect the surgical process. These resources may also become a bottleneck that blocks the efficient operations of operating rooms. Readers are referred to the following references for additional details, Chang et al. (2019, 2021, 2022), Tian et al. (2022), Shi et al. (2014), Gao et al. (2020), Katehakis et al. (2015, 2016), among many others.