1 Introduction

Surgery is a critical issue facing hospitals and healthcare services that have been focused recently [19, 166]. Hospital costs account for a significant amount of the total cost of healthcare expenditures. In this issue, operating rooms (ORs) are one of the most significant services that require high-cost resources, including staff, equipment, and medicine [9, 81, 92]. Consequently, scheduling plays a critical role in OR management; consequently, scholars in the field are studying this problem (Fig. 1). In this paper, strategical, tactical, and operational OR scheduling problems associated with elective and non-elective patients are reviewed and meta-heuristic approaches used to solve large-scale problems are introduced.

Fig. 1
figure 1

Trends in OR scheduling publications along with a forecast indicator

Full size image

Figure 2 presents an analysis that was performed on data extracted from Scopus. Figure 2a shows documents cited by other articles; for example, 1127 is the sum of cited articles that were published in 2010, followed by 923 in 2009, 881 in 2015, and so forth. Figure 2b shows the number of authors who made contributions to the field; for example, the year 2018 possesses the most contributors (71 authors), follow by 2015 (62), and so forth. Figure 2c depicts publishers who contributed to the field, such as Academic Press Inc, BioMed Central Ltd, and American Scientific Publishing. Figure 3 presents a summary of the essential keywords extracted from published documents by year. As an example, Bayesian estimation, uncertainty, and 3 stages stochastic programming have been recently focused upon by researchers. Full details of author keywords can be found in the supplementary file.

Fig. 2
figure 2

A details analysis (count of authors, cited, and publisher) by year

Full size image
Fig. 3
figure 3

Authors’ keywords based on year

Full size image

2 Search Method Procedure

The procedure used to identify the articles reviewed in this paper as a single objective solution approach is introduced in this section.

2.1 Search Method

We used Google Scholar to find related articles. For this aim, we used combinations of the following keywords: “optimization, operating room, scheduling, planning, theatre, surgery, mathematical modeling” and combinations of solution approach keywords such as “linear programming, branch and bound, branch and cut, Monte-Carlo, simulation, heuristic, ant colony, genetic algorithm”. Classification of currently published documents based on the type of article is shown in Fig. 4. We filtered the search for updated papers since 2000 until now, and papers that were indexed by Scopus, with Boolean operators AND, OR, in both topics and titles. We define only technical research articles that contain only algorithmic descriptions, excluding book chapters, review papers, conference papers, case studies, and papers that provide managerial insights (Fig. 5).

Fig. 4
figure 4

Classification of scientific works according to type

Full size image
Fig. 5
figure 5

Research methodology used in this study

Full size image

2.2 Other Reviews

Cardoen et al. [34] evaluated the literature related to OR scheduling and planning based on problem settings such as performance measurement and patient characteristics and technical features such as solution techniques. The review by Cardoen et al. classified patients as elective and non-elective. Performance measurement discussed criteria such as waiting time, utilization, and makespan. Applicability of the research was also addressed in this review. However, a detailed analysis of the implementation of the research efforts or the role of computer–human interactions is urgently needed, which was neglected in the review by Cardoen et al.

Van Riet and Demeulemeester [161] reviewed the trade-offs in OR planning for elective and non-elective patients. The described trade-offs were defined by hospital costs and patient waiting times. The review by Van Riet and Demeulemeester focused on policies that handled trade-offs, such as flexible, dedicated, and hybrid policies. However, there is an urgent need for more comprehensive performance measures. It would be useful to search for a relationship between policies and the patient mix.

Samudra et al. [140] classified OR planning based on patient type, different performance measures, decisions, and the operations research methodology. The authors also evaluated the trends of recent years and examined connections between problem settings and the used methods. However, the review by Samudra et al. had some limitations. For example, the target group was not covered by the authors. Identifying articles based on the planning horizon or the size of a hospital setting is another drawback of this work.

Erhard et al. [53] reviewed papers related to physician and resident scheduling problems. These problems were classified based on modeling methodologies, objectives, solution approaches, and applications. Certain topics were neglected in this work; these topics could be addressed as a break assignment in the scheduling process or as integration of stochastic demand patterns. Gür and Eren [71] analyzed the literature between 2000 and 2018 pertaining to OR scheduling and evaluated the research regarding patient characteristics, performance measures, solution approaches, and uncertainty and applicability of the research.

Zhu et al. [182] performed a comprehensive review of OR planning and surgical case scheduling problems. The authors reviewed published papers based on various perspectives, such as decision levels, scheduling strategy, patient characteristics, uncertainty, models, and solutions. However, these authors did not perform an in-depth analysis of solutions from a single and multi-objective perspective and metaheuristic solution analysis is an urgent need.

3 Main Research Areas: Keyword Co-occurrence Analysis

Investigating keywords provides a chance to have a primary look into research areas ([144]. As stated by Su and Lee [150]: “keywords represent the core research of a paper”. A keywords network provides a decent image of an information area, which provides insight into the secured topics and how these subjects are mentally related and sorted out [158]. Therefore, VOSviewer 1.6.11 software was used to produce a keyword co-occurrence network. To achieve this aim, bibliographic data from Scopus was derived. Author keywords, as opposed to all keywords, were utilized in order to generate a reproducible and meaningful image of the keywords. A sum of 1913 keywords was removed from the dataset, regarding the fractional counting. Parameters were set to the values shown in Table 1.

Table 1 Parameter settings for keyword network visualization
Full size table

The resultant network contains 56 nodes and 188 links, as shown in Fig. 6, which also shows the main areas of the current surgery OR planning. Calculation of the quality of the connection between two keywords is dependent on the number of articles in which the keywords seem to be together, reproducing the relationship of their separate research areas [157]; stronger links, indicated by thicker lines, shows the link in the network visualization. It can be seen in Fig. 6 that surgical planning has a connection link to optimization. In terms of solution methods, genetic algorithms have been bold. Multi-objective optimization and uncertainty are also two important keywords in the presented network.

Fig. 6
figure 6

Keyword co-occurrence network of keywords (main research areas)

Full size image

4 Decision Levels in ORs and Surgery Scheduling

There are different decision levels in OR scheduling and planning. These decision levels can be categorized as strategic, tactical, and operational. The strategic level covers long-term decisions such as capacity planning and allocation which typically takes a long time. A problem within the strategic level is called “Case Mix Problem (CMP)” in which the amount of time a given OR is dedicated to a surgical specialty is determined in order to optimize profit/cost over a long time period [2]. Problems with cyclic OR schedules, such as master surgical scheduling, is categorized at the tactical level. In tactical level problems––namely “Master Surgery Scheduling (MSS) problem”—surgical specialties over the scheduling window (medium time horizon) are assigned to the ORs time slot in order to optimize and level resource utilization [2]. The output of tactical level (cyclic timetable) as instruction is used for decision making in operational problems [3, 11, 23]. Moreover, the last decision level, operational level, is the shortest level and involves decisions such as resource allocation, surgical cases, and advanced scheduling. Based on previously published literature of OR scheduling problems [108], other problem groups—namely “Surgical Process Scheduling (SPS) problem”—is divided into two sub-problems called “advance scheduling” and “allocation scheduling”. The first sub-problem at a tactical level (medium time horizon) solves the planning step by determining a future date for surgical cases. In the operational level—namely “Surgical Case Scheduling (SCS) problem”—as the second part of SPS solves the scheduling step that determines the start time and resource allocation of cases over a short time horizon (typically a day). Reviews on this field have been published [1, 34, 69, 108] reviewed planning and scheduling in the OR. Table 2 presents literature on a different type of decision level. A generic illustration of decision level types is provided in Figs. 7 and 8.

Table 2 Different types of decision levels in the literature
Full size table
Fig. 7
figure 7

Decision level types in ORs

Full size image
Fig. 8
figure 8

Different decision levels in OR problems

Full size image

4.1 Strategic Levels (CMP)

Decisions such as the number and specialties of surgeries to be planned and the number of resources required, could be categorized into the strategic level. The time-frame of these decisions take basically from several months to 1 year or longer [26, 167]. However some authors have classified the different levels of OR planning; for example, [163]) integrated the capacity allocation with the tactical level and [106] addressed capacity allocation with case-mix at the tactical level.

4.2 Tactical Level (MSSP)

Master Surgery Scheduling (MSS) is categorized into tactical level. MSS is known as a cyclic schedule and it is usually monthly or quarterly. MSS assigns OR time to specialties according to their specific requirements. According to Choi and Wilhelm [40], the crucial issues in MSS that need to be considered are the capacities of departmental pre- and post-surgery. Scholars apply a variety of methods to build MSS. Additional information on MSS can be found in Tan et al. [151], Adan et al. [4], Tànfani and Testi [152], Holte and Mannino [77], Lehtonen et al. [96], Barbagallo et al. [17], Durán et al. [51], Guido and Conforti [66], and Koppka et al. [87].

4.3 Operational Level (SSP)

Short-term decision making is related to operational level, which is known as the surgical case scheduling problem (SCSP). In SCSP, scheduling of resources and patients is usually designed and surgical cases are scheduled to specific day and time. In previous studies, OR scheduling was categorized to advance scheduling and integration of advanced scheduling and allocation scheduling which the former was addressed by Agnetis et al. [7], Day et al. [44], Beliën and Demeulemeester [23], Al Hasan et al. [10], and Rachuba and Werners [130]; allocation scheduling: Ozkarahan [122], Vancroonenburg et al. [163], Kroer et al. [89], Hamid et al. [72], Latorre-Núñez et al. [94], and vanVeen-Berkx et al. [162]; and the latter was defined by Díaz-López et al. [49], Huang et al. [80], Moosavi and Ebrahimnejad [118], Hashemi Doulabi et al. [74], Addis et al. [5], Molina-Pariente et al. [116], Van Huele and Vanhoucke [160], and Persson and Persson [126].

This section is focused on the scope of the SCS problem and the details of SCS is described in four parts consisting of surgical process and parameters of surgery in the OR; performance indicators in the OR; booking systems of the OR; and management system of patients. Surgical process is divided into three sub-processes, including of pre-operative/surgery, peri-operative/surgery, and post-operative/surgery in which various parameters are considered as input of each stage [43, 128, 173]. In the literature, upstream units comprise pre-operative holding units (PHUs) and wards, while post-anesthesia care units (PACUs) and intensive care units (ICUs) are placed into downstream units. Multiple ORs connect upstream and downstream units [52, 60, 172]. In the literature, patient are divided between elective (inpatient and outpatient) and non-elective (urgent and emergency) cases. An elective case is a patient that is scheduled in advance by determining multi-resources as well as the start time of the case, while an emergency case that may randomly arrive on the day of surgery is required to be performed online the same day. On the other hand, urgent cases may safely wait for 1–2 days for the surgical process. Inpatients are elective cases that remain in the hospital for more than a day for a recovery period in Wards or ICUs; however outpatients are admitted in ambulatory surgical unit (ASU) and they are discharged on the day of surgery after the operation [43, 148, 149]. As we described earlier, the surgical process is comprised of three stages: cycle time components of ORs including the duration of pre-surgery (setup and clean-up time/turnover time), duration of surgery (case-in/case-out, including required inductions, anesthesia process, and surgical process), and post-surgery duration (recovery time). In general, pre-operative and post-operative times are considered to be non-operative time, while the duration of surgery is considered operative time [43, 173]. Required resources for performing each stage of a surgical process are classified into personnel (surgeon groups, anesthetists, nurses, scrubs, medical technicians) and facility resources (PHU beds, PACU beds, ORs, specialized pieces of equipment) [128, 173]. Optimal OR schedules are evaluated by their ability to perform surgical case operations [43]. To measure OR planning and scheduling, eight main performance indicators have been used in the literature: waiting time, utilization, leveling, throughput, patient deferrals, makespan, preferences, and financial measures [34]. However, in some research studies [43, 173], overtime and idle time are considered to be important measures, while being merged in makespan. In OR planning and scheduling, there are three well known scheduling strategies/booking systems that dedicate OR-time to surgical groups: open scheduling strategy, block scheduling strategy, and modified block scheduling strategy. In block scheduling strategy, a set of time slots is allocated to every surgery specialty group, typically in the cyclic timetable (a certain number of weeks) that is constructed by solving MSS problems and surgical cases are scheduled in these time slots. In contrast, by applying an open scheduling strategy, surgical cases are scheduled on a first-come-first-service (FCFS) and are assigned to available ORs based on what is convenient to the surgeon. In another policy, in order to enhance the flexibility of the strategy, block scheduling is modified by combining strategies of both block and open scheduling. Therefore, in the modified block strategy, some time slots are booked and the rest remain open or some unused time blocks are released and allocated to other surgical cases [2, 43, 113]. In the final strategy, management has the opportunity to perform other operations in the operating theater in order to prevent penalties associated with late cancellations or no-shows [43]. Figure 9 presents the trend over time of different scheduling strategies; as can be seen, up to the year 2010, block scheduling strategy had been more studied than two other strategies, slightly; while after 2010, the number of publications on block scheduling strategy vastly outnumber other subjects. In OR planning and scheduling. VanRiet and Demeulemeester [161] discussed three policies for handling emergencies that may be encountered in the operating theater: the first policy is called flexible, where various rules and scheduling strategies are used because of the lack of separate OR reserved for emergency cases. The second policy is known as dedicated, which separate the different flows of patient classes that result from dedicating ORs to each patient type. The last policy integrates the first two types and is termed hybrid policy.

Fig. 9
figure 9

Trends of different scheduling strategies

Full size image

5 Generic Illustration

There are many resources in OR theatres that are considered in mathematical modeling. Figure 10 presents a general illustration of ORs and other resources available for surgical operations. According to the literature, there are two types of patient arrival: elective and non-elective. Elective patients are those that can be planned in advance while non-elective patients require surgery immediately. Figure 11 presents a three-stage surgery procedure consisting of the following steps: (1) pre-operative stage in which the required resources are nurses and PHU; (2) intera-operative, which is the stage that surgery will be performed; surgeons, anesthetists, nurses, and ORs are required in this stage; (3) post-operative stage, in which patients are transferred to the PACU and ICU following surgery.

Fig. 10
figure 10

General illustration of surgical ORs [156]

Full size image
Fig. 11
figure 11

A sample of surgical flows and associated resources

Full size image

Figure 12 shows the trend of published documents focused on the patients’ characteristics. As can be seen in Fig. 12, recent research has focused mainly on elective patients. Considering inpatients who are admitted by a hospital for overnight stay, different resources, such as post-anesthesia care unit (PHU), an OR, and intensive care units could be utilized. Some of the resources presented in Fig. 10 could be used as performance criteria. For example, the utilization rate of ORs has been a major subject of recent studies. Underutilization of ORs causes redundant costs; additionally, fully planned ORs are seriously unstable, resulting in uncertain costs. Measuring performance could extend to facilities other than an OR, such as Ward, PHU, PACU, and ICU. There is a vast amount of literature published on utilization of different resources; [34, 140] published comprehensive reviews.

Fig. 12
figure 12

Trend of elective and non-elective patients

Full size image

6 Mathematical Modeling

6.1 Deterministic

Gerchak et al. [62] proposed a mix-elective scheduling problem that ORs could utilize for both elective and emergency surgeries; another assumption of this model is uncertainty in the number of emergency cases. Dexter et al. [47] and Magerlein and Martin [108] developed an OR scheduling model to optimize OR implementation. Dexter et al. [48] applied a simulation approach to evaluate the performance of different algorithms in scheduling open OR times. Gupta [69] proposed an elective ORs scheduling problem. Their proposed model has been addressed with a maximum delay that penalizes the hospital’s profit. Min et al. [115] divided patients into several groups in which a stepwise function is used in relation to each patient’s cost; the objective function of the proposed model is to minimize the overall cost, similar to a study conducted by Lamiri et al. [92].

Several studies Fei et al. [55,56,57,58,59] addressed a bi-objective model for maximizing the implementation of ORs and minimizing the overtime of operating cost. Fei et al. [59] scheduled a weekly surgery for an operating theatre that attempts to reserve time blocks. Jerić and Figueira [83] addressed a multi-objective scheduling problem for resident patients in a Croatian hospital and formulated it as a multi-objective binary integer programming restriction placed on medical equipment for daily schedules. Meskens et al. [113] proposed a multi-objective scheduling problem that minimizes makespan and overtime hours and maximizes affinities among members of the surgical team [113, 166] proposed a multi-period, multi-resource scheduling problem as a mixed-integer programming model. Marques et al. [110] introduced a bi-objective model that includes maximizing occupation of the surgical site and maximizing the number of surgeries; this model was implemented in a Portuguese hospital as a case study. Najjarbashi and Lim [119] proposed a three-stage flow-shop scheduling problem as a multi-objective mixed-integer programming model for equilibrating the workload of ORs and surgeons and optimizing waiting times and human reliability. Xiang [174] proposed a multi-objective mixed integer binary programming model for minimizing the makespan, the number of patient deferrals, and waiting time, and maximizing throughput.

6.2 Uncertainty

There has been a vast amount of literature published on the field of uncertainty. Hans et al. [73] proposed a scheduling problem as a stochastic knapsack problem; these authors formulated a robust advanced scheduling problem. While the objective function of the problem is to maximize capacity utilization and minimize the risk of overtime and cancellation; the authors proposed several constructive heuristic and local search methods as solution approaches. Lamiri et al. [92] proposed a stochastic mathematical programming model with random daily emergency demands; the objective function of the proposed model is to minimize the cost to elective patients and the authors proposed a combination of Monte Carlo simulation and Mixed Integer Programming to solve the problem. Shylo et al. [145] formulated an advanced scheduling problem that maximizes the utilization of OR resources and is subject to a set of probabilistic capacity constraints. A chance constraint programming solution method is proposed for solving the block scheduling strategy, which is based on normal approximation of the cumulative duration of surgery. The authors also tested the performance of the approach with actual data from the ophthalmology department of the Veterans Affairs Pittsburgh Healthcare System. Addis et al. [6] proposed an Advanced Scheduling Problem that considers block scheduling of the OR and the duration of stochastic patient surgery; the objective function of the model is to optimize measurement of patient waiting time. The authors developed a robust optimization model for solving the aforementioned problem of uncertain surgery duration.

Gul et al. [68] addressed a multi-stage stochastic programming model that tries to assign surgeries to ORs. The objective function of the model is to minimize the expected cost of surgery cancellations, waiting time, and overtime. The authors used a progressive hedging algorithm to solve the model and validated the model and solution approach with actual data from a large hospital. Bruni et al. [28] developed a stochastic operating theatre scheduling that could manage the uncertainty in demand and the duration of surgery. The authors proposed tailored heuristic solution strategies for addressing the problem. Parizi and Ghate [123] presented a multi-class, multi-resource advanced scheduling problem in which appointment requests can arrive stochastically; they applied an approximate dynamic programming approach rooted in Lagrangian relaxation to solve the aforementioned problem. Wang et al. [169] applied discrete event simulation in the face of uncertain surgical durations, emergency arrivals, and limited downstream resources. Jebali and Diabat [82] proposed a two-stage chance-constraint stochastic programming model that considers the capacity of the ORs and the capacity of the Intensive Care Unit (ICU); the aforementioned problem is solved by the featured Sample Average approximation (SAA) algorithm. Farzad and Mohammad [54] addressed an uncertainty model based on a stochastic programming model to formulate prioritization rules based on moral values in the problem. The objective of the model is to optimize the waiting time and the overtime of surgeries. Gauthier and Legrain [61] applied a stochastic programming approach to their uncertainty model. Uncertainty cases were introduced in the preparation, the operation, and other activities related to surgical cases. The objective of the model was defined as optimizing vacant time, waiting time, and overtime. Kroer et al. [89] proposed robust OR scheduling that minimizes overtime work and releases unused capacity. The objective of the model is to optimize the cost of using the ORs and the overtime costs. Variation in the duration of the operations and arrival of emergency patients was considered to represent uncertainty in the model. For the previously mentioned stochastic model, two mixed integer programming-based heuristics were developed for solving the model. Liu et al. [100] proposed a model that attempts to increase utilization and reduce the cost of the operating theatre and improve satisfaction of the surgeons. In this model, the duration of surgery was considered to be uncertain. To solve the model, the authors suggested two-stage stochastic programming using two stages, based on sample average approximation (SAA). Kamran et al. [86] formulated two-stage stochastic programming and two-stage chance-constraint stochastic programming that considers various criteria in the objective function, including optimizing of waiting time, tardiness, cancellation, block overtime, and the number of days in surgery of each surgeon. The authors solved the aforementioned problem using the SAA method and Benders decomposition technique. Figures 13 and 14 show the portion of documents in the case of deterministic versus uncertainty as well as the portion of different types of uncertainty in modeling. As can be seen in Fig. 13, prior to 2005, the proportion of papers published on deterministic cases was higher than uncertainty cases, while after 2010, the trend dramatically changed. Moreover, as it is clear from Fig. 14, among uncertainty cases, uncertainty in care requirements and resources were two of the most interesting topics until 2005; while duration uncertainty has the highest portion of uncertainty cases after 2010 until now.

Fig. 13
figure 13

Trend of deterministic versus uncertainty along with various types of uncertainties

Full size image
Fig. 14
figure 14

Trend of various types of uncertainties

Full size image

7 Performance Criteria

Different measures are available for evaluating performance of OR scheduling problems. The structure and scope of an OR mathematical model may be limited to these criteria. On the other hand, difficulty and complexity of such a model is related to the number of criteria that are measured in the model. These criteria are known as waiting time (which is described by scholars as two groups distinguished as patient and surgeon), utilization of resources such as ICU and ORs, completion time, patient postponement, financial assets, preferences, humanitarian goals, overtime related to ORs, ICU, and PACU, and other criteria. Figure 15 shows the trend for various criteria that have been previously studied by scholars. Utilization is the most interesting criteria for different time horizons. While financial asset is the second highest criteria between 2005 and 2010, after 2010 it is less interesting than waiting time, overtime, and others. Humanitarian goals have also been studied by researchers after 2010 up to now. As it has been mentioned in previous section, some researchers prefer to evaluate some criteria simultaneously resulting in difficulty of the model.

Fig. 15
figure 15

Trend of various criteria for measuring performance of ORs

Full size image

8 Solution Approaches

This section presents solution approaches that have been used for single-objective optimization OR problems. Figure 16 classifies optimization approaches that have been applied to OR scheduling problems.

Fig. 16
figure 16

Classification of different solution techniques for OR scheduling problems

Full size image

8.1 Single Objective

Attempts at solving OR scheduling problems have used exact, evolutionary, and intelligence algorithms (Fig. 17), which are known as NP-hard problems [35, 56, 125]. For instance, genetic algorithms [52, 59, 110], non-dominated sorting genetic algorithm II [111], integration of greedy and new meta-heuristics [11], tabu search [91, 141], simulated annealing [22, 23], column generation based heuristic [59], Monte-Carlo combined with genetic algorithm [95], a single-objective ACO approach [173], and a hybrid Pareto set-ACO under deterministic conditions [174] were previously developed to address the problem.

Fig. 17
figure 17

Solution techniques

Full size image

Mathematical programming or exact algorithms typically refer to solutions that always find optimal solutions. These approaches typically are applied to small size cases, unless certain mathematical techniques that are suitable for large scale cases are used, such as Benders decomposition algorithm [104, 137]. Some of published studies regarding mathematical programming and metaheuristic (since 2015) are shown in Tables 3, 4, 5 and 6.

Table 3 Exact approaches for OR scheduling problems (since 2015)
Full size table
Table 4 Heuristic approaches for OR scheduling problems (since 2015)
Full size table
Table 5 Simulation approaches for OR scheduling problems (since 2015)
Full size table
Table 6 Metaheuristic approaches for OR scheduling problems (since 2015)
Full size table

Subsequent Sects. (8.1.1–8.3) briefly review various solution approaches that have been addressed in the literature.

8.1.1 Constructive Heuristic

A constructive heuristic is a type of heuristic methodology that begins with a vacant solution and repeatedly extends the present arrangement until a total arrangement is found. A constructive heuristic differs from local search heuristics that begin with a total solution and then endeavors to further propel the present solution through local moves. Examples of such heuristics produced for important issues are: flow shop scheduling, vehicle routing issues, and open shop issues [27, 88, 127]. Table 5 lists references that used constructive heuristic for OR scheduling problems. Varmazyar et al. [164] developed a search algorithm that embedded a constructive heuristic and meta-heuristic algorithm for solving their stochastic operating theatre room problem. In the model presented by Varmazyar et al., the authors analytically computed the completion time of each patient and tested several constructive heuristic algorithms that resulted in selection of the best algorithm as neighborhood structure of meta-heuristic algorithms.

8.1.2 Discrete Event-Simulation

A discrete–simulation (DES) models the task of a system as a discrete order of occasions in time. Every occasion happens at a specific moment in time and denotes a difference in the state of the system [134]. Baesler et al. [15] proposed a combination of discrete even-simulation and simulated annealing for an OR surgery scheduling problem and applied their proposed method in a small hospital in Chile. Ozcan et al. [121] proposed a simulation–optimization model to evaluate resource configuration, improve meeting patient needs, and optimize utilization of ORs. Other application simulation–optimization models are shown in Table 6.

8.1.3 Monte Carlo Simulation

Monte Carlo techniques are an expansive class of computational calculations that depend on repeated arbitrary examination for acquiring numerical outcomes. The fundamental idea of Monte Carlo techniques is to utilize haphazardness to address issues that may be deterministic on a basic level. They are frequently utilized in physical and scientific issues and are most valuable when it is troublesome or difficult to utilize different methodologies. Monte Carlo techniques are typically utilized in three classes of issues: optimization, numerical integration, and creating draws from a probability distribution [90]. Landa et al. [93] combined neighborhood search technique with Monte Carlo simulation to solve an OR problem at an operational planning level by considering two sub-problems: advance scheduling and allocation scheduling; the authors also considered a trade-off as optimization the OR utilization and patient cancellations.

8.1.4 Column Generation

Column generation is a proficient algorithm for illuminating more extensive linear programs. The overall idea is that numerous linear programs are too large for every factor to be considered unequivocally. Since large variables of the factors will be non-essential and are expected to have an estimate of zero in the ideal arrangement, only a subset of factors should be considered, in principle, when addressing the issue. Column generation uses this plan to create only those factors that can improve the work goals—that is, to discover variables with negative reduced cost (assuming no loss of generality and that the issue is a minimization problem). Velásquez et al. [165] applied the column generation approach to optimization of preferences related to ORs. Fei et al. [56] used a column generation based heuristic approach to solve an open scheduling strategy for an OR problem considering different criteria. Fei et al. [59] proposed two-phase OR planning along with three objectives, including maximizing OR utilization, minimizing overtime cost, and minimizing unexpected idle time. In the first phase, the authors solved weekly operating theatre planning using a column generation-based heuristic and in the second phase, daily scheduling planning was solved using a hybrid genetic algorithm.

8.1.5 Dynamic Programming

Dynamic programming is both a mathematical approach and a PC programming technique. The technique was created by Richard Bellman in the 1950s and has been used in various fields, from aviation design to financial matters. Dynamic programming alludes to disentangling a convoluted issue by separating it into less difficult sub-issues in a recursive way. In the computer science field, if an issue can be understood optimally by breaking it into sub-issues and after that recursively to find the ideal answers for the sub-issues, it is said to have an optimal substructure [24, 25]. Liu et al. [102] proposed a heuristic approach that is based on dynamic programming by aggregating states. The authors showed that the proposed algorithm is efficient, especially for large-scale sized OR scheduling problems.

8.1.6 Mixed-Integer Programming

Jebali et al. [81] proposed a two-stage solution approach based on mixed-integer linear programming for OR scheduling; the authors solved their model using the suggested method with commercial software, known as ILOG CPLEX.

8.1.7 Branching Strategies

Cardoen et al. [35] proposed a branch and price algorithm based on column generation for the proposed model. In another work, Cardoen and Demeulemeester [33] used a branch and bound algorithm, which showed that the proposed solution approach needs lengthy computational time, which is costly to apply to a real problem.

8.1.8 Meta-Heuristic Approaches

8.1.8.1 Heuristic Search

Aringhieri et al. [11] applied a two-level metaheuristic algorithm based on greedy search that can solve the joint master surgical schedule and advance scheduling problem. However, the solution approach has not been tested in the case of uncertainty.

8.1.8.2 Genetic Algorithm

Genetic algorithm (GA) is a metaheuristic approach inspired by nature that belongs to the evolutionary algorithm family [65, 76, 143]. Gul et al. [67] proposed a developed genetic algorithm for a daily scheduling problem. Roland et al. [135] used a heuristic approach based on a genetic algorithm to solve mixed-integer programming under minimizing the number of open ORs considering human resource constraints.

8.2 Multi-objective Approaches

8.2.1 Mathematical Approaches

8.2.1.1 Goal Programming

The goal programming approach, first introduced by Charnes et al., [38], is a branch of multi-objective optimization methods and is an extension of linear programming for solving multi-conflicting objective functions. Ozkarahan [122] proposed a multi-objective model in which the objectives of the model include minimizing idle time and overtime and maximizing the satisfaction of patients and staff. The authors proposed a MCDM approach based on goal programming to solve the aforementioned model. Ogulata and Erol [120] also used a similar approach—goal programming—for a hierarchical multi-criteria model to schedule ORs.

8.2.1.2 Epsilon Constraint

Najjarbashi and Lim [119] suggested augmented ɛ-constraint and weighted sum methods for a three-stage multi-objective mixed-integer programming model.

8.2.1.3 Markov Decision Process

Astaraky and Patrick [12] applied a Markov decision model to solve a multi-objective model in which the objective functions consist of minimizing overall waiting time, OR overtime, and ward congestion.

8.2.1.4 Constraint Programming

Meskens et al. [113] proposed a constraint programming paradigm to solve a multi-objective scheduling model, including multiple real-life constraints.

8.2.2 Meta-Heuristic Approaches

8.2.2.1 Simulated Annealing

Sier et al. [146] proposed a simulated heuristic approach to solve mixed-integer nonlinear programming.

8.2.2.2 Tabu-Search

Hsu et al. [79] proposed a heuristic approach based on tabu-search to solve multi-objective programming. They considered two objectives in their model: minimizing the number of nurses in PACU and minimizing completion time.

8.2.2.3 Genetic Algorithm

Jerić and Figueira [83] used NSGAII along with two other metaheuristics, variable neighborhood search and scatter search, for their multi-objective scheduling problem and compared the results of their computational experiments. Lin and Chou [99] applied a hybrid genetic algorithm to a multi-objective OR scheduling problem in which the objectives of the model included maximizing utilization of ORs, minimizing the overtime operating costs, and minimizing the waste cost associated with the unused time. The authors compared the results of the hybrid genetic algorithm with certain heuristics methods and showed that the proposed hybrid genetic algorithm has significantly better performance as compared with proposed heuristics for large problem instances.

8.2.2.4 Ant Colony Optimization

Xiang [174] proposed different types of ant colony optimization approaches for a three-objective mixed-integer binary programming model; the authors also used MD Anderson Cancer Center as a test case for evaluating the performance of the approach.

8.3 Hybrid Approaches

Fei et al. [59] used a genetic algorithm and column-generation-based heuristic hybrid method for their model; the authors applied a column-generation based approach in the planning phase and then proposed a hybrid genetic algorithm to solve daily scheduling problems.

8.4 Statistical Comparison of Solution Methods

There are pros and cons to using different methods as solution approaches. From the point of view of metaheuristics, the key remark is that the purpose of meta-heuristics is to search for and find proper solutions rather than guaranteed optimal solutions. Consequently, if the model is simple enough to allow mathematical methods such as decomposition algorithms to yield an optimal solution, then it is not compulsory to use metaheuristic algorithms. Another disadvantage of metaheuristics is that many parameters must be set by the decision-maker rather than by conventional algorithms, for example decomposition algorithms. In many problems, the solution found by metaheuristics is sensitive to these parameters and therefore, sometimes, several executions of the meta-heuristics with various parameter sets are required before a suitable solution is found. That is, metaheuristics behave like a poor “black box” and are more challenging to use when only a single run of the algorithm is allowed because of time or other limitations.

For example, a drawback of simulated annealing (SA) is the struggle with defining a suitable cooling schedule for both single and multi-objective optimization problems. As another example, it is challenging to design a proper Tabu search technique, since the number of objective functions increases, especially in the case of many-objective.

For using particle swarm optimization (PSO), adjustments are needed to guarantee finding the local optimum; however, when the PSO is used for multi-objective optimization problems, it is challenging to control diversity. The role of PSO parameters in its convergence and its loss of diversity has been rarely addressed.

Furthermore, metaheuristic algorithms are approximate and are usually non-deterministic. Moreover, they are not problem-specific. Additionally, there is no mathematical proof for metaheuristics, as they are based on random evolution and it is also difficult to prove their convergence.

In contrast, metaheuristics are also based on different interpretations of what constitutes an intelligent search [64]. There are several motivations for using these methods; for example, in metaheuristic, considering concavity or convexity is not needed. They also can produce a number of alternative solutions in a single run, which is another advantage of evolutionary algorithms [142]. Additionally, from the point of combination, evolutionary algorithms (such as genetic algorithm) can integrate with certain decomposition algorithms [129].

Additionally, there are some metaheuristics that are suitable for solving global optimization problems, including non-convex and discontinuous problems [75]. Mete and Zabinsky [114] suggested a population-based algorithm for optimizing multi-objective optimization problems (MOOPs), which improves exploration of the solution space by employing Markov kernels, hit-and-run, and pattern hit-and-run. Random search methods competently optimize single ill-structured functions [177, 178] and multi-objective problems [84]. Several continuous and discrete MOOPs were performed by population-based methods, such as evolutionary algorithms [42, 84]. As stated previously, the above-mentioned methods are suitable for MOOPs since they produce a set of solutions in a single iteration.

Additionally, some metaheuristics are able to find a set of well-converged and diversified non-dominated solutions, known as Pareto solutions, in a single run as these algorithms perform better in dealing with some MOOPs, such as huge search space, uncertainty, noise, and disjoint Pareto curves [42, 101, 176].

Conversely, for large-scale optimization problems, hybrid and decomposed methods are two categories of optimization methods which could find efficient solution for various problems [46]. Moreover, mathematical approaches mostly possess strong algebra perception, and decision-makers are able to prove convergence of these algorithms analytically and can adjust the optimality gap precisely if required.

Figure 18 presents trends in the solutions applied to OR scheduling problems. Before 2005, optimization-simulation, heuristic-based on exact methods, constructive and improvement heuristics, dispatching-rule-based heuristics, and metaheuristics were the most popular approaches used by scholars in OR problems. Between 2005 and 2010, the trends changed slightly; focus on simulation–optimization decreased and conversely other mathematical approaches such as dynamic programming, discrete-event simulation, column generation, branch and price, branch and cut, branch and bound were addressed by researchers. From 2010 until now, many works have been solved by simulation methods; however, there has been little focus on Monte Carlo simulation, Markov decision processes, and discrete-event simulation. It is also clear from Fig. 18 that application of metaheuristic algorithms in OR problems has increased dramatically.

Fig. 18
figure 18

Trends of solution approaches applied in OR scheduling problems

Full size image

9 Software

The most common solutions for OR scheduling are limited to mathematical modeling and proposing theoretical approaches. There is a very limited number of software solutions for these particular problems and there is an urgent need for additional exploration in this field in order to translate all pure outputs to commercial software. Table 7 presents a list of the top software for OR scheduling.

Table 7 List of top softwares for OR scheduling
Full size table

10 Conclusion and Directions for Future Studies

The OR scheduling problem is a critical issue in healthcare management. This paper analyzed and comprehensively reviewed in field. The analysis was done on information corresponding to the years between 2000 and 2019 using the Scopus database. In terms of analysis, the following parameters were addressed: keywords, publisher, author, and citation analysis; in the comprehensive review, the decision levels used in OR and surgery scheduling problems were introduced. The problems in OR scheduling are categorized into three decision levels, including strategical, tactical, and operational levels. The review was followed by definitions of different types of scheduling strategies. A review of mathematical modeling in both deterministic and uncertainty cases was presented. A generic illustration of the surgery room and other related facilities was presented.

Since optimizing OR problems are NP-hard optimization problems, this work studied previous research that employed various methods to address these problems. For this aim, solution methods were categorized into two groups as solutions proposed for single-objective problems and those suggested for multi-objective problems. Details of approaches of each category were described. Pros and cons of each category along with statistical comparison were addressed. Lastly, essential software in the field were introduced. This work revealed some important points that are worth mentioning, as follows:

  • In terms of analysis, trends predict that studies of OR scheduling problems will increase in the next few years. In addition, optimization, genetic algorithm, surgery scheduling, and radiosurgery instances are the most interesting keywords for scholars.

  • Among different type of scheduling strategies, the block scheduling strategy has been addressed more in-depth as compared to two other scheduling strategies.

  • Recent publications have focused more on elective patients than on non-elective patients.

  • Uncertainty mathematical modeling along with multi-objective functions are more interesting to scholars since they are more realistic, while duration uncertainty is the most interesting topic among scholars.

  • Analysis of performance criteria shows that utilization and waiting time are the most popular criteria among researchers, while patient postponement, preferences, and completion time have been less studied as compared to other criteria.

  • Various solution methods have pros and cons; however, the literature shows that simulation–optimization and metaheuristic methods have been concentrated upon by many researchers studying OR problems in the last several decades.

  • There is limited software available as user-interference applications for these specific problems, and there is a critical need for more investigation in this field.

As a future study, an in-depth review of multi-objective and many-objective OR scheduling is suggested. Additional research on the development of novel and hybrid approaches for addressing an actual problem is proposed. Some studies in the field along with introducing decision support systems for solving large-scale problems could be a suitable direction for future work. From the perspective of scientometric analysis, bibliometric analysis is valuable.