New heuristics for planning operating rooms

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es This is an Accepted Manuscript of an article published by Elsevier in Computers & Industrial Engineering , Vol. 90, on December 2015, available at: https://doi.org/10.1016/j.cie.2015.10.002 Copyright 2015 Elsevier. En idUS Licencia Creative Commons CC BY-NC-ND 1 New heuristics for planning operating rooms Jose M. Molina-Parientea*†, Erwin W. Hansb, Jose M. Framinana, Tomas Gomez-Ciac a Industrial Management, School of Engineering, University of Seville, Spain b Center for Healthcare Operations Improvement and Research (CHOIR), School of Management and Governance, University of Twente, The Netherlands c Head of Plastic Surgery and Major Burns Specialty, University Hospital Virgen del Rocio, Seville, Spain We tackle the operating room planning problem of the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain). The decision problem is to assign an intervention date and an operating room to a set of surgeries on the waiting list, minimizing access time for patients with diverse clinical priority values. This problem has been previously addressed in the literature considering different objective functions. The clinical priority depends on the surgery priority and the number of days spent on the waiting list. We propose a set of 83 heuristics (81 constructive heuristics, a composite heuristic, and a meta-heuristic) based on a new solution encoding, and we compare these methods against existing heuristics from the literature for solving operating room planning problems. The heuristics are adapted to the problem under consideration (i.e. considering all constraints and the new objective function), being re-implemented using the information provided by the authors. In total, after a calibration procedure, we compare 17 heuristics. The computational experiments show that our proposed meta-heuristic is the best for the problem under consideration. Finally, the proposed heuristics are tested using data from the Plastic Surgery and Major Burns Specialty. The results show significant improvements on several key performance indicators (number of scheduled surgeries, quality of surgical plan, resources utilization, etc.) when comparing with the actual results obtained by the specialty in the current practice. The aforementioned hospital is currently implementing the heuristic methods. Keywords: operations research in health services, operating room planning, surgery scheduling, heuristics, managerial implications * Preprint submitted to Computers & Industrial Engineering. https://doi.org/10.1016/j.cie.2015.10.002 † Corresponding author. Email: jmolina[email protected] 2 1 Introduction Nowadays health care organizations experience increasing pressure in order to provide their services at the lowest possible costs (Fei et al., 2010) as a response to the combination of restrictive budgets, increasing waiting lists, and the aging of the population (Roland et al., 2010). In this context, adequate decision-making in health care, particularly in the operating room (OR), which is the most budget-consuming facility (Macario et al., 1995), may greatly impact the quality and costs of healthcare provision. This study was motivated by the analysis of the operational decision level in the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain), in which surgery planning decisions are made without the support of any optimization based decision-support tool. We have observed that the current surgery assignment approach based on the decision maker’s experience leads to underperformance in terms of access time for patients, and inefficient OR utilization. The importance of providing the decision maker with decision models and heuristics to evaluate the impact of management strategies on management indicators (number of scheduled surgeries, quality of surgical plan, resources utilization, etc.), to reduce/remove surgery cancellations in different ways (expired or not performed surgical tests, no-shows on the day of the surgery, etc.), and to quickly perform what-if analyses over several possible scenarios is evident. The operational decision level consists of the off-line and the on-line levels (Hans et al., 2012). The off-line operational level is traditionally solved into two steps (Cardoen et al., 2010): the first step (called advance scheduling), involves the determination of the OR and the day in which each surgery will be performed, while in the second step (called allocation scheduling), a sequence of surgeries for each OR within each day in the planning horizon is obtained. The on-line operational level involves control mechanisms that dealing with monitoring the process and reacting to unforeseen or unanticipated events (Hans et al., 2012), such as the large discrepancies between the scheduled duration and the real duration of the surgeries (Min and Yih, 2010), and/or the availability of the resources reserved for uncertain arrivals (see e.g. Lamiri et al., 2009). The advance OR scheduling of surgeries on the offline operational decision level is a popular topic of research (see the literature reviews by Cardoen et al., 2010; Guerriero and Guido, 2011; May et al., 2011). In Table 1 we have classified the literature contributions on advance OR scheduling, and have indicated for all these contributions the type of surgical resources are taken into account, the block scheduling strategy, as well as the modeling approach, decision types, objective functions, and solution approach. The aforementioned approaches are not suitable for solving the advance OR scheduling problem in the Plastic Surgery and Major Burns Specialty under consideration, due to the following reasons: 3 (Dexter et al., 1999a) (Ozkarahan, 2000) (Guinet and Chaabane, 2003) (Ogulata and Erol, 2003) (Jebali et al., 2006) (Lamiri et al., 2007) (Fei et al., 2007) (Fei et al., 2008) (Hans et al., 2008) (Lamiri et al., 2008a) (Lamiri et al., 2008b) (Fei et al., 2009) (Lamiri et al., 2009) (Fei et al., 2010) (Min and Yih, 2010) (Liu et al., 2011) Block scheduling strategy Open ▪ ▪ ▪ ▪ ▪ ▪ ▪ Closed ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Decision model Deterministic ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Stochastic ▪ ▪ ▪ ▪ ▪ ▪ Constraints Time-period Release date ▪ ▪ ▪ ▪ ▪ ▪ ▪ Due date ▪ ▪ ▪ ▪ ▪ ▪ ▪ Facilities capacity OR ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ICU ▪ ▪ Personnel capacity Surgeon ▪ ▪ ▪ ▪ ▪ ▪ ▪ OR eligibility Patient ▪ ▪ ▪ ▪ Priority Patient ▪ Decision variables Patient Day ▪ ▪ ▪ Block ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Objective Function Utilization OR Under-utiliz. ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ Over-utiliz. ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ICU Over-utiliz. ▪ Costs Patient Surgery ▪ ▪ ▪ ▪ ▪ ▪ Leveling Surgeon Time ▪ Patient Day ▪ Type ▪ Eligibility Patient OR ▪ Priority Patient ▪ ▪ Solution Approach Exact ▪ ▪ ▪ Heuristics based on exact methods ▪ ▪ ▪ ▪ ▪ ▪ ▪ Constructive heuristics ▪ ▪ ▪ ▪ ▪ Improvement heuristics ▪ ▪ ▪ ▪ Metaheuristics ▪ ▪ Stochastic heuristics ▪ ▪ ▪ Table 1. An overview of the advance OR scheduling problem  Most references propose decision models to tackle the problem assuming that surgeons have no limits on the number of ORs where they could be assigned for performing surgeries on a given day. However, a maximum number of ORs is defined to each surgeon in the specialty depending on the surgeon’s specialty and the surgeon’s workload, trying to reduce the surgeon idle time and to avoid the overlapping of consecutive surgeries performed by the same surgeon.  Regarding the objective function, the Plastic Surgery and Major Burns Specialty considers an objective derived from the performance indicators employed by the Regional Healthcare System in Andalusia (Spain), and it is related to minimizing 4 patients’ access time, prioritizing who have higher clinical priority values. The access time of a patient is defined as the period of time between the surgical procedure is diagnosed (i.e. when the patient is included in the waiting list) and the execution date of the surgery. A clinical priority objective has only been only considered by Ozkarahan (2000) in a goal programming approach. The priority is determined in a straightforward way, being the rank of each surgery the ordinal ranking on the waiting list. In our case, we consider that the clinical priority is defined as a linear combination of the surgery’s urgency and the number of days spent on the waiting list at the time of planning, as occurred in practice at the specialty. This paper contributes twofold to improve quality of care and OR efficiency even further on the target surgical specialty. First, we propose a set of heuristics based on a new encoding scheme for solving real size instances in a reasonable time in order to reduce the negative effects of unforeseen events (rescheduling scheduled surgeries), and to allow the decision maker to quickly perform long-term what-if analyses for determining the best management strategy. We evaluate the performance of the most efficient proposed heuristics and existing heuristics from the literature for solving operating room planning problems, using a test bed we have developed based on the literature. The existing heuristics are adapted for solving the advance OR scheduling problem on the Plastic Surgery and Major Burns Specialty, being re-implemented using the information provided by the authors. In total we have compared 17 efficient methods (i.e. the best parameters of any method have been selected by a calibration procedure). Second, we aim to assess the impact of the best proposed method on the real life case of the Plastic Surgery and Major Burns Specialty. Quantitative results have been obtained comparing the impact on several key performance indicators, several objective functions, several resource management strategies and several planning horizons. The paper is organized as follows. In Section 2 we formally define the advance OR scheduling problem for the Plastic Surgery and Major Burns Specialty, and present an integer linear programming (ILP) decision model. Section 3 presents the heuristics for solving the problem in an approximate way. The generation of the test bed, the calibration of the heuristics and the computational results are presented in Section 4. Section 5 presents the managerial implications of implementing the proposed heuristics in the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain). Finally, in Section 6, we give our conclusions and outline directions for further work. 5 2 Problem description The Plastic Surgery and Major Burns Specialty performs around 3,000 surgeries per year, including emergency, deferred urgency, elective and ambulatory surgeries. More specifically, the specialty has 14 surgeons and 4 multifunctional ORs to perform deferred urgency, elective and ambulatory surgeries. Emergency surgeries do not fall within the scope of the paper, since these surgeries are performed using additional resources (called urgent surgical resources). Currently, on each day, 3 ORs are available for performing deferred urgency and elective surgeries from 8.30 a.m. to 3 p.m., and 1 OR is reserved for performing ambulatory surgeries from 3 p.m. to 8 p.m. On each day, each surgeon has a maximum available time for performing surgeries, being either 0 (not available for surgery) or 6.5 hours (i.e. they could perform surgeries from 8.30 to 3 p.m.). The number of ORs where a surgeon could be allocated (us) is limited in order to reduce surgeon idle time and overlapping of consecutive surgeries by the same surgeon. Finally, the remaining human and instrumental perioperative resources and recovery facilities are assumed to be available whenever needed, not representing bottlenecks for the problem under consideration. The modified block scheduling strategy is used by the decision maker to manage ORs. Burn surgeries (i.e. deferred urgency surgeries) have two reserved OR-days (i.e. a tuple of an OR and a day) every week because of their unpredictable arrivals and their high priority (they have to be operated as soon as possible), and because they can only be operated by only few surgeons. Most plastic surgeries can be performed in any available OR by any available surgeon, with the exception of microsurgeries which have two reserved OR-days every week because of the complexity, the special surgical equipment required, and the 10-hr estimated length of the surgery. At the consultation stage, each patient on the waiting list is assigned to a surgeon who is the responsible for performing the surgery. This assignment is made by the decision maker based on the surgeon’s specialty (i.e. types of surgery which could be performed by the surgeon), his/her skills and workload. The expected surgery duration is forecasted by the decision maker based on the historical data and the patient’s characteristics. Each surgery must be scheduled within a time period defined by its release and due dates. The release date defines the earliest date in which the patient could be operated (i.e. once all medical tests are completed). The due date (i.e. the latest date for performing the surgery) depends on the maximum time before treatment (in days) established by the patient`s urgency-related group, which are defined by National Healthcare Services based on a set of explicit clinical and social criteria. The maximum times considered in the Specialty are 45, 180 and 365 days. 6 Indices and Sets h ∈ H Set of time periods within the planning horizon for peri-operative resources i ∈ I Set of patients (surgeries) on the waiting list j ∈ J Set of operating rooms s ∈ S Set of surgeons Parameters r j h Regular capacity of OR j on day h (in minutes) a s h R egular capacity of surgeon s o n day h (in minutes) us Non-negative integer number of ORs in which surgeon s can perform surgeries within the same day γ i Surgeon in charge of patient i rd i Release da te for performing the surgery on patient i d i Due da te for performing the surgery on patient i δijh Binary parameter yielding 1 if surgery of patient i can be performed in OR j on day h ; 0 otherwise t i Expected time of surgery i (in minutes) wi Clinical weight of surgery i Variables Xijh 1 if patient i is to be operated in OR j on day h; 0 otherwise Z sj h 1 if surgeon s is allocated to OR j on day h ; 0 otherwise Table 2. Sets, data and variables used in the ILP decision model Finally, the objective function is derived from the performance indicators employed by the Regional Healthcare System in Andalusia (Spain), and it is related to minimizing access time for patients with higher clinical weight values. The clinical weight depends on a linear combination of the priority of the surgery (so a higher urgency of the surgery leads to a greater weight) and the number of days per patient spent on the waiting list at the time (patients with longer stays on the waiting list have higher weights and thus it aims to reduce access time). Below, we present the ILP model to solve the OR planning problem of the Plastic Surgery and Major Burns Specialty. Table 2 summarizes sets, data, and variables used in the decision model. 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 1 ℎ󰇭𝑤∙𝑋 ∈∈ 󰇮 ∈ Subject to: 𝑋≤1 (∀𝑖∈𝐼) (2) ∈∈ 𝑋=0 (∀𝑖∈𝐼) (3.1)  ∈ 7 𝑋=1 (∀𝑖∈𝐼|𝑑≤|𝐻|) (3.2) ∈  ∈ 𝑡𝑋≤𝑟 (∀𝑗∈𝐽,∀ℎ∈𝐻) (4) ∈ 𝑡𝑋≤𝑎 (∀𝑠∈𝑆,∀ℎ∈𝐻) (5) ∈  ∈ 𝑍≤𝑢 (∀𝑠∈𝑆,∀ℎ∈𝐻) (6) ∈ 𝑡𝑋≤𝑟𝑍 (∀𝑠∈𝑆,∀𝑗∈𝐽,∀ℎ∈𝐻) (7.1) ∈  𝑡𝑋 ≥𝑍 (∀𝑠∈𝑆,∀𝑗∈𝐽,∀ℎ∈𝐻) (7.2) ∈  𝑋=0 ∀𝑖∈𝐼,∀𝑗∈𝐽,∀ℎ∈𝐻|𝛿=0 (8) 𝑋∈{0,1} (∀𝑖∈𝐼,∀𝑗∈𝐽,∀ℎ∈𝐻) (9) 𝑍∈{0,1} (∀𝑠∈𝑆,∀𝑗∈𝐽,∀ℎ∈𝐻) (10) The objective function (1) maximizes the service level of a surgical specialty prioritizing patients with higher values of w. The service level of a planned surgery is defined as the quotient between the clinical weight and the planned date. Note that, if a surgery is not planned within the planning horizon (therefore its planned date is equal to 0), then the value of the service level is unbounded. In order to avoid such unbounded solutions, we introduce the parameter h in the objective function to capture the planned date. h represents the planned date for a scheduled surgery (at least one Xijh = 1), excluding unscheduled surgeries (all Xijh = 0). The example shown in Table 3 illustrates the calculation of the objective function. | I |=3, | H |= 2, | J |=1, | S |=1 Patient w Solution Objective Function value Xi11 Xi12 P 1 20 0 0 0     480300036012000 2 1 300136002000 1 1 P 2 36 0 0 1 P3 300 1 0 Table 3. Example to calculate the value of the objective function Constraints (2) enforce that each surgery is scheduled at most once during the planning horizon. The set of constraints (3.1) and (3.2) define the earliest and the latest date where a patient can be scheduled. Constraints (3.1) prohibit that the patient is scheduled 8 before the release date, while constraints (3.2) ensure that the surgery of a patient with a due date within the planning horizon must take place before his/her latest date. Constraints (4) prohibit that the total amount of OR time assigned to surgeons in an ORday is higher than its regular capacity. Constraints (5) prohibit that the total amount of time allocated to a surgeon is higher than his/her capacity in any day. Constraints (6) limit the number of OR-days that can be assigned to a surgeon in a day. The set of constraints (7.1) and (7.2) define whether a surgeon is allocated to an OR-day. Constraints (8) ensure that each surgery is carried out in a suitable OR-day. Finally, constraints (9)-(10) are binary constraints for decision variables. 3 Heuristics for the advance OR scheduling problem In this paper we propose a novel encoding scheme for solving the advance OR scheduling problem. A surgical plan is encoded into a permutation vector π and a bin packing (BP) operator, where π represents a certain order of the surgeries in the waiting list, and it is determined considering the prioritization of surgeries with due dates within the planning horizon. The BP operator is the algorithm used to allocate surgeries to ORdays, integrating the constraints (2)-(8) of the decision model. The following BP operators can be considered (see e.g. Dexter et al., 1999a; Dexter et al., 1999b):  Next Fit (NF): the surgery is planned in the last OR-day occupied, if possible. Otherwise, the surgery is planned into the next available OR-day.  First Fit (FF): the surgery is planned in the first OR-day where it fits.  Best Fit (BF): the surgery is planned in the OR-day that has the least amount of available time and it fits.  Level Fit (LF): the surgery is planned on the OR-day that has the most amount available time and it fits. The following sections present a set of constructive heuristics, a composite heuristic and a meta-heuristic for solving the proposed OR planning problem. 3.1 Constructive heuristics In the constructive heuristics, a permutation sequence π composed of an order of the patients in the waiting list is constructed in two stages which simultaneously take into account the fulfillment of time-period constraints (i.e. constrains 3.1 and 3.2) and the objective function.  In stage I, a partial sequence is determined by only sorting patients whose due date falls within the planning horizon in increasing order of due dates, in order to fulfill time-period constraints. 15  An adaptation of the Multi-start method proposed by Lamiri et al. (2009), referred to as MS. This method tries to avoid the problem of getting stuck in a local optimum (Lamiri et al., 2009). Let S be the initial solution at a given iteration, and R the solution provided by HS (the best improvement heuristic) starting from S. At the next iteration, a new initial solution S’ is determined from R by randomly modifying the planned time blocks of some patients. Each patient is selected with probability 1% according to Lamiri et al. (2009). If a patient is selected, a randomly feasible exchange with another patient is carried out (swapping ORdays). In order to compare among the other heuristics, the stopping criterion is modified by defining a computation time limit depending on the size of the instance.  An adaptation of the simulated annealing method of Lamiri et al. (2009), referred to as SA. The procedure to build a new solution at any iteration is applied a random exchange to the solution obtained at the previous iteration. The patient (pair-wise) or the pair of patients (triplet-wise) are randomly chosen, selecting the exchange which yields the largest improvement in any case. The cooling factor is set to 0.95 and the temperature is reduced after |I| iterations. These values result after a calibration procedure using the values proposed by Lamiri et al. (2009). As in MS, the stopping criterion is based on a computation time limit depending on the size of the instance. Finally, we propose the following simulated annealing method:  A simulated annealing method in which the temperature is considered as a constant parameter, referred to as SAC. The temperature is determined as in REI. θ and φ are set to {10%, 20%} and {1%, 5%, 10%} respectively, yielding 10% and 1% the best results. As in SA, the stopping criterion is based on a computation time limit. 16 Reference Testing Data |H| |J| |I|/β% |S|/α mds u Nº instances (Dexter et al., 1999a) Real 1 6, 22 - / 100% - - | J | 5000 (Fei et al., 2007) Ran. 5 NS 40,80,120,160 / - 8 / - - | J | 40 (Fei et al., 2008) Ran. 5 4 10,20,30,…,160 / - - - | J | 320 (Fei et al., 2009) Ran. 5 6 40,60,…,140,160 / - 8/1 * ,1.3 * 3,4,5 | J | 70 (Fei et al., 2010) Real 5 6 53, 101, 131 / - 13,27,31 - | J | 3 (Guinet and Chaabane, 2003) Ran. 5 1,2,3 10,15,20,…,80,85 / - - /1 * - | J | 608 (Hans et al., 2008) Real 1, 5 16 11380 / - - - | J | Variable (Jebali et al., 2006) Ran. 1 3 11,12,13,14,15 / - 4/1.1 * ,1.7 * - | J | 25 (Lamiri et al., 2007) Ran. 5 3,6 - / 75% 3 / - - | J | 40 (Lamiri et al., 2008b) Ran. 5 3,6,9,12 - / 75%, 100% 3 / - - | J | 320 (Lamiri et al., 2008a) Ran. 5 2 - / 100% - - | J | 1 (Lamiri et al., 2009) Ran. 5 4,8,12 - / 85%, 100% - - | J | 640 (Liu et al., 2011) Ran. 5 6 40,80,120,160 / - 8/1 * ,1.3 * - | J | 70 (Min and Yih, 2010) Real 5 10 203 / - 9 / - - | J | 1 (Ogulata and Erol, 2003) Real 5 2 24 / - 3 / - - | J | 1(100) (Ozkarahan, 2000) Real 10 7 400 / - 8 / - - | J | 1 Our contribution Ran. 5 3, 9 100%, 125% 1.5, 2 3,4 1, |J| 320, 960 Table 4. Factors considered in the literature in the design of a test bed 4 Test bed design In existing contributions for planning ORs, the main factors and the levels taken into account to build a test bed are (see Table 4):  |H|: number of days in the planning horizon.  |J|: number of ORs.  |I|: number of surgeries on the waiting list. Some papers propose to generate surgeries one by one until the sum of expected surgery durations for the generated surgeries exceeds a β% of the total OR time available in the whole planning horizon (see e.g. Dexter et al., 1999a; Lamiri et al., 2009). As shown in Table 4, β is set to 75%, 85% and 100%. |I| is also set according to the size of real waiting lists or arbitrarily proposed by authors. In this paper, we consider the levels of 100% and 125% for factor β. Although the latter value is not considered in the literature, we include it to consider scenarios where the total surgery time on the waiting list exceeds the total OR capacity. Currently, these scenarios are common due to restrictive budgets.  mds: maximum number of days per working week in which a surgeon is available to perform surgeries.  |S|: number of surgeons or surgical specialties. As shown in Table 4, |S| is set by real settings or arbitrarily proposed by authors. In our test bed, |S| is generated according to the following expression: 17 |𝑆|=𝛼∙∑ ∑ 𝑟∈∈ 𝑙∙𝑎∙𝑚𝑑𝑠 where l is the number of working weeks in the planning horizon, c is the maximum amount of time available for any surgeon during a day in the planning horizon, rjh is the regular capacity of OR-day (j, h) and, finally, α is the control factor to generate |S|. α is not specifically detailed in the literature, although it can be calculated according to the data provided by the authors (such cases are indicated with an asterisk in Table 4).  u: Non-negative integer number of different ORs in which surgeon s can perform surgeries within the same day. Table 5 shows the parameters and statistical distributions employed in the literature to generate the patient data required for the problem. In this paper, we consider that the surgery duration (t) (in minutes) follows a 2-parameter log-normal distribution (LN). The expected duration (µ) is randomly generated from the interval {60, 120, 180, 240} as in Marcon et al. (2003). The standard deviation (σ) is determined by using the coefficient of variation which is defined as the ratio of σ to µ. The coefficient of variation is randomly generated from interval [0.1µ…0.5µ]. Surgery duration t includes not only the time needed to perform the surgery, but also the set-up time, the clean-up time, and the preparation time for the next surgery. The due date for performing a surgery (d) (in days) is calculated by using the following expression 𝑑=𝑀𝑇𝐵𝑇− 𝑑𝑤𝑙. MTBT and dwl are the Maximum Time Before Treatment (in days) and the number of days on the waiting list respectively. MTBT depends on the patient`s Urgency-Related Group which are defined by National Healthcare Services based on a set of explicit clinical and social criteria (Valente et al., 2009). In this paper, MTBT is generated randomly from the set {45, 180, 360} as in the Spanish Healthcare Service. The number of days on the waiting list (dwl) is drawn from a discrete uniform distribution [1, MTBT–1] in order to avoid negative latest dates. The clinical weight (w) is obtained as a linear combination of the normalized values of the medical priority of the patient (mp) and the number of days of the patient on the waiting list, i.e. 𝑤=𝑎∙𝑚𝑝∗+(1−𝑎)∙ 𝑑𝑤𝑙∗. mp is generated from a discrete uniform distribution [1, 5], being 5 the highest priority. In order to normalize both measures, 𝑚𝑝∗=𝑚𝑝/5 and 𝑑𝑤𝑙∗=𝑑𝑤𝑙/𝑀𝑇𝐵𝑇. We also assume the same weight for both indicators, i.e. a = 0.5. The surgeon in charge (γ) of each surgery on the waiting list is defined as follows: for each iteration, surgeons are randomly sorted, assigning one surgery to each surgeon at random. The procedure finishes when all surgeries on the waiting list have been assigned to a surgeon. Finally, OR eligibility (δ) is generated according to a procedure used by a surgical specialty in a Spanish hospital in which there is a kind of surgeries that can be only performed in a specialized OR. In this case, the waiting list is composed of 90% of surgeries that can be planned into any OR (multifunctional or specialized), while the remaining surgeries have to be performed in a specialized OR. In that unit, 30% of ORs are specialized. 18 Reference t d w γ δ Dist. µ σ (Dexter et al., 1999a) LN 124.2 55.1 Real - Real Real (Fei et al., 2007) PIII [30,150] 80 10 U [1, 20] - NS - (Fei et al., 2008) U[15,480] 248 134 U [1, 20] - - - (Fei et al., 2009) PIII [40,150] 90 15 U [1, 20] - U[1, | S |] - (Fei et al., 2010) - Real - Real - Real - (Guinet and Chaabane, 2003) LN 120 60 LN [4,1] - NC NC (Hans et al., 2008) Multinomial Real Real - - - - (Jebali et al., 2006) LN [30,420] 180 60 NS - NS NS (Lamiri et al., 2007) LN U[60,180] R[0.1 µ …0.5 µ ] - - - Specialty (Lamiri et al., 2008b) U[30,180] 120 43 - - - Specialty (Lamiri et al., 2008a) U[30,180] 120 43 - - - - (Lamiri et al., 2009) U[30,180] 120 43 - - - - (Liu et al., 2011) PIII [40,150] 90 15 U [1, 20] - U[1, | S |] - (Marcon et al., 2003) N, LN R[60,70,80,…,180] R[0.1 µ …0.5 µ ] - - NS - (Min and Yih, 2010) LN Real Real - - - Specialty (Ogulata and Erol, 2003) - Real - - f( dwl , mp ) - - (Ozkarahan, 2000) - Real - - - Real Real Our contribution LN R[60,120,180,240] R[0.1µ…0.5µ] MTBT-dwl f(dwl, mp) U[1, |S|] Real Table 5. Patient parameters considered in the design of the test bed Regarding surgeon data, we construct a weekly schedule specifying which surgeons are available on each day. In order to avoid that an available OR is idle in a day, the following two-step procedure is used to generate a weekly schedule: In the first step, for each day, a number of surgeons equal to the number of available ORs is randomly assigned. In the second step, the difference between mds and the number of days obtained in the first step is assigned to each surgeon. The maximum time that a surgeon is available in a day to perform surgeries is fixed depending on the availability of each surgeon (see e.g. Marcon et al., 2003; Jebali et al., 2006; Fei et al., 2009). We consider that this time is equal to the regular capacity of an OR. Finally, the regular capacity depends on the type of ORs, although it is normally set to 8 hours (see e.g. Guinet and Chaabane, 2003; Jebali et al., 2006). In our case, we consider a regular capacity of 8 hours for all ORs in all days. Overtime capacity is not considered in this paper. 5 Computational experiments In this section we present extensive computational experiments using the ILP decision model, the proposed heuristics, and the adapted ones for solving the proposed advance OR scheduling problem. Note that the proposed mathematical model and the heuristics can be used to solve only the advance scheduling step (1< us ≤ |J|) or simultaneously both steps (us = 1). In order to evaluate the effectiveness of the algorithms, we have considered two response variables: feasibility of the constructed surgical plan, and Relative Percentage Deviation (RPD), according to the expression 𝑅𝑃𝐷= (𝐵𝑒𝑠𝑡−𝐻𝑒𝑢)/𝐵𝑒𝑠𝑡∙100, where Heusol is the solution given by any of the tested constructive heuristics and Bestsol is the best solution found so far (either the 19 optimum, or the best (highest) lower bound for a given generated instance). In our case, Bestsol has been obtained for each instance by solving the related ILP model using the commercial software Gurobi version 4.5.1 with a CPU time limit of 900 seconds. We generate a test bed according to the procedure described in Section 4, considering the 32 different combinations of |H|, |J|, β, mds, α and u shown in Table 4. For each combination, we have generated 30 instances, resulting in a total of 960 instances. The size of the waiting list depends on the tuple (|J|, β), being 50, 61, 146 and 182 the average number of surgeries for (3, 1.00), (3, 1.25), (9, 1.00) and (9, 1.25) respectively. The experiments were carried out on a PC with 2.80 GHz Intel Core i7-930 processor and 16 GBytes of RAM memory. The 960 instances are solved by the best proposed heuristics obtained in the calibration (ST(w, DEC, FF), MTALL, C6 and REI) (see Appendix A), and the best adapted algorithms. The results of the experiments for the advance scheduling (us = |J|) and for the integrated approach (us = 1) are shown in Figure 4. The mean RPD and computation time values are obtained by averaging these results only for feasible solutions obtained by the heuristics. The computation time limit for meta-heuristics is fixed to |I| ∙ |J| ∙ |H| ∙ η seconds for meta-heuristics. η is a time factor, which is set to 0.0125 and 0.025. The value leading to the best results for every meta-heuristic is η = 0.025, not being the difference big enough to consider a double computation time. Therefore, we only include the results for η = 0.0125. Note that the solutions obtained by the heuristics are compared to the solution obtained for each instance by solving the related ILP model using the commercial software Gurobi version 4.5.1. For each level of factor |J| (the most influential on the performance of the methods), Table 6 shows the minimum, the maximum and the average GAP (i.e. (𝐵𝑒𝑠𝑡− 𝑆𝑜𝑙𝑢𝑡𝑖𝑜𝑛)/𝐵𝑒𝑠𝑡∙100) for the advance scheduling problem and the integrated approach. In addition, the percentage of optimal solutions and the average CPU time values are presented. The analysis shows that DPH and MTALL are statistically the best constructive heuristics for the advance scheduling problem and the integrated approach respectively. However, we can conclude that the MTALL heuristic as the best constructive heuristic, because of the reduction on the feasible solutions obtained by DPH (only 79% of feasible solutions) and the larger computation time required. Regarding improvement heuristics, C6 is statistically the best algorithm for both planning problems (3.9% and 8.7% respectively), with not much more computation time required (16.15 and 22.89 seconds respectively). It is important to point out that C6 outperforms the adaptations of the existing meta-heuristics for the integrated approach. Regarding meta-heuristics, the results show that there are statistically significant differences between the REI algorithm and the remaining meta-heuristics for the advance scheduling problem and the integrated approach, yielding 1.7% and 7.8% of RPD values respectively. Finally, as described above, the number of ORs is the most influential factor on the performance of heuristics for off-line decision problems, especially for the integrated approach. 20 Figure 4. Feasibility, CPU time and RPD results for algorithms 21 Problem |J| Min. GAP (%) Max. GAP (%) Average GAP (%) Optimal solutions (%) CPU time (seconds) Advance Scheduling 3 0.00 1.18 0.17 57.0 473 9 0.23 0.72 0.72 0.0 900 Average 0.45 28.5 686.2 Integrated approach 3 0.00 1.52 0.17 65.7 437 9 1.22 4.87 3.10 0.0 900 Average 1.64 32.9 668.5 Table 6. ILP approach performance for solving the off-line decision level Table 7 show the minimum, the maximum, and the average RPD for the best heuristics in the manuscript (constructive, improvement and meta-heuristic), along with the percentage of solutions with RPD values less than 1% and the average CPU times. Finally, Figure 5 shows the average RPD values of the proposed heuristics to solve the off-line decision problems for each level of |J|. 6 Managerial implications In this section we evaluate the implementation of the proposed heuristics for the Plastic Surgery and Major Burns Specialty of the University Hospital “Virgen del Rocio” in Seville (Spain). To analyze the benefits of the deployment, we have generated an extensive test bed (100 instances) based on meetings with the decision maker, data provided by the annual management report and historical data from the Specialty. Each instance contains an initial waiting list along with the patient arrivals for each week of the year (i.e. 52 weeks). Surgery parameters are generated by empirical statistical distributions. The number of surgeries performed by the Specialty during 2012 was 2,823. Using the same surgical resources (ORs and surgeons) and the same initial waiting list, the best approximate method (i.e. the REI method) is able to plan 2,962 surgeries, which means an average increase of 2.67 surgeries per week. In addition, it also has to be noted that the time that the decision maker devotes to planning surgeries is greatly reduced by the use of this method. With the help of heuristics, the decision maker can evaluate different planning objectives using several planning horizons under several guidelines (patient prioritization, waiting list reduction, etc.). Besides analyzing the service level (O1) under the modified block scheduling strategy, the following objectives have been considered: number of scheduled surgeries maximization (O2), ORs utilization maximization (O3), and a weighted objective that maximizes the service level during the first 6 months and the number of scheduled surgeries during the second 6 months (O4) using different planning horizons of a week, a two-week, and four-week. 22 Problem |J| Heuristic Min. RPD (%) Max. RPD (%) Average RPD (%) Solutions RPD <1% (%) CPU time (seconds) Advance Scheduling 3 MT ALL 2.59 17.54 9.75 0 0.02 C 6 0.20 12.00 3.60 1.7 0.51 REI 0.00 4.65 0.82 70 10.31 9 MT ALL 5.34 16.67 10.35 0 0.30 C 6 1.19 9.97 4.22 0 31.8 REI 0.47 6.63 2.55 2.9 92.12 Integrated approach 3 MT ALL 9.40 27.54 17.80 0 0.02 C 6 1.13 16.34 7.15 0 0.58 REI 0.00 7.28 2.64 14.6 10.27 9 MT ALL 17.86 30.04 24.14 0 0.35 C 6 5.28 23.76 10.35 0 45.21 REI 4.93 24.96 13.00 0 92.21 Table 7. Heuristic performance for solving the off-line decision level Figure 5. Influence of the number of ORs on the off-line decision problems 23 Objective Function Planning horizon Service Level Scheduled surgeries OR utilization Waiting list CPU time (sec.) O1 Weekly 1322.0 2970 ( 2.83 ) 89 % 666 ( 29.1 %) 159.1 Two - weekly 1641.0 2962 ( 2.67 ) 89 % 674 ( 30.7 %) 243.5 Four - weekly 1816.3 2943 ( 2.31 ) 89 % 693 ( 34.2 %) 399.0 O2 Weekly 1298.3 3151 ( 6.30 ) 88 % 485 ( - 6.0 %) 122.2 Two - weekly 1586.9 3138 ( 6.06 ) 88 % 498 ( - 3.5 %) 184.5 Four - weekly 1960.6 3097 ( 5.27 ) 87 % 539 ( 4.4 %) 313.5 O3 Weekly 1220.0 2857 ( 0.65 ) 91 % 780 ( 51.1 %) 188.7 Two - weekly 1464.7 2821 ( - 0.04 ) 91 % 816 ( 58.0 %) 296.6 Four - weekly 1720.9 2836 ( 0.25 ) 91 % 800 ( 55.1 %) 467.5 O4 Weekly 1250.6 3143 ( 6.15 ) 88 % 493 ( - 4.5 %) 134.9 Two - weekly 1522.9 3134 ( 5.98 ) 88 % 502 ( - 2.7 %) 207.7 Four - weekly 1725.4 3100 ( 5.33 ) 88 % 536 ( 3.8 %) 348.7 Table 8. Analysis of the objectives and horizons under the modified block scheduling strategy In Table 8, the average annual values for each objective and planning horizon are shown, taking into account the average values of service level, the number of planned surgeries (increase in number of patients with respect to the effectively intervened is shown in brackets), ORs utilization, and number of patients on the waiting list at the end of the year (within brackets, the difference with respect to the size of the waiting list at the beginning of the year). The results show that the selection of the planning horizon greatly depends on the indicator selected by the decision maker. More specifically, the four-week horizon seems the best one regarding the service level, as there are a larger number of high-priority surgeries that can be planned as compared to shorter horizons. With respect to the number of scheduled surgeries, the best horizon is a week, as in this case there are lesser surgeries on the waiting list whose due date is within the planning horizon and therefore there is more flexibility to build the plan. Finally, the planning horizon does not seem to be a significant factor when the objective involves OR utilization. With respect to the time required to generate the surgical plans, it has to be noted that the maximum average time for the evaluation of a scenario is 467.5 seconds. The proposed heuristics can also be employed to assess the impact of the different strategies to manage the resources. Table 9 shows the results assuming an open scheduling strategy, releasing ORs reserved to burn surgeries. In general, there are substantial improvements for all objectives and planning horizons. Regarding the service level, a maximum improvement of 7.71% is achieved (over the value obtained assuming the modified block scheduling strategy). Again, a four-week planning horizon seems to offer the best results. The number of planned surgeries increases from 6.30 to 9.65 patients per week, which translates into a 39.8% reduction of the waiting list at the end of the year. Finally, ORs utilization increases a 6% average for all objectives and planning horizons under consideration. 24 Objective Function Planning horizon Service level Scheduled surgeries OR utilization Waiting list CPU time (sec.) O1 Weekly 1348.1 3151 ( 6.30 ) 95% 485 ( - 6.1 %) 124.4 Two - weekly 1681.6 3143 ( 6.15 ) 95% 493 ( - 4.5 %) 191.5 Four - weekly 1956.0 3129 ( 5.88 ) 95% 507 ( - 1.7 %) 311.2 O2 Weekly 1297.8 3325 ( 9.65 ) 93% 311 ( - 39.8 %) 108.1 Two - weekly 1584.3 3317 ( 9.5 ) 93% 319 ( - 38.1 %) 139.9 Four - weekly 1963.7 3256 ( 8.33 ) 92% 380 ( - 26.4 %) 243.1 O3 Weekly 1260.8 3050 ( 4.36 ) 98% 587 ( 13.7 %) 147.8 Two - weekly 1454.2 3132 ( 5.94 ) 98% 504 ( - 2.3% ) 198.8 Four - weekly 1691.8 3084 ( 5.02 ) 97% 552 ( 6.9 %) 358.8 O4 Weekly 1252.2 3319 ( 9.54 ) 94% 317 ( - 38.5 %) 107.2 Two - weekly 1515.8 3310 ( 9.36 ) 94% 326 ( - 36.9 %) 162.5 Four - weekly 1770.58 3263 ( 8.46 ) 94% 373 ( - 27.8 %) 273.5 Table 9. Analysis of the objectives and horizons under the open scheduling strategy Figure 6. Plot of the evolution of the scheduled surgeries based on the objectives O1 and O2