# Operating Room Surgery Scheduling with Fuzzy Surgery Durations Using a Metaheuristic Approach

Authors: Habibeh Nazif
Journal: Advances in Operations Research
 (2018)

---

## Abstract

Operating room (OR) surgery scheduling is a challenging combinatorial optimization problem that determines the operation start time of every surgery to be performed in different surgical groups, as well as the resources assigned to each surgery over a schedule period. One of the main challenges in health care systems is to deliver the highest quality of care at the lowest cost. In real-life situations, there is significant uncertainty in several of the activities involved in the delivery of surgical care, including the duration of the surgical procedures. This paper tackles the operating room surgery scheduling problem with uncertain surgery durations, where uncertainty in surgery durations is represented by means of fuzzy numbers. The problem can be considered as a Fuzzy Flexible Job-shop Scheduling Problem (FFJSP) due to similarities between operating room surgery scheduling with uncertain surgery durations and a multi-resource constraint flexible job-shop scheduling problem with uncertain processing times. This research handles both the advanced and allocation scheduling problems simultaneously and provides an Ant Colony Optimization (ACO) metaheuristic algorithm which utilized a two-level ant graph to integrate sequencing jobs and allocating resources at the same time. To assess the performance of the proposed method, a computational study on five test surgery cases is presented, considering both deterministic and fuzzy surgery durations to enhance the significance of the study. The results of this experiment demonstrated the effectiveness of the proposed metaheuristic algorithm.


---

## Body

## 1. Introduction

Operating room surgery scheduling deals with determining operation start times of surgeries on hand and allocating the required resources to the scheduled surgeries, considering several constraints to ensure a complete surgery flow. As a vital hospital component, the OR has been estimated to account for more than 40% of a hospital’s total revenues and a similarly large proportion of its total expenses [1].OR management consists of two phases: first, planning provides the date of surgery for each patient, considering the availability of operating rooms and surgeons. Second, daily scheduling determines the sequence of operations in each operating room each day, considering the availability of material and human resources [2]. So, it is rather important to improve OR management to be able to provide well-timed treatments for the patients and an efficient use of clinic resources. In addition, in real-life situations, there is a highly importance of uncertainty in various activities involved in delivery of surgical care and attention, including the duration of the surgical steps in which more complicates assignment decision. The recent OR planning and scheduling literature is classified by [3]. Furthermore, a review of the trade-offs in the OR planning is presented by [4].Generally, a surgery progress involves different activities before, during, and after an actual surgical procedure. Also, the resources needed to perform a surgery are comprised of personnel such as surgeons, nurses, and anaesthetists and facilities like preoperative holding units (PHUs), postanaesthesia care units (PACUs), and intensive care units. Moreover, alternative factors such as priorities for services, different surgical specialties, and personnel shifts also have to be taken into consideration.Some papers about OR surgery scheduling can be found in [5–9]. As well, an ant colony optimization approach is introduced by [10] to solve an operating room surgery scheduling problem. Comprehensive classifications depending on surgery durations (deterministic or stochastic), patient arrivals (elective and nonelective), and operations research strategy are presented by [6]. When activity durations remain highly uncertain, a great variety of methods are considered to deal with many useful situations. A review of fundamental methods for scheduling under uncertainty is available in [11]. Also, a stochastic programming procedure for the project scheduling, where uncertain processing times are taken to be stochastic factors can be found in [12]. More recently, a procedure is suggested by [13] to deal with the resource constrained project scheduling problem with uncertain activity durations, so that uncertain durations are defined by independent random variables with a known probability distribution function.A hybrid two-phase optimization algorithm is developed by [14] for surgeries scheduling, while a rolling horizon approach for the patient selection and assignment is suggested by [15]. Furthermore, a systematic approach is proposed by [16] to help the surgical planner in the scheduling of elective surgeries. A two-stage robust optimization to elective surgery and downstream capacity planning is applied by [17].Fuzzy numbers or, more generally, fuzzy intervals are used to modelling ill-known processing times as an alternative and complementary approach. The fuzzy approach has been around for more than two decades and has received the attention of several researchers [18]. In particular, several metaheuristics have been proposed to solve the fuzzy job-shop scheduling problem since the 1990s, such as the simulated annealing method [19], the genetic algorithm (GA) [20], the particle swarm optimization algorithm [21], a hybrid algorithm which combines a GA with a very efficient local search method [22], the swarm based neighbourhood search algorithm [23], a hybrid algorithm, combining particle swarm optimization with tabu search [24], and an artificial bee colony algorithm [25].Flexibility as another characteristic of real-world problems is contemplated in the flexible job-shop scheduling problem, a variant of the job-shop scheduling problem where multiple machines can perform the same operation. Furthermore, fuzzy processing times and flexibility on the machines can be considered simultaneously. This case is called the fuzzy flexible job-shop scheduling problem (FFJSP). This will be the problem considered in this paper with the objective of minimizing the makespan.Also, flexibility in job-shop scheduling problem was first addressed by researches in the 1990s. The approaches from [26–28] obtain the best results so far for many flexible job-shop scheduling problem instances. The combination of flexibility and uncertainty in FFJSP is used by some researches as follows: the genetic algorithm given in [29], the hybrid artificial bee colony algorithm from [30], the estimation distribution algorithm used in [31], the coevolutionary algorithm from [32], or the swarm-based neighbourhood search algorithm from [33].In this paper, an operating room surgery scheduling problem with uncertain surgery durations is addressed, where uncertainty in surgery durations is represented by means of fuzzy numbers. The problem can be considered as a FFJSP due to similarities between operating room surgery scheduling with uncertain surgery durations and a multi-resource constraint flexible job-shop scheduling problem with uncertain processing times. A typical surgical case scheduling problem in the mixed decision level generally covers two sub-problems: advanced scheduling (also known as OR planning) and allocation scheduling. It is evident that the two sub-problems are generally formulated as separate combinatorial optimization models. Unlike most published papers in this field, this research handles both the advanced and allocation scheduling problems simultaneously and provides an ant colony optimization (ACO) approach with a two-level ant graph to efficiently solve such a computationally challenging problem.The remainder of this paper is organized as follows: Section2 is devoted to the surgery scheduling environment. In Section 3, the detail of the proposed algorithm is presented. Section 4 provides the computational experiments to validate and evaluate the approach. Finally, the paper is ended in Section 5 with conclusion and suggestion for future research.


## 2. Surgery Scheduling Problem

We can sort surgeries in a hospital as elective or emergent surgery. In this article, elective surgery is considered. Here, the patient is picked up by the transporter from either the inpatient ward or the ambulatory surgery unit. The complete elective surgery process generally includes three steps: the pre-surgery (setup), the peri-surgery (surgery), and post-surgery (recovery). Within the first step, if it is necessary, the essential patient information will be confirmed and proper injections will be given. If the given operating room is not ready, the patient has to wait at the PHU for the setup step. During the real surgery step, different kinds of operations are donated to different surgery times and medical groups. When all required resources are prepared, the surgery can begin. In the third step, the patient is transferred to the PACU for recovery as well as further treatment, e.g., intensive care units. After all, medical workers must clean the operating room for another surgery.We have to change the time of the surgery progress if any resource during the three-step surgery is not available promptly and this affects the efficiency of OR. Most of the time, a complete surgery needs personnel and facilities. Essentially, the main facility resources are multifunctional and can support different kinds of cases, as the personnel resources are ever nonhomogeneous regarding their surgery department, expertise, experience, and general availability. This article only contains the surgeons’ nonhomogeneity. However, other personnel resources such as nurses and anesthetists are open to any surgeries and thought to be multifunctional.It is supposed that there is a set of surgeries to be performed within an operating collection with various resources. Every single surgery is accompanied with surgery demand and resource demand. Surgery demand is to identify the specific surgery specialty and uncertain surgery duration, while resource demand implies all resources required for the complete steps of any surgery. The next step can begin regarding all of the available resources and on the performance of every previous step. The scheduling goal is to minimize makespan. The mathematical model that is used here is the optimization model applied by Xiang et al. for solving an operating room surgery scheduling problem (for more details see [10]).


### 2.1. Uncertain Durations

In real-life applications, it is often the case that the exact duration of the surgical procedures is not known in advance. This naturally leads to modelling such durations using fuzzy intervals or fuzzy numbers. A fuzzy intervalA is a fuzzy set on the reals with membership function μA:R→0,1 such that its α-cuts Aα=u∈R:μA(u)≥α, α∈(0,1], are intervals. A fuzzy interval is a fuzzy number if its α-cuts denoted n_α,n-α, are closed, its support A0=u∈R:μAu>0 is compact and there is a unique modal value u∗, μAu∗=1.The simplest model of fuzzy interval is a triangular fuzzy number (TFN), using an intervala1,a3 of possible values and a modal value a2 in it. For a TFN A, denoting A=a1,a2,a3, the membership function takes the following triangular shape:(1)μAx=x-a1a2-a1:a1≤x≤a2x-a3a2-a3:a2≤x≤a30:x<a1ora3<xIn the fuzzy flexible job shop, two issues must be addressed: the precise meaning of minimal makespan when such makespan is a TFN as well as the means of extending the two operations of addition and maximum to work with TFNs.The expected value for a TFNA is given by(2)EA=14a1+2a2+a3It induces a total ordering ≤E in the set of fuzzy intervals, where for any two fuzzy intervals M and N, M≤EN if and only if E(M)≤E(N). Clearly, for any two TFNs A and B, if ∀i,ai≤bi then A≤EB.Regarding the sum, for any pair of TFNsA and B,(3)A+B=a1+b1,a2+b2,a3+b3Also, for any two TFNs A and B, if F denotes their maximum and(4)G=max⁡a1,b1,max⁡a2,b2,max⁡a3,b3its approximated value, it holds that(5)∀α∈0,1,f_α≤g_α,f-α≤g-α,where f_α,f-α is the α-cut of F. In particular, F and G have identical support and modal value. This approximation has been used in [34, 35].


## 2.1. Uncertain Durations

In real-life applications, it is often the case that the exact duration of the surgical procedures is not known in advance. This naturally leads to modelling such durations using fuzzy intervals or fuzzy numbers. A fuzzy intervalA is a fuzzy set on the reals with membership function μA:R→0,1 such that its α-cuts Aα=u∈R:μA(u)≥α, α∈(0,1], are intervals. A fuzzy interval is a fuzzy number if its α-cuts denoted n_α,n-α, are closed, its support A0=u∈R:μAu>0 is compact and there is a unique modal value u∗, μAu∗=1.The simplest model of fuzzy interval is a triangular fuzzy number (TFN), using an intervala1,a3 of possible values and a modal value a2 in it. For a TFN A, denoting A=a1,a2,a3, the membership function takes the following triangular shape:(1)μAx=x-a1a2-a1:a1≤x≤a2x-a3a2-a3:a2≤x≤a30:x<a1ora3<xIn the fuzzy flexible job shop, two issues must be addressed: the precise meaning of minimal makespan when such makespan is a TFN as well as the means of extending the two operations of addition and maximum to work with TFNs.The expected value for a TFNA is given by(2)EA=14a1+2a2+a3It induces a total ordering ≤E in the set of fuzzy intervals, where for any two fuzzy intervals M and N, M≤EN if and only if E(M)≤E(N). Clearly, for any two TFNs A and B, if ∀i,ai≤bi then A≤EB.Regarding the sum, for any pair of TFNsA and B,(3)A+B=a1+b1,a2+b2,a3+b3Also, for any two TFNs A and B, if F denotes their maximum and(4)G=max⁡a1,b1,max⁡a2,b2,max⁡a3,b3its approximated value, it holds that(5)∀α∈0,1,f_α≤g_α,f-α≤g-α,where f_α,f-α is the α-cut of F. In particular, F and G have identical support and modal value. This approximation has been used in [34, 35].


## 3. Ant Colony Algorithm for Surgery Scheduling Problem

In this paper, an ant colony optimization algorithm is developed to solve the surgery scheduling problem with uncertain surgery durations. The ACO is originally designed to solve the well-known travelling salesman problem (TSP) [36]. For original ACO in TSP, there is an ant graph in which each node corresponds to a city, and the arcs correspond to the distances between cities. Ants traverse all the nodes to obtain a minimum tour. To tailor ACO to surgery scheduling problem, cities can be mapped to surgeries, a nodes tour then turns to be the sequence of surgeries. However, the complete surgery scheduling determines not only the sequencing of surgeries in time period, but also the resources allocation for each of the surgery steps. Here, a two-level ant graph is used for the surgery scheduling problem as Xiang et al. [10] applied in their research. A two-level hierarchical ant graph is shown in Figure 1. The nodes in the outer-graph represent the surgeries, and the directional arc, indicating the precedence sequence, is used to link two nodes. The inner-graph nodes represent the total resources of the OR management system which covers the complete 3-step surgery procedure.Figure 1
The two-level ant graph (figure reproduced from Xiang et al. (2015) [10]).


### 3.1. The ACO Algorithm Description

In the ACO, the ants depose the chemical pheromone while moving in their environment. They are also able to detect and to follow pheromone trails. Ants build solutions using a probabilistic transition rule. In this paper, two transition rules are introduced for the inner and outer ant graphs. In the outer surgery graph, the probabilityPij that an ant will choose node j from node i is defined as follows:(6)Pij=τijα∗ηij-β∑j∈I0τijα∗ηij-βifj∈I00otherwisewhere I0 is a feasible node set, α and β are parameters that control the relative importance of trail versus visibility. Each of the ants builds a solution using a combination of the information provided by the outer pheromone trail τij between nodes i and j, and by the heuristic function defined by ηij=Di,j, where Di,j represents the duration time from node i to node j.In the inner resource graph, the probabilityPcmki that ant k will choose resource m for the cth resource type state of surgery i is defined as follows:(7)Pcmki=​inτcmi∗inλmkα∗ηincm-β∑r∈R​inτcri∗inλrkα∗ηincr-βifr∈R0otherwisewhere R is the available set of resources for selecting the next resource node, the inner surgery-related pheromone,τincmi, is denoted to record the information which links the surgery with resources in different steps; and the inner resource-itself pheromone, inλmk, is defined to record the information related to resource utilization while an ant is constructing an inner resource allocation solution. The heuristic function is defined by inηcm=Dc,m, where Dc,m is the duration of surgery i under resource m of resource type c.To balance the resource utilization in any surgery step, once a resource is selected, its opportunity to be selected by another surgery should be reduced. Therefore,inλmk is locally updated after visiting each node by the following equality.(8)inλmk=inλmk-q0where q0 is the decremented pheromone value.To allow the ants to share information about good solutions, the updating of the pheromone trail must be established. In the outer level graph, when all the ants finish traversing the nodes, the ant with the best schedule in the iteration updates the trails as follows:(9)τij=1-ρ∗τij+ρ∗∆τij(10)∆τij=LminLkifantkgoesthroughi,jinthisiteration0otherwisewhere ρ denotes the pheromone evaporation rate, Lk is the makespan of a solution, and Lmin is the best makespan of all solutions given by a set of ants.For the inner level graph, we have(11)​inτcmi=1-ρ∗inτcmi+ρ∗∆inτcmi(12)∆inτcmi=LminLkifantkgoesthroughsurgryiwithresourcegraphc,m0otherwise


## 3.1. The ACO Algorithm Description

In the ACO, the ants depose the chemical pheromone while moving in their environment. They are also able to detect and to follow pheromone trails. Ants build solutions using a probabilistic transition rule. In this paper, two transition rules are introduced for the inner and outer ant graphs. In the outer surgery graph, the probabilityPij that an ant will choose node j from node i is defined as follows:(6)Pij=τijα∗ηij-β∑j∈I0τijα∗ηij-βifj∈I00otherwisewhere I0 is a feasible node set, α and β are parameters that control the relative importance of trail versus visibility. Each of the ants builds a solution using a combination of the information provided by the outer pheromone trail τij between nodes i and j, and by the heuristic function defined by ηij=Di,j, where Di,j represents the duration time from node i to node j.In the inner resource graph, the probabilityPcmki that ant k will choose resource m for the cth resource type state of surgery i is defined as follows:(7)Pcmki=​inτcmi∗inλmkα∗ηincm-β∑r∈R​inτcri∗inλrkα∗ηincr-βifr∈R0otherwisewhere R is the available set of resources for selecting the next resource node, the inner surgery-related pheromone,τincmi, is denoted to record the information which links the surgery with resources in different steps; and the inner resource-itself pheromone, inλmk, is defined to record the information related to resource utilization while an ant is constructing an inner resource allocation solution. The heuristic function is defined by inηcm=Dc,m, where Dc,m is the duration of surgery i under resource m of resource type c.To balance the resource utilization in any surgery step, once a resource is selected, its opportunity to be selected by another surgery should be reduced. Therefore,inλmk is locally updated after visiting each node by the following equality.(8)inλmk=inλmk-q0where q0 is the decremented pheromone value.To allow the ants to share information about good solutions, the updating of the pheromone trail must be established. In the outer level graph, when all the ants finish traversing the nodes, the ant with the best schedule in the iteration updates the trails as follows:(9)τij=1-ρ∗τij+ρ∗∆τij(10)∆τij=LminLkifantkgoesthroughi,jinthisiteration0otherwisewhere ρ denotes the pheromone evaporation rate, Lk is the makespan of a solution, and Lmin is the best makespan of all solutions given by a set of ants.For the inner level graph, we have(11)​inτcmi=1-ρ∗inτcmi+ρ∗∆inτcmi(12)∆inτcmi=LminLkifantkgoesthroughsurgryiwithresourcegraphc,m0otherwise


## 4. Computational Experiments

### 4.1. Illustrative Test Cases

The proposed ACO is assessed using five test surgery cases presented by Xiang et al. [10], that are different in surgery duration and their required OR resources. They are classified into five types, small, medium, large, extra-large, and special. Regarding surgery duration, uncertainty is added to the durations based on the idea from [34]. Let d be the real duration of a surgery, so we build a TFN D=d1,d2,d3 where d2=d and d1 and d3 are random positive integer values verifying that d1∈[0.85d,d) and d3∈[2d-d1,1.2d]. In the case that no integer value exists in the interval [0.85d,d), we set d1=max⁡1,d-1, and if there is no integer value in [2d-d1,1.2d], d3 takes a random value in [d+1,d+2].The information about these five surgery cases are given in Tables1, 2, and 3. For more details about surgery cases, see [10].Table 1
The surgery durations (table reproduced from Xiang et al. (2015) [10]).
Pre-surgery Surgery case Post-surgery Small Medium Large E-large Special Duration  Random. Normal (min) (8, 2) (33, 15) (86, 17) (153, 17) (213, 17) (316, 62) (28, 17)Table 2
The resources required in different resource types (table reproduced from Xiang et al. (2015) [10]).
Resource type No. of nurses No. of anesthetists 1 1 1 2 1 2 3 2 1 4 2 2Table 3
The five test cases (table reproduced from Xiang et al. (2015) [10]).
Number of CaseNo. Surgeries PHUbeds Nurses Surgeons ORs PACUbeds Anesthetist Surgery type(S:M:L:E:SE) 1 10 2 8 6 4 4 6 2:6:1:1:0 2 10 1 5 5 2 2 5 2:6:1:1:0 3 15 3 10 8 4 3 8 3:9:2:1:0 4 20 3 15 10 5 4 8 4:12:3:1:0 5 30 4 20 10 6 5 10 7:18:3:1:1


### 4.2. The Set up Parameter Values

The set up parameter values used in the ant system scheduling algorithms are often very important in getting good results. All parameters are experimented by different adjustments and the final parameters used in our paper are displayed as follows:(i)
α: this algorithm works well with a value around 1.(ii)
β: a value around 2 appeared to offer the best trade-off between following the heuristic and allowing the ants to explore the research space.(iii)
ρ: the pheromone evaporation parameter tests a value of range 0.1- 0.99 to find good solutions, and finally a value around 0.2 in surgery cases 1 and 2 and 0.1 in other cases is accepted.(iv)
q0: the decremented pheromone value is set with a value around 0.1.(v)
the number of ants: around 30 ants are in surgery cases 1 and 2; 50 ants are in surgery cases 3, 4, and 5.


### 4.3. Experiments Result Discussion

The ACO algorithm is implemented with Matlab and run using a laptop running Windows 7 with Intel Core2 Duo, 4 GB memory. Furthermore, the CPU time varied according to the complexity of the test cases as well as the number of ants used.The proposed ACO is tested on five test surgery cases, considering both deterministic and fuzzy surgery durations. Tables4 and 5 show the result from the five test cases with fuzzy surgery durations. In Table 4, the columns with the header Makespan, the finishing time of all surgeries to be scheduled, contain the makespan (a TFN) together with its expected value. The next column, with header Overtime, records the total additional time required in addition to the regular working hours (8 h). In this paper, if a surgery cannot be completed within 10 h, it will be scheduled for the next day. This means the authorized overtime is limited to 2 h. Also, the variation coefficient of working times (VCWT) defined as the ratio of the standard deviation to the mean is calculated in Table 5, where the expected values of different resources are considered.Table 4
Computational results (fuzzy durations).
Makespan Case No. (TFN) (Expected value) Overtime 1 (329,351,377) 352 0 2 (538,568,652) 582 102 3 (428,449,543) 467 0 4 (474,498,590) 515 35 5 (779,793,897) 816 336Table 5
Resources’ VCWT (fuzzy durations).
VCWT Case No. OR Nurse Anesthetist Surgeon 1 Surgeon 2 Surgeon 3 Surgeon 4 1 0.09 0.56 0.16 0 0.22 0.04 - 2 0.07 0.47 0.37 0 0.08 0.03 - 3 0.09 0.45 0.43 0.27 0.26 0.24 - 4 0.11 0.48 0.21 0.11 0.18 0.23 0.15 5 0.11 0.47 0.32 0.23 0.12 0.13 0.03It is clear from Table4 that ACO scheduling realizes the makespan within one working day except in test case 5.The resources’ VCWT for test cases 1 and 2 is shown in Figure2. Clearly, the VCWT is reduced in test case 2. Furthermore, test case 2 is the resource shortage case to test case 1. Therefore, the ACO performs even better especially facing to resource shortage problem which is an important issue in OR management, because currently more hospitals are facing the nurse shortage issue.Figure 2
Comparison on VCWT in test cases 1 and 2.Regarding deterministic surgery durations, the proposed ACO is compared against the results reported by Xiang et al. [10]. They presented an ant colony optimization approach to solve an operating room surgery scheduling problem. Tables 6 and 7 show the results from the five test cases. In Table 6, the makespan and overtime are given, while the variation coefficient of resources’ working time is calculated in Table 7.Table 6
Computational results (deterministic durations).
Case No. Method Makespan Overtime 1 ACO 348 0 [10] 341 0  2 ACO 570 90 [10] 574 94  3 ACO 458 0 [10] 464 0  4 ACO 501 21 [10] 489 9  5 ACO 798 318 [10] 789 309Table 7
Resources’ VCWT (deterministic durations).
VCWT Case No. Method OR Nurse Anesthetist Surgeon 1 Surgeon 2 Surgeon 3 Surgeon 4 1 ACO 0.08 0.56 0.15 0 0.21 0.04 - [10] 0.08 0.55 0.13 0 0.20 0.04 -  2 ACO 0.05 0.45 0.36 0 0.07 0.02 - [10] 0.06 0.45 0.37 0 0.07 0.03 -  3 ACO 0.08 0.44 0.41 0.25 0.25 0.23 - [10] 0.08 0.45 0.42 0.26 0.26 0.23 -  4 ACO 0.10 0.47 0.20 0.09 0.17 0.22 0.14 [10] 0.09 0.46 0.18 0.08 0.15 0.23 0.14  5 ACO 0.10 0.45 0.31 0.21 0.09 0.13 0.02 [10] 0.09 0.44 0.31 0.21 0.08 0.12 0.01It is clear from Table6 that the proposed ACO finds schedules with less makespan than the presented method by [10] in cases 2 and 3. Moreover, in case 5, the results indicate that all surgeries have to be finished until the second working day. As it can be seen from Table 7, the ACO is competitive in terms of the values of the resources’ VCWT found, which indicates the proposed algorithm can produce a schedule with relative balanced resource utilization.


## 4.1. Illustrative Test Cases

The proposed ACO is assessed using five test surgery cases presented by Xiang et al. [10], that are different in surgery duration and their required OR resources. They are classified into five types, small, medium, large, extra-large, and special. Regarding surgery duration, uncertainty is added to the durations based on the idea from [34]. Let d be the real duration of a surgery, so we build a TFN D=d1,d2,d3 where d2=d and d1 and d3 are random positive integer values verifying that d1∈[0.85d,d) and d3∈[2d-d1,1.2d]. In the case that no integer value exists in the interval [0.85d,d), we set d1=max⁡1,d-1, and if there is no integer value in [2d-d1,1.2d], d3 takes a random value in [d+1,d+2].The information about these five surgery cases are given in Tables1, 2, and 3. For more details about surgery cases, see [10].Table 1
The surgery durations (table reproduced from Xiang et al. (2015) [10]).
Pre-surgery Surgery case Post-surgery Small Medium Large E-large Special Duration  Random. Normal (min) (8, 2) (33, 15) (86, 17) (153, 17) (213, 17) (316, 62) (28, 17)Table 2
The resources required in different resource types (table reproduced from Xiang et al. (2015) [10]).
Resource type No. of nurses No. of anesthetists 1 1 1 2 1 2 3 2 1 4 2 2Table 3
The five test cases (table reproduced from Xiang et al. (2015) [10]).
Number of CaseNo. Surgeries PHUbeds Nurses Surgeons ORs PACUbeds Anesthetist Surgery type(S:M:L:E:SE) 1 10 2 8 6 4 4 6 2:6:1:1:0 2 10 1 5 5 2 2 5 2:6:1:1:0 3 15 3 10 8 4 3 8 3:9:2:1:0 4 20 3 15 10 5 4 8 4:12:3:1:0 5 30 4 20 10 6 5 10 7:18:3:1:1


## 4.2. The Set up Parameter Values

The set up parameter values used in the ant system scheduling algorithms are often very important in getting good results. All parameters are experimented by different adjustments and the final parameters used in our paper are displayed as follows:(i)
α: this algorithm works well with a value around 1.(ii)
β: a value around 2 appeared to offer the best trade-off between following the heuristic and allowing the ants to explore the research space.(iii)
ρ: the pheromone evaporation parameter tests a value of range 0.1- 0.99 to find good solutions, and finally a value around 0.2 in surgery cases 1 and 2 and 0.1 in other cases is accepted.(iv)
q0: the decremented pheromone value is set with a value around 0.1.(v)
the number of ants: around 30 ants are in surgery cases 1 and 2; 50 ants are in surgery cases 3, 4, and 5.


## 4.3. Experiments Result Discussion

The ACO algorithm is implemented with Matlab and run using a laptop running Windows 7 with Intel Core2 Duo, 4 GB memory. Furthermore, the CPU time varied according to the complexity of the test cases as well as the number of ants used.The proposed ACO is tested on five test surgery cases, considering both deterministic and fuzzy surgery durations. Tables4 and 5 show the result from the five test cases with fuzzy surgery durations. In Table 4, the columns with the header Makespan, the finishing time of all surgeries to be scheduled, contain the makespan (a TFN) together with its expected value. The next column, with header Overtime, records the total additional time required in addition to the regular working hours (8 h). In this paper, if a surgery cannot be completed within 10 h, it will be scheduled for the next day. This means the authorized overtime is limited to 2 h. Also, the variation coefficient of working times (VCWT) defined as the ratio of the standard deviation to the mean is calculated in Table 5, where the expected values of different resources are considered.Table 4
Computational results (fuzzy durations).
Makespan Case No. (TFN) (Expected value) Overtime 1 (329,351,377) 352 0 2 (538,568,652) 582 102 3 (428,449,543) 467 0 4 (474,498,590) 515 35 5 (779,793,897) 816 336Table 5
Resources’ VCWT (fuzzy durations).
VCWT Case No. OR Nurse Anesthetist Surgeon 1 Surgeon 2 Surgeon 3 Surgeon 4 1 0.09 0.56 0.16 0 0.22 0.04 - 2 0.07 0.47 0.37 0 0.08 0.03 - 3 0.09 0.45 0.43 0.27 0.26 0.24 - 4 0.11 0.48 0.21 0.11 0.18 0.23 0.15 5 0.11 0.47 0.32 0.23 0.12 0.13 0.03It is clear from Table4 that ACO scheduling realizes the makespan within one working day except in test case 5.The resources’ VCWT for test cases 1 and 2 is shown in Figure2. Clearly, the VCWT is reduced in test case 2. Furthermore, test case 2 is the resource shortage case to test case 1. Therefore, the ACO performs even better especially facing to resource shortage problem which is an important issue in OR management, because currently more hospitals are facing the nurse shortage issue.Figure 2
Comparison on VCWT in test cases 1 and 2.Regarding deterministic surgery durations, the proposed ACO is compared against the results reported by Xiang et al. [10]. They presented an ant colony optimization approach to solve an operating room surgery scheduling problem. Tables 6 and 7 show the results from the five test cases. In Table 6, the makespan and overtime are given, while the variation coefficient of resources’ working time is calculated in Table 7.Table 6
Computational results (deterministic durations).
Case No. Method Makespan Overtime 1 ACO 348 0 [10] 341 0  2 ACO 570 90 [10] 574 94  3 ACO 458 0 [10] 464 0  4 ACO 501 21 [10] 489 9  5 ACO 798 318 [10] 789 309Table 7
Resources’ VCWT (deterministic durations).
VCWT Case No. Method OR Nurse Anesthetist Surgeon 1 Surgeon 2 Surgeon 3 Surgeon 4 1 ACO 0.08 0.56 0.15 0 0.21 0.04 - [10] 0.08 0.55 0.13 0 0.20 0.04 -  2 ACO 0.05 0.45 0.36 0 0.07 0.02 - [10] 0.06 0.45 0.37 0 0.07 0.03 -  3 ACO 0.08 0.44 0.41 0.25 0.25 0.23 - [10] 0.08 0.45 0.42 0.26 0.26 0.23 -  4 ACO 0.10 0.47 0.20 0.09 0.17 0.22 0.14 [10] 0.09 0.46 0.18 0.08 0.15 0.23 0.14  5 ACO 0.10 0.45 0.31 0.21 0.09 0.13 0.02 [10] 0.09 0.44 0.31 0.21 0.08 0.12 0.01It is clear from Table6 that the proposed ACO finds schedules with less makespan than the presented method by [10] in cases 2 and 3. Moreover, in case 5, the results indicate that all surgeries have to be finished until the second working day. As it can be seen from Table 7, the ACO is competitive in terms of the values of the resources’ VCWT found, which indicates the proposed algorithm can produce a schedule with relative balanced resource utilization.


## 5. Conclusions

In this paper, the surgery scheduling problem with uncertain surgery durations is considered, where uncertainty in surgery durations is represented by means of fuzzy numbers. Furthermore, the problem is complicated by the need to account for the entire three steps (setup, surgery, and recovery) associated with a surgery, open scheduling strategy, as well as multiple resource constraints. The problem can be described as a multi-resource constrained fuzzy flexible job-shop scheduling problem. An ACO approach which utilized a two-level ant graph is developed to efficiently solve the problem. The two-level hierarchical ant graph contains both outer surgery graph and inner resource graph. The relative mechanisms of the proposed ACO, such as heuristic visibility, the pheromone updating rule, and the state transition rule, is also presented. The objective is minimizing the makespan of all surgeries by aiming at achieving suboptimal solutions.The five test cases in the literature are considered with different surgery problem sizes and available resources to evaluate the ACO algorithm. In addition, uncertainty was added to the durations of test cases to build fuzzy surgery durations. The computational results of the performance of the ACO on five test surgery cases, considering both deterministic and fuzzy surgery durations, were also presented. Concerning the deterministic surgery durations, the proposed method was compared with the reported results of an ant colony optimization approach in the literature. In this comparison, three performance measurements were evaluated: makespan, overtime, and the variation coefficient of working times. Experimental results indicate that the proposed algorithm is competitive in terms of the quality of the solutions found. As for future work, it may be interesting to add diversification in the local update rule and using local search in the ACO.



---

*Source: 8637598-2018-12-31.xml*