Which Algorithm for Scheduling Add-on Elective Cases Maximizes Operating Room Utilization? : Use of Bin Packing Algorithms and Fuzzy Constraints in Operating Room Management

Ten different algorithms to schedule add-on elective cases into ORs were considered (table 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,2The 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.”

On-line algorithms consider each case in the order in which cases are submitted. 1,2We 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, 1,2in 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,2We 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. 4Best 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 2and as such serves as a positive control.

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.

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.

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.

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 5was 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).

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 ∥proceeded in the following stepwise manner for each surgical suite (figs. 1 and 2):

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. 5The 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. #We 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.

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).

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.

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.

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.

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.

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.

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.

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).

Rounding case durations to the nearest 15 min affected differences among algorithms in OR utilization by < 0.2%.

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).

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).

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 **that 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).

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 

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. 2OR managers who schedule their surgical suites to maximize OR utilization may want to use Best Fit Descending when assigning elective cases to ORs.

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.

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. 8Therefore, 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 

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.