Free
Education  |   November 1999
Which Algorithm for Scheduling Add-on Elective Cases Maximizes Operating Room Utilization?  : Use of Bin Packing Algorithms and Fuzzy Constraints in Operating Room Management
Author Affiliations & Notes
  • Franklin Dexter, M.D., Ph.D.
    *
  • Alex Macario, M.D., M.B.A.
  • Rodney D. Traub, Ph.D.
  • *Associate Professor, Department of Anesthesia, University of Iowa, Iowa City, Iowa. †Assistant Professor of Anesthesia & Health Policy and Research, Department of Anesthesia, Stanford University, Stanford, California. ‡Assistant Professor, Department of Management Sciences, University of Iowa, Iowa City, Iowa.
  • Dennis M. Fisher, M.D., was Acting Editor-in-Chief for this article.
Article Information
Education
Education   |   November 1999
Which Algorithm for Scheduling Add-on Elective Cases Maximizes Operating Room Utilization?  : Use of Bin Packing Algorithms and Fuzzy Constraints in Operating Room Management
Anesthesiology 11 1999, Vol.91, 1491. doi:
Anesthesiology 11 1999, Vol.91, 1491. doi:
A PRODUCTIVE surgical suite includes elements such as low cancellation rates, minimal overtime personnel costs, and high utilization. Utilization equals the time that an operating room (OR) is used, including setup and cleanup, divided by the length of time an OR is available and staffed. To maximize utilization, elective cases are scheduled to be completed during regularly scheduled hours (e.g.  , Monday through Friday from 7 A.M. to 3 P.M.). Elective cases (which we define as those for which the patient can wait for surgery for at least 3 days, e.g.  , Friday to Monday) can be scheduled by surgeons until a specified cutoff time (e.g.  , 10 A.M. the working day before surgery). At that predetermined cutoff time, cases are assigned to ORs and given predicted start times. After the cutoff time, surgeons can submit additional add-on elective cases to be scheduled into the remaining open OR time. To maximize OR utilization, as many hours of the submitted add-on elective cases are scheduled as possible into the open OR time.
Several algorithms can be used to determine how to schedule add-on elective cases into the remaining open OR time. Surgical suites commonly schedule add-on elective cases on a first-come, first-served basis. Algorithms that schedule each case as soon as the case is submitted are referred to as “on-line” algorithms. 1,2 Alternatively, all of the requests for add-on elective cases may be batched together or saved until a set time (e.g.  , 4 P.M. the day before surgery). Only then are the cases considered and assigned simultaneously to ORs in the surgical suite. Algorithms using this strategy are referred to as “off-line” algorithms. 1,2 
The algorithm for scheduling add-on elective cases that maximizes OR utilization is unknown. Because salaries of OR staff account for the majority of OR costs, 3 it is important to match optimally add-on elective cases to when there are OR staff scheduled to work (i.e.  , to maximize OR utilization). The goal of this study was to use computer simulation to evaluate statistically several scheduling algorithms described in the management sciences literature in terms of their relative performance at scheduling as many hours of add-on elective cases as possible into open OR time.
Methods 
Review of the Algorithms To Schedule Add-on Elective Cases 
Ten different algorithms to schedule add-on elective cases into ORs were considered (table 1). 1. These algorithms, taken from the management sciences or operations research literature, are appropriate for the “variable-sized bin packing problem with bounded space.”1,2 The process of scheduling a patient for surgery in an OR is equivalent mathematically to packing an item into a bin. Because each OR contains one or more previously scheduled elective cases, the open time available in each OR for add-on elective cases differs among ORs. This is why the bins are considered to be “variable-sized.” The number of ORs available for add-on elective cases is fixed, providing for the phrase “bounded space.”
Table 1. Features of the 10 Algorithms Considered in the Study 
Image not available
Table 1. Features of the 10 Algorithms Considered in the Study 
×
On-line Algorithms. 
On-line algorithms consider each case in the order in which cases are submitted. 1,2 We evaluated the effect on OR utilization of the following four on-line algorithms (table 1):
  • Algorithm #1:Best Fit.  Each case is assigned to the OR that (1) has sufficient additional time available for the new case and (2) has the least amount of additional time available. This algorithm was used as the standard against which the other algorithms were compared.
  • Algorithm #2:Worst Fit.  Each case is assigned to the OR that (1) has sufficient additional time available for the new case and (2) has the longest amount of additional time available.
  • Algorithm #3:Best Fit with fuzzy constraints.  Same as algorithm #1 with the addition of fuzzy constraints (described below).
  • Algorithm #4:Worst Fit with fuzzy constraints.  Same as algorithm #2 with the addition of fuzzy constraints.
Off-line Algorithms. 
Off-line algorithms, 1,2 in which cases are batched before being scheduled, use a specified cutoff time for the submission of add-on elective cases (e.g.  , 4 P.M. the day before surgery). Because off-line algorithms batch cases together and schedule add-on elective cases into ORs simultaneously, they are known generally to be able to schedule more total hours of add-on elective cases than the on-line algorithms. 1,2 We evaluated the effect on OR utilization of the following five off-line algorithms (table 1):
  • Algorithm #5: Best Fit Descending. Add-on elective cases are sorted based on scheduled duration from longest to shortest. Cases are considered in this descending order, such that the longest add-on case is assigned to an OR first. 4 Best Fit is applied to determine to which OR each case is assigned.
  • Algorithm #6: Worst Fit Descending. Cases are sorted based on scheduled duration from longest to shortest. Cases are considered in this descending order. Worst Fit is then applied.
The algorithms used commonly for off-line bin packing are Best Fit Descending (algorithm #5) and Worst Fit Descending (algorithm #6). Both algorithms schedule long add-on cases while there are still ORs with long periods of open OR time. 4 
  • Algorithm #7: Best Fit Descending with fuzzy constraints. Same as algorithm #5 with the addition of fuzzy constraints.
  • Algorithm #8: Worst Fit Descending with fuzzy constraints. Same as algorithm #6 with the addition of fuzzy constraints.
  • Algorithm #9: Worst Fit Ascending. Cases are sorted based on scheduled duration from shortest to longest. Cases are considered in this ascending order. Worst Fit is applied.
We included Worst Fit Ascending (algorithm #9) to represent a clerk who is handed a stack of requests for add-on elective cases. In this situation, the clerk may use a scheduling algorithm that does not require computation (i.e.  , assigns short cases to ORs with lots of time). Worst Fit Ascending is known to perform relatively poorly at maximizing OR utilization 2 and as such serves as a positive control.
Fuzzy Constraints. 
Fuzzy constraints were included in algorithms #3, #4, #7, #8, and #10 (below). Best Fit, Worst Fit, Best Fit Descending, Worst Fit Descending, and Worst Fit Ascending schedule cases into ORs provided that the cases can be completed within the open OR time. However, this fixed criterion may not be what is truly desired. For example, an OR manager may want to schedule a 5-h add-on case, although the longest time available in any of the ORs is 4 h and 55 min. It may be desirable to assign the case to the OR even though the total duration of cases in that OR is expected to exceed the preset time limit. To allow for such flexibility, fuzzy constraints were used in the following manner. Cases were considered in the order specified by the algorithm. If no OR had sufficient open time available for the case, but sufficient open time was available in the OR with the most remaining time provided the scheduled duration of the case was shortened by ≤ 15 min, then the case was assigned to the OR with the most remaining time.
Algorithm #10: Hybrid Algorithm. 
We also considered a hybrid algorithm that we created to have advantages of both on-line and off-line algorithms. Algorithm #10 requires determination at the time that each case is submitted whether there are restrictions preventing assignment of a case into an OR. As each new add-on case is submitted for consideration, all add-on cases that have previously been assigned to a specific OR and the new case are reassigned using Best Fit Descending with fuzzy constraints (algorithm #7). If all add-on cases that have previously been assigned to an OR and the new case cannot be scheduled, then the new case is not scheduled. The surgeon is informed that the case will not be performed in the surgical suite that day unless there is a cancellation (i.e.  , an increase in the open hours in the surgical suite). If all add-on cases that have previously been assigned to an OR and the new case can be scheduled, then the case being considered is added to the array of “add-on cases that have previously been assigned to an OR.” The surgeon and patient are informed that the case has been added to the elective schedule. However, neither an OR nor a time assignment is given to the surgeon or patient. Then, the process is repeated for subsequent submitted cases. At the specified cutoff time for the submission of add-on elective cases, surgeons and patients are given OR and time assignments from the most recent schedule developed for the array of add-on cases.
Overview of Our Computer Simulation Study Comparing the Relative Performance of the Algorithms at Maximizing OR Utilization 
To compare which of the 10 algorithms yields the highest OR utilization, a computer model of OR scheduling of add-on elective cases was created. First, actual data were collected from two surgical suites to get probability distributions used in the simulations. These data were:(1) number of hours of open time available for add-on cases in each OR in the surgical suite each day and (2) duration of each elective add-on case. Second, these two sets of measured time data were summarized by fitting probability distributions appropriate for the data. Third, the probability distributions were used in computer simulations to compare the performances of the different scheduling algorithms. Best Fit (algorithm #1) was used as the standard to which the other algorithms were compared. The relative performance of each algorithm was summarized using OR utilization.
Collection of Empirical Data Used To Generate the Probability Distributions Required To Perform the Computer Simulations 
The time data were obtained from each of two different surgical suites: the University of Iowa's tertiary surgical suite (11,600 cases per year during regularly scheduled hours in 22 ORs) and the University of Iowa's Ambulatory Surgery Center (4,800 cases per year in six ORs). The Ambulatory Surgery Center includes routine, elective, outpatient cases. Cases in the two surgical suites were scheduled independently. Our testing of the algorithms using computer simulation was performed separately for these two surgical suites.
The “open OR time,” or staffed OR time remaining after regularly scheduled elective cases had been scheduled, was obtained for all working days between April 1, 1998, and June 30, 1998. For the tertiary surgical suite, there were 1,183 combinations of OR and days from which to measure the remaining open OR time (e.g.  , one combination might be 2 h remaining in OR #9 on June 26). For the Ambulatory Surgery Center, there were 218 combinations of OR and days. To use these data (the time remaining in hours in each OR in a surgical suite) in the computer modeling, an empirical probability distribution 5 was generated for each surgical suite (ExpertFit; Averill M. Law & Associates, Tucson, AZ).
The actual (i.e.  , not scheduled) duration of each add-on elective case performed between July 1, 1997, and June 30, 1998, was obtained. There were 751 of these add-on elective cases performed in the tertiary surgical suite and 258 in the Ambulatory Surgery Center. The duration of each add-on case was considered to equal the time from when the preceding patient exited the OR until the patient undergoing the add-on elective case exited the OR. If the turnover time exceeded 1 h, a turnover time of 1 h was used. Otherwise, interpreting the time between two cases without a maximum value would exaggerate the time actually used to perform the needed cleanup and setup between the two cases. The probability distributions for the case durations (again, including the preceding turnover time) were log normal 5 (ExpertFit).
Use of Probability Distributions in Computer Simulations To Compare Performances of the Scheduling Algorithms at Maximizing OR Utilization 
The probability distributions previously described were used in computer simulations to generate hypothetical values for the number of hours of open OR time and the duration of each elective add-on case. With this step, the computer analyses scheduled cases using each of the 10 algorithms to determine which algorithm yielded the highest OR utilization.
We wrote the computer code (Microsoft Excel 97 Visual Basic; Microsoft Corp., Redmond, WA) such that the computerized statistical data analysis 2proceeded in the following stepwise manner for each surgical suite (figs. 1 and 2):
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
×
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
×
  1. A hypothetical surgical suite began each day with no add-on cases scheduled in any of the ORs. The time remaining in each of the ORs in the suite was sampled from the empirical probability distribution. 5 The total time remaining in all of the ORs was then calculated and termed “total available time.”

  2. Add-on elective cases with their concomitant turnover times were generated until the sum of the durations of the “submitted” add-on elective cases exceeded the total available time. The duration of each case was sampled from the log-normal distribution. 5 

  3. The add-on elective cases from step #2 were scheduled using one of the algorithms studied. The total hours of add-on elective cases scheduled during the regularly scheduled hours was then calculated and expressed as a percentage of the total hours available for cases during regular hours. The algorithms that use fuzzy constraints permit cases to be assigned to an OR provided that the case does not have a duration > 15 min longer than the open OR time. Only the hours of cases scheduled to be completed during regularly scheduled hours were considered when calculating the total hours of add-on elective cases.

  4. Steps #1 to #3 were repeated to represent a total of 5,000 days of elective surgery. The output from each set of 5,000 simulated days was the OR utilization, calculated using the total hours of regularly scheduled and add-on elective cases, including turnover times. 3We report the results of the analysis as the mean difference in performance (OR utilization) achieved by each algorithm as compared with Best Fit, a commonly used algorithm (P  value by paired two-sided Student t  test).

We used a total of 5,000 simulated days for each of the algorithms below because this number of trials was sufficient for the SEs of the calculated means to be < 0.1% for all comparisons.
Sensitivity Analyses 
Because computer simulation was used to describe the scheduling of add-on cases using different algorithms, the analysis could be run multiple times to explore sensitivity effects (i.e.  , parameters were varied to determine their impact on OR utilization).
Sensitivity Test A. 
Some surgical services information systems schedule cases in increments of 15 min (e.g.  , the second case of the day in an OR would start at 9:15 A.M., not at 9:12 A.M.). Therefore, steps #1 and #2 were modified by rounding available times in the ORs and durations of the add-on cases to the nearest 15 min.
Sensitivity Test B. 
At some surgical suites, the number of submitted add-on elective cases may be large relative to the total number of hours of open OR time. The off-line (“batching”) algorithms would then be expected to perform particularly well at maximizing OR utilization relative to the on-line algorithms, because off-line algorithms consider the cases simultaneously and thus can evaluate the additional cases for a good match between each case's duration and the open time in each OR. Step #2 was modified by generating add-on elective cases with their concomitant turnover times until the sum of the durations of the “submitted” add-on elective cases exceeded twice the total available time fromstep #1.
Sensitivity Test C. 
Some add-on cases may not be performed in some ORs because the personnel already assigned to each OR may not have the necessary experience to perform the case. Such restrictions were modeled by eliminating the first choice of the scheduling algorithm and scheduling each case into the OR that was the second choice.
Results 
Analysis of Empirical Data from OR Databases To Generate the Necessary Statistical Distributions To Perform the Computer Simulations 
Tertiary Surgical Suite with 22 ORs. 
At the 10 A.M. cutoff time the working day before surgery, there were 1.26 ± 1.60 h (mean ± SD) of time remaining in each OR per day. No open time was available to schedule add-on elective cases in 42% of the ORs. The duration of add-on elective cases, including their turnover times, was 3.35 ± 1.74 h.
Ambulatory Surgery Center with Six ORs. 
At the 10 A.M. cutoff time the working day before surgery, there were 0.98 ± 1.23 h of remaining time in each OR per day. There was no open time available to schedule add-on cases in 45% of the ORs. The duration of add-on elective cases, including their turnover times, was 2.06 ± 0.91 h.
Computer Simulation of OR Utilization Using the Best Fit Algorithm (Standard to Which the Other Algorithms Were Compared) 
The simulated OR utilization before scheduling add-on elective cases was 84% for the tertiary surgical suite and 85% for the Ambulatory Surgery Center. Using Best Fit (algorithm #1) to schedule add-on elective cases into ORs, OR utilization was 92.7% for the tertiary surgical suite and 92.5% for the Ambulatory Surgery Center (table 2, columns 1 and 2). The simulations scheduled 0.24 ± 0.11 cases each day into each OR of the 22-room tertiary surgical suite. There were 0.28 ± 0.23 cases scheduled each day into each OR of the six-room Ambulatory Surgery Center.
Table 2. Differences among Algorithms in Operating Room Utilization (%) 
Image not available
Table 2. Differences among Algorithms in Operating Room Utilization (%) 
×
Computer Simulation Results To Determine Which Algorithm Yields the Highest OR Utilization 
Operating room utilization was affected by the algorithm chosen to schedule add-on elective cases (table 2). All mean differences were significantly different from 0% at P  < 0.05.
Surgical suite utilization rates were highest with Best Fit Descending with fuzzy constraints (algorithm #7;table 2). For the tertiary surgical suite, the difference between this algorithm's OR utilization and the OR utilization achieved by the algorithm with the lowest OR utilization (Worst Fit Ascending, algorithm #9) was 4.1%.
The increases in OR utilization achieved by using both fuzzy constraints and off-line algorithms relative to using Best Fit were greater than the sums of the increases in OR utilization achieved by using fuzzy constraints or off-line algorithms (table 2). The hybrid algorithm (algorithm #10) had an intermediate effect on OR utilization (table 2, rows 3, 7, and 10).
Sensitivity Analyses 
Sensitivity Analysis A. 
Rounding case durations to the nearest 15 min affected differences among algorithms in OR utilization by < 0.2%.
Sensitivity Analysis B. 
The increase in OR utilization achieved by using the algorithm with the highest utilization (Best Fit Descending with fuzzy constraints, algorithm #7)versus  lowest utilization (Worst Fit Ascending) was larger when there was twice as many hours of add-on cases submitted than could be scheduled (table 2).
Sensitivity Analysis C. 
Restrictions into which OR a case can be assigned had essentially no impact on OR utilization achieved by the off-line algorithms (table 2, rows 11 and 12).
Discussion 
Application of Our Results to Other Surgical Suites (Study Limitations) 
We used computer simulation as an analytical tool to understand better how an intervention (such as using different algorithms for deciding in which OR to assign an add on case) is likely to impact OR utilization. We identified the algorithm, Best Fit Descending with fuzzy constraints, for scheduling add-on cases that is most likely to maximize OR utilization. Our results suggest that, to optimize OR utilization, add-on cases should be considered simultaneously at a cutoff time (e.g.  , 4 P.M. the day before surgery) and then scheduled based on scheduled duration from longest to shortest. If no OR has sufficient open time available for an add-on case, but sufficient open time is available in the OR with the most remaining time provided the scheduled duration of the case is shortened by ≤ 15 min, then the case should be scheduled into the OR with the most remaining time. Although this approach may be best to maximize OR productivity, our results may not apply to surgical suites in which maximizing OR utilization is secondary to demands by other stakeholders in the OR, such as surgeons and patients.
Our results are subject to the condition that the surgical suite usually has sufficient additional time in each OR to schedule either zero or one add-on elective case. If only  zero or one add-on elective case could be scheduled into each OR, then Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Descending with fuzzy constraints (algorithm #8) would produce identical and maximal OR utilization. Best Fit Descending with fuzzy constraints performed slightly better than Worst Fit Descending with fuzzy constraints because occasionally more than one add-on elective case was performed in an OR. When scheduling longer cases, Best Fit Descending left open some OR time in which a second short case considered later could fit. The limitation that our results only apply when each OR usually has zero or one add-on elective cases is unlikely to limit the usefulness of our results because the mean number of cases per OR per day in the United States is 2.0. 6 
There are two other implications of the limitation of our results to surgical suites that have a few add-on elective cases per OR per day. First, almost all add-on elective cases were scheduled into ORs with sufficient open time for only one add-on elective case. As a result, scheduling all of the add-on elective cases at a predetermined cutoff time (off-line) worked particularly well compared with algorithms that scheduled cases as they were submitted (on-line). Second, with many surgeons and only a few add-on elective cases each day, the probability of a surgeon scheduling more than one add-on elective case each day is small. This permits the assumption 4that each add-on case is scheduled by a different surgeon and thus can be scheduled independently of other add-on cases.
The utilization for elective cases excluding add-on elective cases equaled approximately 85% in the tertiary surgical suite and Ambulatory Surgery Center. If the surgical suite utilization had been higher, fewer hours would have been available for add-on elective cases, and the mean number of add-on cases per OR per day would have been even < 0.24–0.28, respectively. Then, the differences in utilization among scheduling algorithms would have been less than we observed. Our results are of limited relevance to surgical suites with a utilization approaching 100%; such surgical suites would not require an algorithm to schedule add-on elective cases because no such cases would be scheduled. In contrast, surgical suites with large day-to-day variability in the number of hours of submitted elective cases will have a lower utilization rate. For such surgical suites, the use of scheduling algorithms for add-on elective cases may be particularly beneficial.
Our results are relevant economically to surgical suites that schedule add-on elective cases into open OR time provided the cases are scheduled to be completed during regularly scheduled hours. Such surgical suites share two common features. First, labor costs are higher when cases are routinely completed after regularly scheduled hours. For example, staff may be full-time hourly employees who work 40 h per week during regularly scheduled OR hours, and thus receive overtime at 1.5 times the regular wage for working after regularly scheduled hours. Alternatively, staff may be salaried employees who frequently quit, citing long working hours. Second, add-on elective cases that cannot be scheduled to be completed during regularly scheduled hours are not performed in the surgical suite that day. For example, the surgical suite may have a fixed budget (staffed hours of OR time) for elective cases, regardless of how many elective cases are submitted by the surgeons. Alternatively, the surgical suite may only schedule an elective case outside of regularly scheduled OR hours if there is insufficient open OR time for the case during a time period of many work days (e.g.  , 4 weeks).
Economic Implications 
We found that the algorithm with the best expected performance (Best Fit Descending with fuzzy constraints) is predicted to increase utilization of the surgical suite by approximately 4% over the worst-performing algorithm. Although this increase may seem small, it can translate into important increases in revenue for a surgical suite with a fixed staff budget for elective cases. This optimal algorithm, whether implemented manually by a scheduler or programmed into an OR scheduling system, can increase OR revenue without increasing the number of staffed OR hours. For a surgical suite such as the tertiary surgical suite with 22 ORs, an 8-h regularly scheduled work day, and a mean case duration of 3.35 h, a difference of 4.2% in utilization corresponds approximately to an additional 7.4 h of cases per day (22 × 8 × 0.042) or 2.2 cases per day (7.4 ÷ 3.35). If OR time is charged at $13/min, anesthesia time is charged at $45 an American Society of Anesthesiologists relative value scale unit, and reimbursement is 50% of charges, then the surgical suite gains $877,344 per year:(7.4 h/day)×(247 elective OR days/yr)×(60 min/h)×[$13/min for OR time +($45 per unit ÷ 15 min per unit)]× 50% reimbursement. The financial benefit would be larger if more hours of add-on elective cases were submitted (sensitivity analysis B).
Our analysis is appropriate for surgical suites with at least some staff who are full-time employees without overtime. If overtime is frequent because of the time to complete elective cases, then the surgical suite has chosen to schedule elective cases outside of regularly scheduled hours. For example, in some communities competition among surgeons and surgical suites for patients may be sufficiently intense that a surgical suite wanting to perform a case must provide staffing for the case within a work day. In this setting, the goal of a scheduling algorithm for add-on elective cases is to schedule the cases to minimize the total number of overtime hours. The scheduling algorithm to achieve this objective was analyzed previously. 7 
Issues in Implementing the Algorithms 
Implementation of off-line (batching) algorithms such as Best Fit Descending requires that add-on elective cases be considered simultaneously at a specified cutoff time for the submission of such cases. Generally, this restriction will be practical because the information system or OR manager doing the scheduling at the cutoff time is likely to know about most restrictions, limiting into which OR a case can be scheduled. In contrast, off-line algorithms may not be practical at some surgical suites because surgeons or patients may not accept having to wait until the cutoff time to learn whether they will have surgical time for a case. At such surgical suites, the hybrid method may be acceptable and may provide better performance than on-line algorithms.
The defining characteristic of on-line algorithms is that the patient and surgeon can be told immediately whether the case has been scheduled into an OR and, if so, to what OR the case has been assigned and with what expected start time. Implementation of an on-line algorithm requires that either the computer or scheduler using the algorithm can determine at the time that each case is submitted whether there are restrictions preventing assignment of a case into one or more ORs. For example, the equipment required for the case may not be able to fit in one of the ORs. If an on-line algorithm is to be used, higher utilization can be achieved by using Best Fit rather than Worst Fit.
None of the algorithms that we considered needs to be implemented using an OR information system. Because almost all add-on elective cases are scheduled into ORs with sufficient open time for only one add-on elective case, implementation of the algorithms is straightforward and can be performed manually, especially at surgical suites with few numbers of ORs.
Operating room managers who implement Best Fit Descending, with (algorithm #7) or without (algorithm #5) fuzzy constraints, for scheduling add-on elective cases using an OR information system may achieve a secondary advantage of being able to use the same computer program for scheduling elective cases (i.e.  , not add-on elective cases). Among the on-line and off-line algorithms that we considered, Best Fit Descending achieves the highest percentage utilization when used to schedule elective cases into a prespecified number of ORs. 2 OR managers who schedule their surgical suites to maximize OR utilization may want to use Best Fit Descending when assigning elective cases to ORs.
Fuzzy Constraints May Not Be Useful in OR Scheduling Other Than for Add-on Cases 
The appropriateness of using fuzzy constraints for OR scheduling depends on both the baseline utilization for elective cases (excluding add-on elective cases) and the number of ORs. If, for example, a hypothetical surgical suite with few ORs and high utilization (before placing the add-on elective cases) uses fuzzy constraints, then the use of 15 min of “flexibility” afforded by fuzzy constraints is no different than extending the duration of the regularly scheduled day by 15 min. If a different hypothetical surgical suite with many ORs and a low utilization (excluding add-on elective cases) uses fuzzy constraints, then the use of 15 min of flexibility intermittently may be appropriate. This argument applies generically to applications of fuzzy constraints to OR scheduling.
Duration of an Add-on Case Should Be Estimated Using the Mean of the Durations of Previous Like Cases When Applying Our Results 
We designed our analysis to be appropriate economically for surgical suites with at least some staff who are full-time employees without overtime. For convenience, we consider surgical suites with regularly scheduled OR hours that are 8-h per day, 5 days per week. For each day that an hourly employee works longer than 8 h, there must typically be another day within the pay period when they can stop working sufficiently early to ensure that the mean work week does not exceed 40 h. Consequently, case durations need to be predicted in a manner to ensure that the mean time that cases are completed in each OR is within the 8-h period. An add-on elective case would be scheduled into an OR provided that the case is scheduled to be completed within the 8-h period (although we also considered fuzzy constraints to relax this requirement). Therefore, provided that cases are scheduled in a manner so that the mean error in the time to complete the series of consecutive cases in each OR is ≤ zero, errors in surgeons’ predictions of the durations of their cases will not increase labor costs. The mean time to complete a series of consecutive cases approximately equals the sum of the mean times to complete each of the consecutive cases. 8 Therefore, for inaccuracy in predictions of the durations of cases to not increase labor costs in the economic setting that we simulated, each add-on elective case should be scheduled using the mean duration of previous like cases (e.g.  , same scheduled procedure and surgeon). 8 
Conclusions 
We identified the algorithm for scheduling add-on cases that maximizes OR utilization. Our simulations are likely to reflect reality for surgical suites with sufficiently few add-on elective cases each day (1) that usually have sufficient additional OR time to schedule zero or one add-on elective case in each OR and (2) in which the probability of a surgeon scheduling more than one add-on elective case each day is small. The algorithm can be used manually by a scheduler or can be implemented in an OR information system. The ease of implementation of the algorithm, either manually or in an OR information system, needs to be studied, as well as the conditions under which the algorithm actually increases (or does not increase) OR utilization relative to strategies currently used by OR managers.
References 
References 
Galambos G, Woeginger GJ: On-line bin packing: A restricted survey. Math Methods Oper Res 1995; 42:25–45
Kennedy MH: Bin-packing, knapsack, and change-constrained approaches to operating room scheduling [dissertation]. Troy, New York, Rensselaer Polytechnic Institute, Department of Decision Sciences and Engineering Systems, 1992, pp 24, 83, 84, 99
Dexter F, Macario A: Applications of information systems to operating room scheduling. ANESTHESIOLOGY 1996; 85:1232–4
McQuarrie DG: Limits to efficient operating room scheduling. Archiv Surg 1981; 116:1065–71
Law AM, Kelton WD: Simulation Modeling and Analysis, 2nd Edition. New York, McGraw-Hill, 1991, pp 337, 351, 465, 491, 492, 495
Solovy A: Benchmarking guide 99. Hospital Health Netw 1999; 73:49–62
Ozkarahan I: Allocation of surgical procedures to operating rooms. J Med Sys 1995; 19:333–52
Dexter F, Traub RD, Qian F: Comparison of statistical methods to predict the time to complete a series of surgical cases. J Clin Monit Comput 1999; 15:45–51
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
Fig. 1. Computer simulation uses real operating room (OR) time data (to obtain statistical distributions) and simulates the scheduling of add-on elective cases into ORs to determine which algorithm maximizes OR utilization. A hypothetical surgical suite begins with no add-on cases. The computer simulation modeling uses random draws from a probability distribution to generate open available time in each OR in the hypothetical surgical suite. Then, add-on elective cases (with their turnover times) are generated until the sum of the durations of the submitted add-on elective cases exceeds the total time remaining the operating rooms. These cases are scheduled into the operating rooms using one of the 10 algorithms studied (  table 1). OR utilization is computed for each algorithm. Utilization equals the time that an OR is used, including setup and cleanup, divided by the length of time an OR is available and staffed. 
×
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
Fig. 2. Example of scheduling add-on elective cases into the Ambulatory Surgery Center. In step #1, the time remaining in each of the six operating rooms in the suite was calculated. In step #2, the durations of add-on elective cases were determined. In step #3, the add-on elective cases were scheduled into the operating rooms (ORs). Results of step #3 are shown for Best Fit Descending with fuzzy constraints (algorithm #7) and Worst Fit Ascending (algorithm #9). Best Fit Descending scheduled the cases in descending sequence of case duration. Worst Fit Ascending scheduled cases in ascending order of case duration. In this example, Best Fit Descending with fuzzy constraints permitted five add-on elective cases to be completed, providing 6.65 h of cases during regularly scheduled hours (revenue). Case C would not be completed in the surgical suite on the day considered. In contrast, Worst Fit Ascending permitted only three of the add-on elective cases to be completed, achieving 3.08 h of cases (revenue). The other three add-on cases would not be completed on the day considered. Sensitivity analysis A modified steps #1 and #2 by rounding available times in the operating rooms and durations of the add-on cases to the nearest 15 min. 
×
Table 1. Features of the 10 Algorithms Considered in the Study 
Image not available
Table 1. Features of the 10 Algorithms Considered in the Study 
×
Table 2. Differences among Algorithms in Operating Room Utilization (%) 
Image not available
Table 2. Differences among Algorithms in Operating Room Utilization (%) 
×