A bicriteria heuristic for an elective surgery scheduling problem

Abstract

Resource rationalization and reduction of waiting lists for surgery are two main guidelines for hospital units outlined in the Portuguese National Health Plan. This work is dedicated to an elective surgery scheduling problem arising in a Lisbon public hospital. In order to increase the surgical suite’s efficiency and to reduce the waiting lists for surgery, two objectives are considered: maximize surgical suite occupation and maximize the number of surgeries scheduled. This elective surgery scheduling problem consists of assigning an intervention date, an operating room and a starting time for elective surgeries selected from the hospital waiting list. Accordingly, a bicriteria surgery scheduling problem arising in the hospital under study is presented. To search for efficient solutions of the bicriteria optimization problem, the minimization of a weighted Chebyshev distance to a reference point is used. A constructive and improvement heuristic procedure specially designed to address the objectives of the problem is developed and results of computational experiments obtained with empirical data from the hospital are presented. This study shows that by using the bicriteria approach presented here it is possible to build surgical plans with very good performance levels. This method can be used within an interactive approach with the decision maker. It can also be easily adapted to other hospitals with similar scheduling conditions.

Appendices

Appendix A: Mathematical model

The bicriteria integer linear programming model involves the parameters summarized in Table 5 and its formulation is presented in Fig. 5 (according to [16]).

Table 5 Parameters of the mathematical model

Fig. 5

Mathematical formulation of the bicriteria elective surgery scheduling problem

According to previous notation, objective functions z ₁ and z ₂ correspond to the surgical suite occupation and the number of surgeries scheduled, respectively. Some sets of constraints must be split between conventional and ambulatory surgeries because they use different operating rooms (R ^CS and R ^AS). The sets of constraints in this situation are identified with the same number and a C or an A is added in order to distinguish, respectively, between conventional and ambulatory surgeries.

Constraints (c1) force deferred urgency level priority surgeries to be scheduled on Monday in order to meet the 72 hour deadline for their completion. Constraints (c2) impose high priority surgeries to be scheduled during the planning week. Constraints (c3) state that the remaining surgeries, classified as priority or normal, may be scheduled or not during the planning week. Constraints (c4) guarantee that surgeries do not overlap in the same room. These constraints also impose γ empty periods for room cleaning at the end of each surgery (based on the definition of the lower sum limit). Constraint (c5) prevents assignment of more than one surgery specialty to each room and day. Constraints (c6) are the linking constraints for variables x and y. Constraint (c7) ensures that surgeons do not overlap between rooms in the same time period and day. Constraints (c8) and (c9) impose a daily and weekly operating time limit for each surgeon. The remaining constraints (c10) express the variables’ domain.

Appendix B: Application of rule (a, b)

This Appendix reports on the versions implemented and tested for the application of the rule (a, b) to schedule priority and normal surgeries. A brief description of these versions is listed below and the average results are summarized in Table 6.

Table 6 Average results for the different versions considering the application of rule (a, b)

vA:

[a + b] Basic version. Sequentially schedules a surgeries by descending order of estimated duration and then b surgeries by ascending order. The disadvantage of this version is the imbalance between the two objective functions when the weights originate a proportion with high values of a and b, favoring objective function z ₁. For instance, for $(\lambda , 1-\lambda ) = (0.47,0.53) \rightarrow a : b = 47 : 53$. In this case, in each cycle 47 surgeries are first scheduled by descending order of estimated duration and then 53 surgeries by inverse order.

vB:

[a + b; accounts for urgent deferred and high priority surgeries] Version developed from vA. For all the deferred urgency and high priority surgeries scheduled in steps 1 and 2 of the constructive phase (Algorithm 1), if the estimated duration is higher than the mean estimated duration of the surgeries in the waiting list ($\overline {p}$), then it is counted as having been scheduled by descending order of duration; and if the estimated duration is lower than the mean estimated duration of the surgeries in the waiting list, then it is counted as having been scheduled by ascending order of duration.

vC:

[1 + 1; accounts for urgent deferred and high priority surgeries] Version developed from vB. Alternately schedules one surgery by descending order of estimated duration and one surgery by ascending order of duration and schedules the remaining surgeries at the end of the cycle (a, b) to respect the proportion given by the weight λ. For instance, for (a, b) = (47,53), alternately schedules 1+1 surgeries until it reaches 47+47 and then schedules 6 surgeries by ascending order of estimated duration (to achieve 53). This version is introduced to overcome the disadvantage identified in the versions vA and vB. As well as in version vB, in this version the urgent deferred and high priority surgeries are counted for the rule (a, b). Thus, at the beginning of step 3 of Algorithm 1, a cycle (a, b) has already been started.

Next two versions differ from vC as they adjust the cycle that has already been started when entering step 3 of Algorithm 1. To describe these versions, let N _a and N _b be the number of (urgent deferred and high priority) surgeries counted in the current cycle resulting from the surgeries scheduled in steps one and two (as stated in vB).

vC1:

[1 + 1; accounts for urgent deferred and high priority surgeries; N _a = N _b ] Version developed from vC. In the first cycle of step 3 (Algorithm 1), starts to schedule (priority and normal) surgeries by the order (descending/ascending) with less surgeries already scheduled until N _a = N _b and then proceeds as stated in vC.

vC2:

[1 + 1; accounts for urgent deferred and high priority surgeries; a − N _a = b − N _b ] Version developed from vC. In the first cycle of step 3 (Algorithm 1), starts to schedule (priority and normal) surgeries by the order (descending/ascending) with the higher difference towards the maximum (a/b) until a − N _a = b − N _b and then proceeds as stated in vC.

Table 6 clearly shows that version vA provides slightly worst average results while, among the remaining versions, the results do not significantly differ. By comparing vA with the results obtained from the remaining versions, it is possible to observe the disadvantage identified in versions vA and vB, favoring objective function z ₁. For these reasons, versions vA and vB have been left out. Among the remaining versions, we chose the simplest version vC to report on the detailed results (Section 5) as it provided better average values simultaneously in both criteria $\max z_{1}$ and $\max z_{2}$.

Appendix C: Example

This Appendix illustrates the steps of the bicriteria heuristic in the search for a potentially non-dominated solution using instance I4_1899 and weight λ = 0.4. Tables 7 and 8 present a brief summary of the instance. Considering the weight vector (λ, 1−λ) = (0.4,0.6), then (a, b) = (2, 3). Figure 6 shows the evolution of the solution after each step of the heuristic. The changes that occurred in each step are highlighted by using the first option in the legend; the second option is used to represent surgeries scheduled in previous steps. The steps not represented in the figure did not change the solution. The surgical plan obtained (Fig. 6h) is a potentially non-dominated solution for instance I4_1899 with objective values (z ₁,z ₂) = (1044,191).

Table 7 I4_1899: Number of surgeries by surgical specialty, priority level and type (conventional/ambulatory)

Table 8 I4_1899: Summary statistics for the estimated duration (in time periods) - p - by surgical specialty and type (conventional/ambulatory)

Fig. 6

Bicriteria heuristic steps for I4_1899 with λ = 0.4