A two-stage robust optimization approach for the master surgical schedule problem under uncertainty considering downstream resources

Abstract

This paper addresses a planning decision for operating rooms (ORs) that aim at supporting hospital management. Focusing on elective patients, we determined the master surgical schedule (MSS) on a one-week time horizon. We assigned the specialties to available sessions and allocated surgeries to them while taking into consideration the priorities of the outpatients in the ambulatory surgical discipline. Surgeries were selected from the waiting lists according to their priorities. The proposed approach considered operating theater (OT) restrictions, patients’ priorities and accounted for the availability of both intensive care unit (ICU) beds and post-surgery beds. Since the management decisions of hospitals are usually made in an uncertain environment, our approach considered the uncertainty of surgery duration and availability of ICU bed. Two robust optimization approaches that kept the model computationally tractable are described and applied to deal with uncertainty. Computational results based on a medium-sized French hospital archives have been presented to compare the robust models to the deterministic counterpart and to demonstrate the price of robustness.

FormalPara Highlights

• We propose a two-stage approach to address the master surgical schedule and the surgical case assignment problems considering downstream resource capacity.

• The scheduling of surgeries in outpatient surgery follows a hygiene rule to reduce the risk of nosocomial infections.

• Uncertainty in surgery duration and intensive care unit bed availability is considered. We formulate the models as robust optimization problems.

• The proposed approach shows the impact of robust optimization for tactical schedules and evaluates the obtained solutions in terms of scheduled surgeries and operating theater’s utilization rate.

1 Introduction

An operating theater (OT) consisting of several operating rooms (ORs) is one of the most critical resources in hospitals because it generates both high revenues (more than 40% of a hospital’s total revenues [31]) and incurs high costs [3, 73]. Therefore, optimizing its resources by efficient scheduling becomes a top priority for an ever-growing number of hospitals, considering the waiting list of patients and different details on the characteristics and availability of several resources (e.g., ORs, intensive care unit (ICU) beds, post-surgery unit and surgeons), as well as the variability of surgery duration and patients’ length of stay (LOS).

OT planning problems consist of determining the schedule of surgeries, especially for critical services such as the ambulatory discipline, to maximize multiple performance measures such as OR utilization, efficiency, overtime, patients’ priority, lateness, and so on.

Ambulatory surgery, also known as day surgery and outpatient surgery, refers to surgery that does not require an overnight hospital stay. “Outpatient” refers to surgery, patients may enter and leave the facility on the same day.

Many countries are moving towards ambulatory surgery due to its benefits such as reduced costs, reduced infection rates, reduced complications, amenable appointment to patient requirements and preferences, the opportunity for the patients to heal at home, and shorter surgery duration, and so on. Berg et al. [16] (see [4, 16, 28, 48, 66, 91] and references therein for more details). The outpatient service provides many gains in terms of a reduction in health infections, since the exposure to the risk increases with the length of hospitalization. Economically, international studies have shown that outpatient care mobilizes fewer resources than classical surgery in terms of direct hospital costs [5].

The type of structure chosen is decisive for the establishment that performs the ambulatory surgery [5]. Four models are widely defined for coordinating ambulatory surgery, namely: the integrated facilities, the self-contained unit on the hospital site, the satellite facilities, and the free-standing self-contained unit. The integrated facilities are the most developed in France. They have reception and admission facilities that are dedicated to ambulatory surgery while being located in a classical hospital unit; the OTs are common to inpatient and outpatient admissions. The integrated model has been used in almost all French facilities over the last 20 years. This can be explained economically because this type does not require new buildings or large investments.

Our research aimed at finding an efficient planning and scheduling tool for the common OT in integrated facilities. Surgeries in ORs are carried out in sessions called “block time”. The block time is an OR session reserved to each surgical specialty, it can be a full day or a half-day. In this study, a block time is considered a full day.

The planning involves two stages. The first stage consists of deciding the surgical specialty that will be performed in each block time, then selecting patients to be operated in each block time according to the OT restrictions. In accordance with the OT manager instructions, we consider sequencing surgeries. The sequencing refers to assigning a sequence of appointment times for each type of surgery [4, 16, 66, 91] according to outpatients’ priorities and type of surgeries in the ambulatory surgery block time. The second stage determines the optimal number of surgeries that can be performed in each day according to their priorities and the availability of the downstream resources (such as post-surgery unit beds and ICU beds for patients requiring ICU treatment).

The problem of deciding the surgical specialty to be performed in each block time is tactical; it involves the master surgical schedule (MSS), which is a cyclic timetable. It gives the open time of available ORs to surgeons or specialties [106]. A new MSS is created whenever the total amount of OT time changes [2, 100]. Selecting the patients to be operated in each block time is operational, it refers to the scheduling case assignment problem (SCAP), and the problem of sequencing the surgeries in each block time is the elective sequencing of surgeries (ESS); surgeries must be scheduled in each block time and the sequence of surgeries must be determined. Developing higher quality schedules that integrate uncertainty in surgery durations may increase the satisfaction of both patients and surgeons, minimize costs, and produce improved health results [91]. Approaches focusing on surgery scheduling and/or sequencing can be found in [4, 16, 24, 31, 37, 48, 66, 91] and references therein for more details. In general, the OT manager faces many difficulties to solve such problems; they require respecting many different types of cases and various surgical procedures, many types of resources, such as OR personnel (surgeons, nurses, etc.), OR medical equipment, an so on. Moreover, many factors of the MSS are subject to uncertainty because they are made in an uncertain environment, such as surgery duration, patient arrival, resource availability, and so on. The hospital calls for strategies to promote decision-making tools and operation research approaches to handle scheduling and OT planning. From the OT manager’s perspective, the planning must be protected against uncertainties that may occur and sometimes respecting several objectives (e.g., overtime, idle time, OR utilization, patients’ waiting time, etc.). These problems lead to solving complex mathematical problems under several constraints, uncertainties, and objectives.

In this paper, we first propose a two-stage approach to address the MSS and SCAP on a one-week time horizon by considering sequencing surgeries in the ambulatory specialty. The approach consists of concurrently defining the surgical specialty in each block time, the list of surgical cases to be performed during each block time, and the desirable sequencing for the ambulatory surgical discipline. It is based on the current state of the patients’ waiting list, the OT restrictions, availability of resources (surgeon, OR, etc.), and downstream availability of resources (ICU beds and post-surgery unit beds). Throughout this study, “clean surgery” defines a surgery that requires a short cleaning time. Approximately 5 minutes after performing the surgery, and does not involve a hygienic issue for using the OR to treat future patients. In comparison, “dirty surgery” defines a surgery that requires a longer cleaning time (15 minutes) so as to prevent bacteria from spreading to subsequent patients. Dirty surgeries may be gallbladder, hemorrhoids, and cleaner surgeries may be a colonoscopy, hernia, and so on. For example, in a block time of visceral surgery, surgeries should follow a hygiene order (e.g., the first surgery to be treated is a hernia, the second is gallbladder surgery, and the last is hemorrhoid surgery). Therefore, the surgeries in the ambulatory specialty are treated from the cleanest to the dirtiest to avoid the infections from spreading to future patients and reduce the risk of nosocomial infection. The sequencing in the ambulatory specialty depends on various factors: the age of the patient, the type of surgery: clean or dirty, and so on. Secondly, we define and apply a robust optimization when surgery duration (processing time) is subject to uncertainty. The robust optimization approach by [17, 18] deal with uncertainty by limiting the number of uncertainties by a robustness parameter (the budget of robustness). We present in detail how new variables and constraints are applied to linear models to build robust models and evaluate the impact of robust solutions on the objective function.

Furthermore, we study the problem when ICU bed availability is subject to uncertainties. One approach to solve this problem involves the worst-case criterion [42, 93], and we use it in this study. We generate and discuss several scenarios to evaluate the proposed robust approach in terms of the utilization rate of the OT and the number of scheduled surgeries. Our study is inspired by a real hospital; models presented in this work are tested on empirical data from the archives of a French hospital.

The organization of the paper is as follows. Section 2 reviews a relevant state of the art that covers OT planning and highlights the contribution of the work. Section 3 describes the problem and the models. In Section 4, we provide a short background on the robust optimization; we present the approaches adopted in this study and highlight the importance of considering the robust nature of the problem. Computational results are given by comparing the robust models with the deterministic counterpart in Section 5. Finally, conclusions are given in Section 6, with outlines for future work.

2 Literature review

In this section, we provide a literature review of studies dealing with surgical scheduling. As stated in [106], the problem of OR planning and scheduling has been the subject of a wide number of contributions and it has been thoroughly reviewed by several authors. The decisions of OR planning and scheduling is divided into three levels: Long-term strategic, medium-term tactical and short-term operational [22, 55].

Strategic level

Resources planning problems, resource allocation problems, and case-mix problems (CMP) consist of scheduling problems at the strategic level. The problems generally have a long planning horizon and are based on very aggregate information and forecasts. The basic goal at this level is to enhance the use of resources and the allocation of budgets among the common surgical specialties. It focuses on the number and specialties of surgeries to be planned, and the number of the resources required, and so on. [20, 103]. Nonetheless, following the classification approach of most researchers, we classify capacity planning, resources allocation, and case-mix problem into a strategic level [106]:

• a. Capacity Planning: It can be described as the process of determining the number of resources needed to meet cost-effectively the demands [21, 26, 34, 40, 49, 61, 80, 92].

• b. Case-mix problems: It concerns the number and type of surgeries performed in the ORs [23, 45, 51, 53, 63, 64, 102].

• c. Capacity allocation: It refers to the allocation of specialties in OR management to OR days [20, 25, 28, 33, 47, 60].

Tactical level

The MSS is a tactical problem. Based on strategic level decisions, MSS provides advice to facilitate operational level decision-making. MSS is a cyclic timetable that determines the surgical unit associated with each block of OT time. Usually the time-scale is monthly or quarterly. MSS determines the distribution of the workload, which plays a major role in the scheduling process. Researchers use a variety of approaches to build MSS. Guido and Conforti [46] defined a MSS as that which assigns OR time to specialties and surgeons by optimizing conflicting objectives while taking into consideration the surgical characteristics and the maximum OR time set for each surgical specialty and surgeon. Agnetis et al. [3] focused on assigning the different surgical specialties to the available sessions, then allocating surgeries to each session to assess the weekly MSS. More papers focused on MSS can be found in [6, 8, 27, 68, 69, 89, 96, 97].

Operational level

The operational level involves decision-making in the short term, which is the surgery scheduling problem (SSP) or patient scheduling. Following the tactical level decisions, operational level implementation is supposed to match and schedule resources or patients. Surgery on the waiting list is scheduled for specific OR, day and time of commencement. The uncertainties in surgery duration and patient attendance significantly impact patient appointment booking, sequencing, and scheduling decisions in hospitals [16]. The surgeries on a day may end in longer overall surgical durations. Late start times often result in costs and staff overtime as the last surgery ends longer than expected [31]. [31] showed the impact using sequencing rules and surgery duration on total surgeon and OR team waiting time, OR idling, and overtime costs. The authors in [31] developed a Stochastic programming (SP) model with some heuristics to schedule the surgeries under duration uncertainty. Their model can be applied using both the block scheduling and the open scheduling scenario [106]. Berg et al. [16] developed an appointment scheduling model based on a two-stage stochastic mixed-integer program for optimizing booking and appointment times and sequencing of outpatients under uncertainty. Later, [91] considered two sets of decisions; sequencing and scheduling surgeries on a day for a single provider. Shehadeh et al. [91] presented a stochastic mixed-integer linear programming (MILP) model for the stochastic outpatient procedure scheduling problem to minimize patient waiting time, provider idling, and clinic overtime. Many studies decompose the OR scheduling and planning process into two steps:

• a. Advance scheduling: Also called as intervention assignment or SCAP [2] consisting of assigning an OR and a day for each surgery [6, 29].

• b. Allocation scheduling: It specifies the start time of the surgeries. [7, 57, 62, 87]. Some authors focused on the start times of surgeries and assumed that the sequencing of surgeries is already fixed in advance [91], (e.g., in [30, 37, 44] and references therein). Other authors focused on the scheduling and the sequencing of surgeries at the same time. Papers that addressed both decisions can be found in [4, 16, 28, 31, 66, 91, 95] and references therein.

• c. Integration of advance scheduling and allocation scheduling: Some authors integrate both the advance scheduling problem and the allocation scheduling problem [9, 35, 50, 52, 84, 85].

Basically, three different strategies design the scheduling problems [54]: The block scheduling strategy, the open strategy [10] and the modified block strategy. In the block scheduling strategy, the OT is allocated to a single surgical specialty [46, 56, 65], consisting of one or more surgeons in the same surgical discipline, since the same type of surgery is done in a given room over a given period. The physical management of equipment and/or materials is usually simplified [3, 7, 10, 12, 59, 78]. The block scheduling strategy is applied more often than the open scheduling strategy in European hospitals [106]. The open scheduling strategy is more flexible, in which there is no prespecified session-to-discipline assignment. Two surgical cares may be operated in the same block time at the same time [10, 38, 67, 69, 71, 104]. However, some inconveniences are related to the block scheduling strategy; if a block time is assigned to one surgeon, other surgeons cannot fill the block even if that surgeon does not schedule surgical cases in the block time. This is why the modified block scheduling strategy has been proposed [10, 31, 39, 75, 86, 101]. The modified scheduling strategy is usually applied in American hospitals.

The literature indicates that the uncertainty of surgery duration is implicit in surgical services. It is an affecting problem due to the highly variable nature of surgical specialties [101]. Such uncertainty or variability is commonly ignored in many OR planning and scheduling problems which assume deterministic surgery duration [106]. The duration of the surgery relates to the processing time. Duration uncertainty refers to the differences between the actual and expected durations of surgeries; it can be caused by the patient condition, the skill of the surgeon, and sometimes it depends on the surgical specialty [106]. So many authors have dealt with the duration uncertainty using stochastic optimization using Monte Carlo simulation [39, 72, 73, 88, 107]. Tohid et al. [99] presented a two-level physician planning framework for polyclinics under uncertainty. They used a Monte Carlo simulation algorithm to demonstrate the planning framework. Only a few of them have addressed robust approaches to deal with uncertainties [8, 11, 81, 82]. Addis et al. [1] addressed a robust optimization model to solve the advanced scheduling problem with uncertain surgery durations. Neyshabouri and Berg [77] developed a two-stage robust optimization approach for surgery scheduling under surgery duration and LOS uncertainty in the ICU based on the worst-case criterion. Neyshabouri and Berg [77] adopted the block scheduling strategy and presented robust solutions to schedule the surgeries with a low probability of lack of enough capacity. Min and Yih [74] proposed a two-stage SP approach based on the sample average approximation (SAA) method to generate an optimal schedule for the surgeries. Min and Yih [74] considered the uncertainty in surgery durations, LOS, and ICU beds capacity each day. Their model minimized both patient and overtime costs. Later, [90] introduced a distributionally robust elective surgery scheduling (DRESS) to schedule elective surgeries under block scheduling strategy. Shehadeh and Padman [90]’s approach took into consideration random surgery durations, random LOS in the ICU in addition to a limited ICU capacity. The DRESS model developed in [90] minimized the surgery costs, overtime, idle time, and ICU capacity. Zhang et al. [105] presented a two-stage SP model to schedule surgeries over a short-term planning horizon under surgery duration, LOS, and patients arrival uncertainty. They considered capacity constraints (ORs and ICU). Zhang et al. [105] modeled the problem as a Markov decision process and a two-stage SP.

In terms of problems addressed, this paper considers the block scheduling scenario. We propose a two-stage RO approach to address the MSS and SCAP in addition to the decisions considered in [74, 77, 90, 105]. Our approach can be considered as an extension of [3]. As in [3], the authors have addressed a decomposition approach to solving MSS and SCAP without taking into consideration several factors such as surgeons’ timetables, the uncertainties of surgery processing time, the particularity of the ambulatory discipline, and the availability of both post-surgery units and ICU beds.

The selected papers are listed in Table 1. Column 1 shows the references, the last row corresponds to the work proposed in the respective paper. Column 2 provides a short overview of the problem(s) addressed (strategical, tactical or operational). Column 3 shows the methodology used to solve the problem addressed. Column 4 defines the objective functions used. Finally, column 5 refers to the constraints considered.

Table 1 Comparison between the main literature on the MSS and the SCAP and the presented work in this paper

3 Problem description and mathematical modeling

3.1 Overview of problem

This study relies on the problem of allocating elective surgeries to ORs over a week. The surgeries are grouped into surgical specialties. For each surgery, a group of information is considered:

• Specialty type (general surgery, urology, ambulatory surgery, etc.)

• Nominal duration of surgeries (processing time)

• Decision time (day when the surgery entered the waiting list)

• Waiting time (days since the decision time)

• Due date (nominal time by which the surgery should be performed according to their priority)

• (Outpatient priority if the surgery is ambulatory) (children, elder, clean/dirty surgery)

• Post-surgery LOS in recovery unit

• ICU LOS

The hospital has one ICU and several post-surgery units. One of the post-surgery units is dedicated to ambulatory surgery outpatients, noted by (u = DS) as shown in Fig. 1. The patients stay in a bed in one of the surgical units upon arrival on the day of surgery. After the surgery, the patients expect to be monitored in the post-anesthesia care unit (PACU) for a range of minutes (e.g., 30 to 40 minutes for endoscopy) to several hours. When ready, they are transferred to the post-surgery unit. The outpatients are brought back to the ambulatory surgery unit and are discharged on the same day. On the other hand, some patients have to stay in the ICU before taken to the post-surgery unit.

Fig. 1

Elective patient flow

The main objective of this study is to define the best mix of elective surgeries types that must undergo surgery during the week according to the various hospital restrictions.

A block time can be a half-day [2] or the whole day (full-day sessions). In this study, the block time is considered a full-day session.

The elective surgical planning problem is a two-stage approach. In the first stage, we aimed to define the MSS by considering the OT restrictions. Some types of surgeries may only be performed in a restricted set of ORs due to limitations in size or equipment. Moreover, due to the number of surgeons available for the surgical discipline, only certain block times of the specialty can take place on the same day. Due to hospital management rules, the lower and upper limits block times for each surgical specialty are known. Furthermore, sometimes the hospital can assign one or more block time each day for some specialties. We took into account the following:

• Session capacity and demand should be balanced as much as possible [3].

• The due date of the patient must be taken into account, because the quality of the service may be determined by its due date results.

• Respecting the priority of surgeries in the ambulatory discipline: The sequencing is important because it gives children priority to undergo surgery first. Moreover, the cleanest surgeries to be achieved before the dirtiest ones. Besides, the sequencing may reduce health infections, and so on.

• Testing the robustness of the MSS against the variability of the duration of surgeries.

We considered a score of each surgery, which depends on how close is the surgery to its due date φ_i = (W − R_i), where R_i are the days to the due date and W is the maximum waiting time for low priority surgeries. W guarantees that urgent surgeries have a greater impact on the objective function and thus the model has more incentives to select them and consider the priorities of patients.

According to OT manager instructions, the scheduling of the outpatients in the ambulatory surgery block time must be respected. To do this, we assign two dummy outpatients to each ambulatory surgery block time. The first dummy outpatient is the first outpatient to be operated, its processing time is zero and its preference is the highest (so it can be always the first). The second dummy outpatient is considered as the last outpatient to be operated, its processing time is also zero and its preference is the lowest (so it can be the last). This technique will simplify the modeling of the problem. The outpatients will be scheduled according to their preference and health infections will be reduced. The model always favors children and cleanest surgeries, by assigning to them maximal preference; unlike dirty surgeries, to which we give lowest preference to be scheduled last. Similar surgeries take the same preference; for instance, two clean surgeries in the ambulatory specialty block time obtain the same preference. Therefore, the sequencing between the two is randomly chosen as they have the same preference.

In the second stage of the approach, we aimed to find the best mix of elective patients to be operated during the week based on the MSS given in the first stage, considering availability of both post-surgery units and ICU beds for the patients requiring ICU treatment. The patients are selected according to their scores, i.e., urgent surgeries have a greater impact and more chances to be selected. Basically, ICU beds are shared with the emergency department and may depend on human resources availability. Consequently, we aimed to build a robust solution when availability of ICU bed is subject to uncertainties.

3.2 First stage

We describe the deterministic model, decision variables, parameters and the objective function. We aimed to define the MSS on a weekly basis and allocate surgeries to sessions by considering the OT restriction and availability of resources.

We propose the following integer linear programming (ILP) model:

3.2.1 Problem’s parameters

To formally define the problem, we use the following notations and parameters:

S	Set of surgical specialties
Cs	Set of surgeons in specialty s
I	Set of all surgeries in the waiting list
	(I={1,...,n})
Is	Set of surgeries in the waiting list of specialtys
J	Set of days
Ro	Set of the operating rooms
SPR	Set of the outpatients with the same preference
NAORs	Set of unavailable ORs for specialty s
r	Index for operating room in Ro
j	Index for day
i	Index for surgery
s	Index for surgical specialty in S
a	Index for the ambulatory specialty in S
d	Index for surgeon in Cs
α	Dummy outpatient assigned to each
	ambulatory surgery block time and would
	be treated as the first outpatient
β	Dummy outpatient assigned to each
	ambulatory surgery block time and would
	be treated as the last outpatient
Ri	Days to due-date (nominal date) for surgery i
Pi	Expected duration of surgery i
φi	The score for surgery i
Omax	Block time capacity
$NBT_{s}^{max}$	Maximum number of block time for specialtys
$NBT_{s}^{min}$	Minimum number of block time for specialtys
PBTs	Maximum number of parallel block time for
	specialty s
W	Maximum waiting time for low-priority
	surgeries
NWDd	Number of days that surgeon d can work
	in a week
prfi	Preference of surgery i
M	Very large number

$$ dsp_{dj}= \left\{\begin{array}{lcr} 1 & \text{if surgeon d is available on day j} \\ 0 & \text{otherwise} \end{array} \right. $$

3.2.2 Decision variables

We define the decision variables as follows:

$$ x_{isrj} = \left\{\begin{array}{ll} 1 & \text{if surgery i of surgical specialty s is assigned to room r on day j} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ z_{dsrj} = \left\{\begin{array}{ll} 1 & \text{if surgeon d of surgical specialty s is assigned to room r on day j} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ w_{ilrj} = \left\{\begin{array}{ll} 1 & \text{if the outpatient l is operated immedietly after the outpatient i in room r on day j} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ y_{srj}= \left\{\begin{array}{ll} 1 & \text{if surgical specialty s is assigned to room r on day j} \\ 0 & \text{otherwise} \end{array} \right. $$

3.2.3 First stage’s ILP model

The objective considered in this paper is formulated as follows:

$$ \max\underset{s \in S}{\sum}\underset{i \in I_{s}}{\sum}\underset{r \in Ro}{\sum}\underset{j \in J}{\sum} x_{isrj} \varphi_{i} $$

(1)

Subject to:

$$ \underset{r \in Ro}{\sum}\underset{j \in J}{\sum} x_{isrj}\leq 1 \qquad \forall s\in S \qquad \forall i\in I_{s}\setminus\{\alpha,\beta\} $$

(2)

$$ \underset{s \in S}{\sum}\underset{i\in I_{s}}{\sum} P_{i} x_{isrj}\leq O^{max} \qquad \forall r\in Ro \qquad \forall j\in J $$

(3)

$$ \underset{i \in I_{s}}{\sum} x_{isrj}\leq M y_{srj} \qquad \forall s\in S \qquad \forall r\in Ro \qquad \forall j\in J $$

(4)

$$ \underset{s \in S}{\sum} y_{srj}\leq 1 \qquad \forall r\in Ro \qquad \forall j\in J $$

(5)

$$ \underset{r \in Ro}{\sum}\underset{j \in J}{\sum} y_{srj}\leq NBT^{max}_{s} \qquad \forall s\in S $$

(6)

$$ \underset{r \in Ro}{\sum}\underset{j \in J}{\sum} y_{srj}\geq NBT^{min}_{s} \qquad \forall s\in S $$

(7)

$$ \underset{r \in Ro}{\sum} y_{srj}\leq PBT_{s} \qquad \forall s\in S \qquad \forall j\in J $$

(8)

$$ \underset{r \in NAOR_{s}}{\sum}\underset{j \in J}{\sum} y_{srj} = 0 \qquad \forall s\in S $$

(9)

$$ x_{\alpha arj}\leq y_{arj} \qquad \forall r\in Ro \qquad \forall j\in J $$

(10)

$$ x_{\beta arj}\leq y_{arj} \qquad \forall r\in Ro \qquad \forall j\in J $$

(11)

$$ \underset{i \in I_{a}}{\sum} w_{i\alpha rj}=0 \qquad \forall r\in Ro \qquad \forall j\in J $$

(12)

$$ \underset{l \in I_{a}}{\sum} w_{\beta lrj}=0 \qquad \forall r\in Ro \qquad \forall j\in J $$

(13)

$$ x_{iarj} = \underset{l \in I_{a}/i \neq l}{\sum} w_{ilrj} \quad \forall i\in I_{a}\setminus\{\beta\} \quad \forall j\in J \quad \forall r\in Ro $$

(14)

$$ \underset{l \in I_{a}}{\sum} w_{ilrj} = \underset{l \in I_{a}}{\sum} w_{lirj} \quad \forall i\in I_{a}\setminus\{\alpha,\beta\} \quad \forall j\in J \quad \forall r\in Ro $$

(15)

$$ prf_{i} \!\geq\! w_{ilrj}\times prf_{l}\qquad \forall i,l\in I_{a} \qquad \forall j\in J \qquad \forall r\in Ro $$

(16)

$$ \underset{r \in Ro}{\sum}\underset{j \in J}{ \sum} z_{dsrj} \leq NWD_{d} \qquad \qquad \forall s\in S \qquad \forall d\in C_{s} $$

(17)

$$ y_{srj}=\underset{d \in C_{s}}{\sum} z_{dsrj} \qquad \forall s\in S \qquad \forall r\in Ro \qquad \forall j\in J $$

(18)

$$ z_{dsrj}\!\leq\! \mathit{dsp}_{dj} \quad \forall s\in S \quad \forall d\in C_{s} \quad \forall j\in J \quad \forall r\in Ro $$

(19)

$$ \underset{r \in Ro}{\sum} z_{dsrj}\leq 1 \qquad \forall s\in S \qquad \forall d\in C_{s} \qquad \forall j\in J $$

(20)

$$ \begin{array}{@{}rcl@{}} \underset{(i,l)\in SPR}{\sum}w_{ilrj}&\leq& \mid SPR \mid -1 \qquad \forall 2 \leq \mid SPR \mid \leq \mid I_{a} \mid \\&&-1 \quad \forall j\in J \quad \forall r\in Ro \end{array} $$

(21)

$$ \begin{array}{@{}rcl@{}} &&w_{ilrj},y_{srj},z_{dsrj},x_{isrj}\in \{0,1\} \qquad \forall s\in S \quad \forall i,l\in I_{s} \\&& \forall r\in Ro \quad \forall j\in J \end{array} $$

(22)

Objective Eq. 1 aims to select the surgeries that maximize the overall score. Constraint Eq. 2 ensures that each surgery can be performed at most once. Constraint Eq. 3 ensures that the upper limit of block time is respected. Constraint Eq. 4 guarantees that patients are assigned to only block time opened for their surgical discipline. Constraint Eq. 5 guarantees that at most one surgical specialty is assigned to an OR in a day. Constraints Eqs. 6-7 bound the number of weekly block time assigned to each discipline. Constraint Eq. 8 limits the number of parallel block time assigned to the same surgical discipline. Discipline-to-OR restrictions are taken into account by constraint Eq. 9. Constraints Eqs. 10-11 guarantee that the two dummy outpatients α and β are assigned to each ambulatory surgery block time. Constraint Eq. 12 ensures that the dummy outpatient α cannot have a predecessor. Constraint Eq. 13 guarantees that the dummy outpatient β cannot have a successor. Constraint Eq. 14 ensures that if an outpatient is selected from the ambulatory discipline, he/she has definitely one successor; this constraint links between sequencing and assignment variables. Constraint Eq. 15 ensures that if an outpatient of the ambulatory specialty has a successor, then the outpatient has definitely a predecessor (the conservation of flow). Constraint Eq. 16 guarantees that the sequencing of outpatients in the ambulatory surgery block time depends on the preference value of each outpatient. Constraint Eq. 17 limits the number of days that a surgeon can work. Constraint Eq. 18 guarantees that a block time is assigned to one surgeon of the same discipline. Days surgeons’ availability is taken into accounts by constraint Eq. 19. Constraint Eq. 20 ensures that a surgeon is assigned to one OR at most on a day. Schedule between outpatients with the same preference in the ambulatory surgery block times is considered by constraint Eq. 21, this constraint schedules randomly outpatients with the same preference by avoiding selecting outpatients already scheduled. Constraint Eq. 22 defines the integrality constraint.

3.3 Second stage

In the second stage, we aimed to find the best mix of elective patients to be planned during the week according to downstream resources’ availability (ICU and post-surgery unit beds). Using the MSS defined in the first stage as input, urgent patients have more chances to be selected and keep their places in the MSS. Hence, we propose the following MILP model:

3.3.1 Additional parameters

We define the following additional notation and parameters:

F	Set of classes of patients’ post-surgery LOS
Ω	Set of block times
K	Set of surgical groups
U	Set of post-surgery units in the hospital
Ik	Set of surgeries in the waiting list in group k ∈ K
k	Index for surgical group in K. A group k ∈ K
	of patients is characterized by its class and
	block time
f	Index for a class in F, f = 1 refers to
	outpatients surgical class
u	Index for the post-surgery units. u = 1 refers
	to the ambulatory surgery unit
ω	Index of block time in Ω
𝜗i	The score of the surgery i
τuj	Number of post-surgery beds available in
	surgical unit u ∈ U on day j
νj	Number of ICU beds available on day j ∈ J
$LS_{ik}^{ICU}$	The total LOS in the ICU for patient i ∈ Ik
$LS_{ik}^{U}$	The total LOS in the post-surgery unit for patient
	i ∈ Ik
pi	Surgery duration of patient i according to first
	stage

$$ VL_{k\omega} = \left\{\begin{array}{lcr} 1 & \text{if the block time $\omega \in {{\varOmega}}$ contains group $k\in K$} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ WL_{kj}= \left\{\begin{array}{lcr} 1 & \text{if the group $k\in K$ is assigned to day $j\in J$} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ rc_{k}= \left\{\begin{array}{lcr} 1 & \text{if surgeries in group $k\in K$ require a ICU bed} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ ec_{kf}= \left\{\begin{array}{lcr} 1 & \text{if the group $k\in K$ is of class $f\in F$} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ q_{il} = \left\{\begin{array}{lcr} 1 & \text{i{\kern-.2pt}f{\kern-.2pt} t{\kern-.2pt}h{\kern-.2pt}e{\kern-.2pt} o{\kern-.2pt}u{\kern-.2pt}t{\kern-.2pt}p{\kern-.2pt}a{\kern-.2pt}t{\kern-.2pt}i{\kern-.2pt}e{\kern-.2pt}n{\kern-.2pt}t{\kern-.2pt} \textit{l}{\kern-.2pt} i{\kern-.2pt}s{\kern-.2pt} s{\kern-.2pt}c{\kern-.2pt}h{\kern-.2pt}e{\kern-.2pt}d{\kern-.2pt}u{\kern-.2pt}l{\kern-.2pt}e{\kern-.2pt}d{\kern-.2pt} i{\kern-.2pt}m{\kern-.2pt}m{\kern-.2pt}e{\kern-.2pt}d{\kern-.2pt}i{\kern-.2pt}a{\kern-.2pt}l{\kern-.2pt}t{\kern-.2pt}l{\kern-.2pt}y{\kern-.2pt} a{\kern-.2pt}f{\kern-.2pt}t{\kern-.2pt}e{\kern-.2pt}r{\kern-.2pt} t{\kern-.2pt}h{\kern-.2pt}e{\kern-.2pt} o{\kern-.2pt}u{\kern-.2pt}t{\kern-.2pt}p{\kern-.2pt}a{\kern-.2pt}t{\kern-.2pt}i{\kern-.2pt}e{\kern-.2pt}n{\kern-.2pt}t{\kern-.2pt} \textit{i}} \\ 0 & \text{otherwise} \end{array} \right. $$

3.3.2 Decision variables

We define the decision variables as follows:

Aiωj	Start time of the outpatient i of block time ω on dayj

$$ \gamma_{ik\omega j} = \left\{\begin{array}{ll} 1 & \text{i{\kern-.2pt}f{\kern-.2pt} s{\kern-.2pt}u{\kern-.2pt}r{\kern-.2pt}g{\kern-.2pt}e{\kern-.2pt}y{\kern-.2pt} i{\kern-.2pt} o{\kern-.2pt}f{\kern-.2pt} g{\kern-.2pt}r{\kern-.2pt}o{\kern-.2pt}u{\kern-.2pt}p{\kern-.2pt} k{\kern-.2pt} a{\kern-.2pt}n{\kern-.2pt}d{\kern-.2pt} b{\kern-.2pt}l{\kern-.2pt}o{\kern-.2pt}c{\kern-.2pt}k{\kern-.2pt} t{\kern-.2pt}i{\kern-.2pt}m{\kern-.2pt}e{\kern-.2pt} $\omega$ {\kern-.2pt}i{\kern-.2pt}s{\kern-.2pt} a{\kern-.2pt}s{\kern-.2pt}s{\kern-.2pt}i{\kern-.2pt}g{\kern-.2pt}n{\kern-.2pt}e{\kern-.2pt}d{\kern-.2pt} t{\kern-.2pt}o{\kern-.2pt} d{\kern-.2pt}a{\kern-.2pt}y{\kern-.2pt} j} \\ 0 & \text{otherwise} \end{array} \right. $$

3.3.3 Second stage’s MILP model

The objective considered is formulated as follows:

$$ \max\underset{k \in K}{\sum}\underset{i \in I_{k}}{\sum}\underset{\omega \in {{\varOmega}}}{\sum}\underset{j \in J}{\sum}\gamma_{ik\omega j} \vartheta_{i} $$

(23)

Subject to:

$$ \underset{j \in J}{\sum}\gamma_{ik\omega j}\!\leq\! VL_{k \omega}\qquad \!\!\!\forall k\in K \qquad\!\!\! \forall i\in I_{k} \!\!\!\qquad \forall \omega\in {{\varOmega}} $$

(24)

$$ \underset{\omega \in {{\varOmega}}}{\sum}\gamma_{ik\omega j}\!\leq\! WL_{k j}\qquad\!\!\! \forall k\in K \qquad \!\!\!\forall i\in I_{k} \qquad \!\!\!\forall j\in J $$

(25)

$$ \underset{k \in K}{\sum}\underset{i \in I_{k}}{\sum}\underset{\omega \in {{\varOmega}}}{\sum} ec_{k1}\gamma_{i k\omega j}\leq \tau_{1 j}\qquad \forall j\in J $$

(26)

$$ \begin{array}{@{}rcl@{}} &&\underset{\underset{ec_{k1}=0}{k \in K}}{\sum}\left[(1-rc_{k})\left( {\sum}_{i \in I_{k}}{\sum}_{\omega \in {{\varOmega}}}\gamma_{i k\omega j}+ \underset{\underset{j^{\prime}>j-LS_{ik}^{U}}{j^{\prime} \in J}}{\sum}^{j-1}\gamma_{i k \omega j^{\prime}}\right)\right.\\ &&{\kern23pt}\left.+ rc_{k}\sum\limits_{i \in I_{k}}\sum\limits_{\omega \in {{\varOmega}}} \underset{j^{\prime}>j-LS_{ik}^{U}-LS_{ik}^{ICU}}{\sum\limits_{j^{\prime} \in J}^{j-1}}\gamma_{i k\omega j^{\prime}}\right] \\&&\leq \underset{\underset{u\neq 1}{u \in U}}{\sum}\tau_{uj}\qquad \forall j\in J \end{array} $$

(27)

$$ \begin{array}{@{}rcl@{}} &&\underset{\underset{ec_{k1}=0}{k \in K}}{\sum}rc_{k}\sum\limits_{i \in I_{k}}\sum\limits_{\omega \in {{\varOmega}}} \left( \gamma_{i k\omega j}+ \underset{j^{\prime}>j-LS_{ik}^{ICU}}{\sum\limits_{j^{\prime} \in J}^{j-1}}\gamma_{i k\omega j^{\prime}}\right) \\&&\leq \nu_{j}\qquad \forall j\in J \end{array} $$

(28)

$$ \begin{array}{@{}rcl@{}} &&A_{l\omega j}\geq A_{i\omega j}+p_{i}-M(1-q_{il}\sum\limits_{k \in K}\gamma_{i k\omega j})\\ &&\qquad \forall (i,l) \in I_{a}\\ &&\qquad \forall \omega \in {{\varOmega}} \qquad \forall j\in J \end{array} $$

(29)

$$ \begin{array}{@{}rcl@{}} \gamma_{ik\omega j}\in \{0,1\}&& \quad \forall k \in K \qquad \forall i \in I_{k}\\&& \quad \forall \omega \in {{\varOmega}} \qquad \forall j\in J \end{array} $$

(30)

$$ A_{i\omega j}\geq 0 \qquad \forall i \in I_{a} \qquad \forall \omega \in {{\varOmega}} \qquad \forall j\in J $$

(31)

Objective Eq. 23 aims to select the surgeries that maximize the overall score. Constraint Eq. 24 guarantees that each surgery is assigned at most one time during the planning horizon according to their corresponding group and block time in the MSS (linking with the MSS planning of the first stage). Constraint Eq. 25 guarantees that each surgery is assigned at most to one block time during the planning horizon according to their corresponding group and day in the MSS (linking with the MSS planning of the first stage). Constraint Eq. 26 ensures that the sum of elective surgeries not requiring an overnight stay does not exceed the number of beds in the outpatient surgical unit (u = 1) on day j. Constraint Eq. 27 guarantees beds’ availability in the post-surgery unit u on the day j. It is divided into two possibilities; (i) If surgeries of the group k require ICU stay, then rc_k = 1. Only the last term remains in the inequality. Consequently, the surgeries of ICU transferred on the day j to the unit u must not exceed the number of beds available in unit u on the day j. (ii) If surgeries of the group k do not require ICU stay, then rc_k = 0 the last term in the inequality is zero. The first term accounts for surgeries performed on the day j and transferred immediately to the unit u and the surgeries that have been and would stay in the unit u on the day j, the total of these surgeries must not exceed the number of beds available in unit u on the day j. Constraint Eq. 28 guarantees beds’ availability in the ICU on the day j; the sum of the surgeries performed on that day j and transferred to the ICU and the surgeries that were performed on previous days and used the ICU and would stay using the beds must not exceed the number of ICU beds available on the day j. Constraint Eq. 29 defines the start time for each surgery from the ambulatory specialty. Constraints Eqs. 30 and 31 enforce the binary variable of the model and the non-negativity restrictions.

4 Robust formulation

4.1 Overview of robust optimization

Robust optimization (RO) is a framework for modeling uncertainty in stochastic optimization problems when the distribution of uncertain problem data is not known. It has gained renewed interest over the past two decades with many applications from both practitioners and theorists [83]. RO models uncertain data using continuous or discrete sets of possible values, with no attached distributional probability. RO generates optimal solutions that are feasible for a defined set of values that uncertain parameters can take [77]. A solution is called “robust” if it is resistant to data disruption, at least within a given range. The robust solution is feasible for various data scenarios and not necessarily optimal for all of them. The term “robust” was used for the first time by [76].

Earlier, [93] introduced a robust approach that represents a guarantee against all possible realizations of uncertainties, reducing the problem’s resolution under uncertainty to solving a deterministic problem in which all the uncertain parameters take their worst-case values. Such robust solutions can be considered too pragmatic and are characterized in the literature as conservative solutions. A worst-case decision will not always be acceptable. The cost can be unnecessarily high if it is unlikely to happen. Later, [13, 14, 36] introduced less conservative approaches to deal with uncertainty. However, their models are nonlinear and hard to solve [79]. Consequently, a less conservative approach has been presented in [17, 18], and it is used in this study. A recent survey of literature about RO can be found in [15, 19, 43]. Bertsimas and Sim [18] state that in real life, not all parameters attain their worst values simultaneously, and only a part of them deviate from nominal values. The robust model introduced by [18] remains linear and computationally tractable.

Not privileging uncertainty may impact patients’ health and hospital quality of service. Using RO to evaluate uncertainty in health care and surgery planning problems can be more efficient than SP. SP has a significant drawback, which concerns the large size of the problems it generates, and involves memory space and computation time problems. The solutions given by the RO are protected against uncertainty and generate a probabilistic guarantee for the feasibility of solutions. SP may provide incorrect solutions for short-term planning, while RO can be successfully used [77].

Some specialties may be very sensitive and require particular attention (e.g., cardiology, oncology, vascular surgery). Cardiology and vascular surgery patients may undergo complicated surgeries that require long surgery duration and LOS in the post-surgery units and ICU beds. RO can produce solutions that are protected against uncertainty for short-term planning in such complex situations, and when it is not evident to receive probabilistic information or infeasibility cannot be tolerated [77].

4.2 Surgery duration uncertainty

The ILP model Eq. 1-22 assumes that the input duration data of surgeries (processing time) are precisely defined and equal to certain nominal values. Nonetheless, the impact of data uncertainties on accuracy and variability of the model is not taken into account. It is likely that since the data take values that are different from the nominal values, certain constraints may be violated and the optimal solution found using the nominal data may no longer be optimal or even feasible. The processing time of surgeries is subject to fluctuations because of several factors, namely surgeon’s skills, patient’s age and health, and so on. This is why we are looking to adopt our model to be resistant to data uncertainty.

Let assume that the processing time values are symmetric and bounded random variables that take values in $[\overline {P}_{i}-\widehat {P}_{i},\overline {P}_{i}+\widehat {P}_{i}]$, where $\overline {P}_{i}$ denotes a nominal value and $\widehat {P}_{i}$ its deviation ($\widehat {P}_{i}\geq 0$). The robustness parameter ∇ protects the constraint Eq. 3.

We define the random variables: $\eta _{i}=\frac {P_{i}-\overline {P}}{\widehat {P}_{i}}$, where η_i ∈ [− 1,1]. The data uncertainty is defined by the polyhedral uncertainty set as follows [18]:

$$ {{\varGamma}}^{P}_{rj}=\{P_{i}\in \mathbb{R}^{n}| P_{i}=\overline{P}_{i}+\widehat{P}_{i}\eta_{i}, \underset{i \in I}{\sum}\eta_{i} \leq\nabla, 0 \leq \eta_{i} \leq 1 \} $$

(32)

The decisions variables are assumed to be nonnegative. Consequently, the worst case will be reached at the right-hand side of the range $[\overline {P}_{i}-\widehat {P}_{i},\overline {P}_{i}+\widehat {P}_{i}]$. Hence, the random variable η in Eq. 32 is assumed to be positive (0 ≤ η_i ≤ 1). Without loss of generality, the confidence range $[\overline {P}_{i}-\widehat {P}_{i},\overline {P}_{i}+\widehat {P}_{i}]$ does not have to be symmetric.

For each day j, and OR r, a subset of patients which cardinal is denoted by ∇ follows the worst-case scenario in surgery duration. The worst-case value is reached by considering the largest surgery duration deviation. The subset chosen is the one with the worst effect on the block time capacity from all possible subsets, and the solution is assumed to be feasible concerning this subset [1].

The protection function was included in the constraint Eq. 3 as follows:

$$ \underset{s \in S}{\sum}\underset{i \in I_{s}}{\sum}\overline{P}_{i}x_{isrj}+\beta_{rj}(x^{*},\nabla)\leq O^{max} \qquad \forall r,j $$

(33)

Where,

$$ \begin{array}{@{}rcl@{}} &&\beta_{rj}(x^{*},\nabla)=\underset{\{S^{\prime}_{rj}\cup \{t_{rj}\}|S^{\prime}_{rj}\subseteq I, card(S^{\prime}_{rj})=\left\lfloor\nabla\right\rfloor, t_{rj}\in I\setminus S^{\prime}_{rj}\}}{\max} \left\{{ \underset{s \in S}{\sum} \underset{i \in S^{\prime}_{rj}}{\sum}\widehat{P}_{i} x_{isrj}^{*}+(\nabla-\left\lfloor\nabla\right\rfloor)\widehat{P}_{t_{rj}} x_{isrj}^{*}}\right\} \end{array} $$

(34)

Where $\overline {P}_{i}$ the nominal value of the processing time, for all r and j. β_rj is equivalent to the following problem:

$$ \max \underset{s \in S}{\sum} \underset{i \in I_{s}}{\sum} \widehat{P}_{i} x_{isrj}^{*}g_{i} $$

(35)

$$ \underset{i\in I}{\sum} g_{i}\leq \nabla $$

(36)

$$ 0 \leq g_{i} \leq 1 \qquad \forall i\in I $$

(37)

Note that $x_{isrj}^{*}$ is the optimal solution of the deterministic model and not a variable in this problem. g_i is the decision variable, $\widehat {P}$ is the precision range.

The dual of model Eqs. 35–37 is written as follows:

$$ \min \nabla u_{rj}+\underset{s \in S}{\sum} \underset{i\in I_{s}}{\sum}v_{isrj} $$

(38)

$$ u_{rj}+v_{isrj} \geq \widehat{P}_{i}x_{isrj} \qquad \forall s\in S \qquad \forall i \in I_{s} $$

(39)

$$ u_{rj} \geq 0 $$

(40)

$$ v_{isrj} \geq 0 \qquad \forall s\in S \qquad \forall i \in I_{s} $$

(41)

Where u_rj and v_isrj are the dual variables associated to constraints Eqs. 40 and 41, respectively. By strong duality, the optimal values of Eqs. 38 and 35 coincide. The dual model Eqs. 38-41 is replaced with the protection function to obtain the robust formulation of Eq. 33:

$$ \underset{s \in S}{\sum} \underset{i \in I_{s}}{\sum}\overline{P}_{i}x_{isrj}+\nabla u_{rj}+\underset{s \in S}{\sum}\underset{i \in I_{s}}{\sum} v_{isrj} \!\leq\! O^{max} \qquad \!\!\forall r,j $$

(42)

$$ u_{rj}+v_{isrj} \geq \widehat{P}_{i}x_{isrj} \qquad \!\!\forall s\in S \qquad \!\!\forall i \in I_{s} \qquad \!\!\forall r,j $$

(43)

$$ u_{rj} \geq 0 \qquad \forall r,j $$

(44)

$$ v_{isrj} \geq 0 \qquad \forall s\in S \qquad \forall i \in I_{s} \qquad \forall r,j $$

(45)

The robust optimization problem Eqs. 1-22 can be reformulated as the following ILP model:

$$ \max \sum\limits_{s \in S}\underset{i \in I_{s}}{\sum}\underset{r \in Ro}{\sum}\underset{j \in J}{\sum}x_{isrj}\varphi_{i} $$

(46)

subject to: Eqs. 2, 4-22

$$ \underset{s \in S}{\sum} \underset{i \in I_{s}}{\sum}\overline{P}_{i}x_{isrj} + \nabla u_{rj} + \underset{s \in S}{\sum}\underset{i \in I_{s}}{\sum} v_{isrj} \!\leq\! O^{max} \qquad \!\!\forall r,j $$

(47)

$$ u_{rj} + v_{isrj} \!\geq\! \widehat{P}_{i}x_{isrj} \qquad \!\!\forall s\in S \qquad \!\!\forall i \in I_{s} \qquad \!\!\forall r,j $$

(48)

$$ u_{rj} \geq 0 \qquad \forall r,j $$

(49)

$$ v_{isrj} \geq 0 \qquad \forall s\in S \qquad \forall i \in I_{s} \qquad \forall r,j $$

(50)

The robust approach increases the number of constraints and variables, but the big advantage is that the model remains linear and computationally tractable. Thus, it can be solved using commercial optimization solvers in a reasonable time.

4.3 ICU bed availability uncertainty

We consider the MILP model Eqs. 23-30; we suppose that the number of available ICU beds in each day j is uncertain. We deal with uncertainty on right hand sides with inequality constraints. The approach introduced by [18] cannot always be usefully applied [42]; [41] presented a critical analysis. Hence, the worst-case criterion can be relevant [42, 93].

We consider the following linear programming model:

$$ \left\lbrace \begin{aligned} min \quad cx\\ s.t. \quad Ax\geq b \end{aligned} \right. $$

(51)

Where A is an n × m matrix, and $\displaystyle b\in \mathbb {R}^{m}$. We suppose that b_i is uncertain and varies in an interval $[\underline {b_{i}},\overline {b_{i}}]$. Let π be the Cartesian product of interval $[\underline {b_{i}},\overline {b_{i}}]$. For all b ∈π, we define the nonempty polyhedron $\displaystyle X_{\geq }^{b}=\{x\in \mathbb {R}^{n}: Ax \geq b\}$; it contains the feasible solutions under scenario b. The smallest feasible solution set of Eq. 51 is obtained when b is $\overline {b}$. For all x in $X_{\geq }^{\overline {b}}$ the worst value is equal to cx for all scenarios. A solution x, which does not belong to $X_{\geq }^{\overline {b}}$ has a worst value equal to $+\infty$ (because x is at least infeasible for one scenario) [42]. Hence, the optimal solution according to the worst-case criterion necessarily belongs to $X_{\geq }^{\overline {b}}$ and the optimal solution according to the worst-case criterion is solved as follows:

$$ \left\lbrace \begin{aligned} min \quad cx\\ s.t. \quad Ax\geq \overline{b} \end{aligned} \right. $$

(52)

The number of available ICU beds in each day j ∈ J is uncertain and varies in an interval $[\underline {\nu _{j}},\overline {\nu _{j}}]$. As a result, the optimal solution according to the worst-case criterion is solved as follows:

$$ \max\underset{k \in K}{\sum}\underset{i \in I_{k}}{\sum}\underset{\omega \in {{\varOmega}}}{\sum}\underset{j \in J}{\sum}\gamma_{ik\omega j} \vartheta_{i} $$

(53)

subject to: Eqs. 24–27,29-31

$$ \begin{array}{@{}rcl@{}} &&\underset{\underset{ec_{k1}=0}{k \in K}}{\sum}rc_{k}\underset{i \in I_{k}}{\sum}\underset{\omega \in {{\varOmega}}}{\sum} \left( \gamma_{ik\omega j}+ \underset{{j^{\prime}>j-LS_{ik}^{ICU}}}{\sum\limits_{j^{\prime} \in J}^{j-1}}\gamma_{ik\omega j^{\prime}}\right) \\&&\leq \underline{\nu_{j}}\qquad \forall j\in J \end{array} $$

(54)

The problem is solved in polynomial time [42]. The optimal solution of Eqs. 53-54 is considered as the robust solution, since it is feasible under any possible scenario.

5 Computational experience

The experimental tests aim to evaluate the behavior of the proposed two-stage approach for the deterministic and the robust case in terms of utilization rate and number of scheduled surgeries from the waiting list. The dataset is taken from the archives of the OT of a medium-sized public French hospital. The assessments were carried out over a week. The choice of week was made based on two factors; a week with a large volume of outpatient surgery and a week not containing school holidays.

The OT has R = 8 ORs; nevertheless, we only take into consideration 7 of them. In fact, the 8^th room is devoted to the emergencies (EMR). All the ORs are identically equipped, but some rooms are more suitable for some specialties than others. Surgeries belong to the following specialties as shown in Table 2: Gynecology (s=GYN), urology (s=URO), orthopedic surgery (s=ORTH), vascular surgery (s=VAS) and ambulatory surgery (s=DS).

Table 2 Specialties of the hospital

We tested three different sizes of the OT, 8 ORs, 12 ORs and 16 ORs with 2 different waiting lists (140 and 180 surgical cases). For instance (P.140,R.8) refers to the waiting list contains 140 surgical cases; (45 outpatients, 95 patients from the different specialties) and 20 surgeons.

The number of days that surgeons can work in a week is fixed to 4 days per week. The age of the outpatients in the ambulatory surgery is generated randomly between 1 and 100 years, 50% of the surgeries are considered clean and 50% dirty, the block time lasts 450 minutes, we set W = 90.

The surgeons are grouped in sets of surgical specialties that are allowed to work 4 days distributed across the week. We generated a matrix of availability of surgeons, which is 0 if the surgeon is not available in a day, otherwise 1.

The scheduling of the surgeries in each ambulatory specialty block time takes into consideration the priorities of the outpatients. According to the preference values given by the decision-maker to the ambulatory surgeries, the model always favors children and the cleanest surgeries, hence, they are always scheduled first by assigning maximal preference to them. Unlike dirty surgeries, we give to the similar surgery types the same preference. For instance, two clean surgeries in the ambulatory specialty have the same preference. The choice between two surgeries with the same preference is random and has no criterion.

Table 3 shows the restrictions on rooms in the computational settings for the instance (P.140,R.8). The second column defines the set of unavailable ORs for each discipline. The gynecology specialty can only be assigned to OR 2 and 3 then NAOR_gyn = {1,4,5,6,7,8}, although the ambulatory surgery can be assigned to any OR in the OT except OR 8 because this room is reserved to the emergencies. Furthermore, columns 3 and 4 refer to the number of minimal/maximal block time for each discipline. Column 4 shows that parallel block times are only allowed in some surgical specialties, for example, the ambulatory specialty and the orthopedic surgery.

Table 3 Restriction on MSS for instance (P.140,R.8)

We define $NBT_{s}^{max}$ (the number of maximal block time for specialty s) as the weighted sum of two components $NBT_{s}^{max}=w_{1} \times HNBT_{s}+ w_{2}\times LNBT_{s}$, where w₁ and w₂ are positive numbers such that w₁ + w₂ = 1. The first component HNBT_s is the historical number of block time, which have been assigned weekly to specialties, the second component LNBT_s is the number of sessions to clear the waiting list of specialties.

5.1 Deterministic models computational results

The hospital has 8 ORs, one of them is devoted to emergencies. Three post-surgery units are dedicated to elective surgeries. The post-surgery unit (u = 1) is committed to ambulatory surgery, it has 15 beds and it closes at nights. The two other units (u = 2,u = 3) are dedicated to elective patients and have respectively 14 and 18 beds. The ICU has 7 beds shared with the emergency department.

The LOS of the patients varies from 1 to 10 days. The patients requiring ICU treatment are limited. Hence, we generate 3 scenarios; 0%, 1% and 2% of patients requiring ICU treatment. (I.1) refers to 1% of surgeries on the waiting list require ICU treatment.

5.1.1 Operated patients

Numerical results for a deterministic model are given in Table 4. Column 2 shows the number of scheduled surgeries for each instance without taking into account the availability of ICU beds and the post-surgery unit beds. While column 3, 4 and 5 give the number of scheduled surgeries with taking into account the availability of ICU beds and post-surgery unit beds with 0%, 1% and 2% of patients requiring ICU treatment, respectively. When the number of patients requiring ICU beds increase, the number of patients selected decreases. The experiments were performed using CPLEX Optimization Studio 12.6 on Dell computer Intel Xeon CPU E5 − 2667 v4 3.20 GHz 64 G RAM.

Table 4 Operated patients of the deterministic models

Table 5 shows results obtained for instance (P.140,R.8). The MSS planning respects all constraints and discipline-to-OR restrictions.

Table 5 MSS planning for instance (P.140, R.8)

Figure 2 shows an example of the scheduling obtained in the ambulatory surgery block time with respect to outpatient priorities and preferences. Dirty surgeries are scheduled last to avoid health infections.

Fig. 2

Example of scheduling in an ambulatory surgery block time

5.2 Robust models computational results

Table 6 provides statistics related to the distributions of surgery durations for each surgical specialty. We present the mean surgery duration denoted by ${\mu ^{s}_{P}}$, and the standard deviation ${\sigma ^{s}_{P}}$ for each specialty s. For each patient i from specialty s, the nominal surgery duration $\overline {P}_{i}$ is computed by randomly generated from a lognormal distribution according to the statistics corresponding to specialty s [94]. To compute stochastic surgery time, the lognormal distribution is recommended by several authors [32, 70, 94] and it is consistent with the data analysis of surgery duration. Figures 3 and 4 present the distribution of surgery durations of orthopedic and gynecologic surgery, respectively. The maximum deviation $\widehat {P}_{i}$ (worst-case deviation) in surgery duration for each patient i is computed as follows: $\widehat {P}_{i}={\delta \sigma ^{s}_{P}}$, we set δ = 1.

Table 6 Data statistic on the distributions of surgery durations related to specialties

Fig. 3

Distribution of surgery durations of orthopedic surgery

Fig. 4

Distribution of surgery durations of gynecologic surgery

The effect of protection level on objective function value is illustrated in Fig. 5. When ∇ = 0 the optimum value is 11106. Which represents the deterministic model; while with a maximum protection, it refers to [93] method; the optimum value is reduced to 4.65% by 10589, the decrease in the objective value is the price of robustness.

Fig. 5

Optimal value as function of ∇

The degree of protection for a given constraint i is determined by the level of protection ∇_i. The parameter is related to the probability bound to determine the value ∇_i to meet the i^th constraint with a given probability [79].

Bertsimas and Sim [18] evaluated the degree of constraint satisfaction by a probability bound $exp(-\frac {{\nabla _{i}^{2}}}{2n})$; the probability bound depends on the size of the problem; more precisely, the number of uncertain coefficients within the same constraint. The approach becomes relevant when the value of n is high; it brings a significant gain compared to [93] approach [83].

Table 7 presents the results of the robust MSS; the objective function value and the probability bound of constraint violation. The horizontal axis represents the probability of violation, and the vertical axis shows the optimal value according to the budget of robustness. Column 4 refers to the decrease of the objective value, which is the price of robustness; when ∇ = 12 the optimum value is 10607, while with a maximum protection, it refers to the method of [93]; the optimum value is reduced to 4.65% by 10589. The decrease in the objective function as result of robust solution compensated by the benefit in terms of robustness or feasibility.

Table 7 Result of the robust MSS for instance (P.140,R.8)

The price of robustness is calculated by the following formulation:

$$ \frac{f(x(\nabla))-f}{f}.100 \% $$

(55)

Where x(∇) is the optimal solution for the defined budget ∇ and f(x(∇)) its objective value, and f represents the optimal objective value of the deterministic problem.

In Fig. 5, we plot the optimal value as a function of ∇ the robust decision has a small effect on the objective value; when there is no protection the objective value is 11106. When ∇≥ 12 the model is insensitive to ∇. This is exactly the solution given by the method of [93]. With maximum protection, the objective value is reduced by 4.65%.

Figure 6 shows the optimal value with respect to the probability bound of constraint violation. To have a probability guarantees at most a 0.8% chance of constraint violation, the objective is only reduced by 1.9%. We noticed that the optimal value is marginally affected when we increased the protection level. The approach of [18] succeeded in showing the price of robustness; it is not necessary to penalize the objective function value to protect the model against constraints violation.

Fig. 6

Optimal value as a function of the probability bound of constraint violation

We aim to calculate the infeasibility probability of robust solutions for different budgets by considering random realizations of the uncertain surgery duration. We empirically assess the number of times a given optimal solution is infeasible. Therefore, we randomly generate 300 random realizations provided by the Monte Carlo simulation for uncertain surgery duration from the lognormal distribution.

The simulation steps are presented as follows:

• 1. Input. Solution x(∇)

• 2. For ϖ = 1 to 300, do: -${P}_{i}^{\varpi }\sim lognormal({\mu ^{s}_{P}},{\sigma ^{s}_{P}}) \quad i\in I$ -Evaluate the feasibility of x(∇) using ${P}_{i}^{\varpi }$

• 3. Output. The empirical probability evaluating constraint violation of the solution.

The significant impact of the budget of robustness ∇ on the infeasibility probability of robust solutions out of 300 random realizations of uncertain surgery duration is depicted in Fig. 7. It also shows the price of robustness as a function of ∇.

Fig. 7

Infeasibility probability and price of robustness for robust solutions

According to Fig. 7, the budget of robustness that ensures the feasibility is 6. Moreover, the penalty of robust solutions feasibility is about 2.3%. Figure 7 shows the trade-off between feasibility and robust schedules penalty for different values of ∇.

Figure 8 illustrates the decrease in the objective function for the worst case criterion approach for three instances. 1,2,3 and 4 correspond to without DR, (I.0), (I.1) and (I.2), respectively.

Fig. 8

Comparison between wost case and deterministic solutions

5.2.1 Scheduled surgeries

The ICU has 7 beds shared with the emergency department. Only a number of them are dedicated to the OT (2 or 3). The availability of the ICU beds depends generally on human resource availability and the emergency department. Hence, we suppose that the availability of beds varies on each day within an interval $\nu _{j}\in [\underline {\nu _{j}},\overline {\nu _{j}}]\quad \forall j \in J$. The number of surgeries performed according to the proposed two-stage approach is given in Table 8. The first block of Table 8 refers to the first stage problem when downstream resource availability is not taken into consideration. Blocks 2, 3, and 4 give the number of scheduled surgeries when 0%, 1%, and 2% of patients require ICU beds. The availability of ICU beds is uncertain. (P.140,R.8,I.0) denotes instance of 140 patients, 8 ORs, and 0% of patients require ICU beds.

Table 8 Scheduled surgeries

Table 8 presents the number of scheduled surgeries for each instance to observe the influence of ∇ on the number scheduled surgeries. The objective function becomes constant when ∇ reaches a certain level, and it varies for different instances. In the following tables we denote (−) to when ∇ reaches that value. We remark that for greater values of ∇, the number of scheduled surgeries decreases, because the solution becomes more robust and a larger subset of patients require the maximum surgery duration.

The number of scheduled surgeries remains the same when ∇ exceeds a certain value, it is related to the fact that ∇ is equal or greater to the number of maximum patients that can be scheduled in one block time. Consequently, all the patients require their maximum surgery duration. The subset of scheduled surgeries is not the same for different values of ∇.

5.2.2 Comparison of the deterministic models and robust models in computational time

Table 9 presents the computational time required to solve the two-stage models.

Table 9 Computational time

The first block of Table 9 shows the computational time required to solve the first-stage model. The gap is fixed to 1.e-4 when the solver attends the gap; we refer to it with “ag”. The deterministic case (DC) is not complicated in terms of computational time. For the DC, all instances are solved to optimality. Concerning the second stage of the problem, the computational time requires more effort because of the limited number of ICU beds and the increasing number of patients requiring ICU beds. The computational time increases, but the models are still solved to optimality. Concerning the robust model of the first stage problem (the first block of the Table 9 with varying ∇), the model requires more computational time compared to its deterministic counterpart. The computational time increases when the value of ∇ increases. We observed that it reaches its maximum when ∇ is between 6 and 10. Since the number of surgeries that can be operated during the block time is achieved and all the scheduled surgeries require their maximum surgery duration, the computational time is not dramatical for a weekly planning. The number of block times considered during the planning horizon and the number of patients on the waiting list have a significant effect on the computational time required to solve the robust model of the first stage problem. Two instances run out of memory (they are denoted with “^∗”), and three instances were interrupted by the user because no optimal value was reached within a time limit of three hours (denoted with “$\sim$”). However, the gaps are reasonable, with an average value of 4.01 %.

5.2.3 Comparison of the deterministic models and robust models in utilization rate

Table 10 shows the utilization rate of block times. The second column refers to the DC when no uncertainty occurs. The DC has a high utilization rate and varies between 100% and 80%. While the utilization rate decreases when the value of ∇ increases, the number of patients requiring longer surgery duration increases. The utilization rate below 100% is related to a lack of OR capacity utilization. The utilization varies according to the instances and the uncertainties that occur. The utilization rate of the OR could be 70% and 60% but it is still above 60%. We can remark that small ∇ guarantees a better utilization of the OT. In other words, only a small number of surgeries can be allowed to deviate its duration on each block time to properly explore the OT. The unexplored OR capacity could be managed to concern emergencies. Besides, it can be used to schedule surgeries that cannot be handled by the MSS and the SCAP generated, without changing the planning.

Table 10 Utilization rate of the OT (%)

The DC model gives the optimal solutions in reasonable computational time, provides a high utilization rate, and it helps to schedule a large number of surgeries. However, sometimes the higher utilization rate may lead to overtime, delay, and so on. Speaking intuitively, it is unlikely that none of the surgeries will deviate from the nominal surgery duration. The results show that the proposed robust models can be used since they give protected solutions against uncertainty. The robust models can have a challenging computational time but still suitable for the weekly schedules; the gaps are limited even for the larges instances. The behavior of robust models in terms of utilization rate and scheduled surgeries are reasonable for all instances; the utilization rate is above 60% even for a high value of ∇. In other words, the robust models can produce good results by correctly turning the budget of robustness ∇.

5.2.4 Overtime impact

We evaluate the impact of allowing overtime in the model. In other words, we permit some block times to have overtime. Then, we observe its behavior on scheduled surgeries and utilization rate. Maximum overtime equal to 1.5 hours is allowed for half-block times of the MSS. We add a parameter as follows:

$$ o_{rj}= \left\{\begin{array}{lcr} t & \text{if overtime is allowed on day j and room r} \\ 0 & \text{otherwise} \end{array} \right. $$

$$ t \qquad \text{The amount of overtime} $$

The following constraint is added to the model Eqs. 1-22 as follows:

$$ \sum\limits_{s \in S}\sum\limits_{i\in I_{s}} P_{i} x_{isrj}\!\leq\! O^{max} + o_{rj} \qquad \!\!\forall r\in Ro \qquad \!\!\forall j\in J $$

(56)

Constraint Eq. 56 allows the block times to have an overtime.

The following Tables 11 and 12 show the impact of overtime on the number of scheduled surgeries and utilization rate of OT, respectively.

Table 11 Scheduled surgeries with allowed overtime

Table 12 Utilization rate of the OT with allowed overtime (%)

Allowing overtime influences the obtained solution. It increases the number of scheduled surgeries for most instances as shown in Table 11. In addition, the overtime improves the utilization rate of OT as given in Table 12. The utilization rate has a significant impact for most instances and reaches a high rate for some of them, which ensures a high hospital productivity. For the robust solutions, the limited number of ICU beds still produces a good rate of utilization, especially with ∇ between 0 and 8. Allowing a few surgeries to deviate for each block time can be acceptable to achieve a good utilization rate of the OT.

Allowing overtime has a significant impact on hospitals in terms of costs [74]. A good trade-off between hospital quality of service and cost can be reached by fixing the budget of robustness ∇, and the block times allowed to have overtime. However, allowing overtime not only impacts in terms of extra costs and staff salaries but also can significantly impact staff performance. Nurses and surgeons may become overtired or inattentive due to overtime fatigue. Hence, performance efficiency may suffer by eventual risks of errors and mistakes [98].

6 Conclusion and perspectives

This investigation established a new two-stage approach to solving the MSS and SCAP, which considered patients’ priorities, OT restrictions, and downstream resource availability in an integrated hospital facility. The approach gave a particular interest to ambulatory surgery. Two robust optimization approaches were applied. Using the approach by [17, 18], we incorporated duration uncertainty. The trade-off between conservatism and robustness was explored, and the price of robustness was demonstrated.

Moreover, the worst-case criterion [42, 93] was applied when the availability of ICU beds was uncertain. Computational results were tested on empirical data from the archives of a French hospital. The results obtained showed the impact of uncertainty in surgery duration and ICU bed availability on the scheduled surgeries and the utilization rate of the OT; the budget of robustness had a significant impact on the obtained planning. The robust model is an efficient tool to schedule the OT in a real context.

This study may be the basis for further developments by considering the emergency department. In the future, we would like to work on a robust version with more uncertain parameters (e.g., LOS uncertainty in the post-surgery recovery beds and ICU beds) to build robust decisions to evaluate OT efficiency and performance.

Appendix: Overview of the robust optimization approach by [18]

We consider the linear programming problem:

$$ \max \sum\limits_{j=1}^{n} c_{j}x_{j} $$

(57)

subject to:

$$ \sum\limits_{j=1}^{n} a_{ij}x_{j}\leq b_{i} \qquad \forall i $$

(58)

$$ x_{j} \geq 0 \qquad \forall j $$

(59)

The variable x_j, the cost c_j, indexes and the dual variables defined in this section are independent.

We consider $J^{\prime }_{i}$ the set of coefficient a_ij that are subject to uncertainty. The coefficients a_ij belongs to a symmetric range $[\overline {a}_{ij}-\widehat {a}_{ij},\overline {a}_{ij}+\widehat {a}_{ij}]$, where $\overline {a}_{ij}$ is the nominal value and $\widehat {a}_{ij}\geq 0$ its deviation. A random variable of deviation can be introduced as $\tau _{ij}=(a_{ij}-\overline {a}_{ij})/\widehat {a}_{ij}$, τ_ij takes values in [− 1, 1]. The decisions variables are assumed to be nonnegative. Hence, the worst case will be achieved at the right-hand side of the range $[\overline {a}_{ij}-\widehat {a}_{ij},\overline {a}_{ij}+\widehat {a}_{ij}]$. Therefore, the random variable τ is assumed to be positive (0 ≤ τ_i ≤ 1). The confidence range $[\overline {a}_{ij}-\widehat {a}_{ij},\overline {a}_{ij}+\widehat {a}_{ij}]$ does not have to be symmetric. For every i a parameter ∇_i is introduced. This parameter is the sum of the total deviations of the nominal values of the uncertain coefficients in the same constraint i. This parameter is called “the budget of robustness”; its role is to protect the constraint against uncertainty and to adjust the robustness of the method against the degree of conservatism. This parameter is not necessarily an integer but takes values in $[0,card(J^{\prime }_{i})]$; if the parameter is zero no deviation is allowed on the coefficients of the i^th constraint and this case is the deterministic case, whereas, if ∇_i is equal to $card(J^{\prime }_{i})$ all the parameters are likely to deviate and this case is the one considered in [93].

We consider the following nonlinear formulation of constraint Eq. 58:

$$ \sum\limits_{j=1}^{n} \overline{a}_{ij} x_{ij}+\beta_{i}(x^{*},\nabla_{i}) \leq b_{i} \qquad \forall i $$

(60)

where:

$$ \begin{array}{@{}rcl@{}} \beta_{i}(x^{*},\nabla_{i})=\underset{\{S^{\prime}_{i}\cup \{t_{i}\}|S^{\prime}_{i}\subseteq J^{\prime}_{i}, card(S^{\prime}_{i})=\left\lfloor\nabla_{i}\right\rfloor, t_{i}\in J^{\prime}_{i}\setminus S^{\prime}_{i}\}}{\max} \left\{{\sum\limits_{j\in S^{\prime}_{i}}\widehat{a}_{ij} x_{j}^{*}+(\nabla_{i}-\left\lfloor\nabla_{i}\right\rfloor)\widehat{a}_{it_{i}} x_{j}^{*}}\right\} \end{array} $$

(61)

The formulation Eq. 61 is the protection function of constraint i. The protection function protects the left-side of the inequality to be lower than b_i for different values of a_ij; the protection function is defined for every constraint with uncertain coefficient. It is an optimization problem in itself; it depends on the protection level ∇_i; when ∇_i = 0, then β_i = 0 and the problem is deterministic [79].

In the following formulation, the protection function is transformed into an optimization problem; the formulation Eq. 61 can be replaced by the following linear problem:

$$ \max \sum\limits_{j \in J^{\prime}_{i} }\widehat{a}_{ij}x_{j}^{*}w_{ij} $$

(62)

subject to:

$$ \sum\limits_{j \in J^{\prime}_{i}} w_{ij}\leq \nabla_{i} $$

(63)

$$ 0 \leq w_{ij} \leq 1 \qquad \forall j\in J^{\prime}_{i} $$

(64)

$x_{j}^{*}$ is not variable in the problem, w_ij is the new variable corresponding to τ_ij described below, to prove the equivalence of problems Eq. 61 and Eqs. 62-64, the optimal solution value of problem Eqs. 62-64 consists of $\left \lfloor \nabla _{i}\right \rfloor$ variables at 1 and one variable at $\nabla _{i}-\left \lfloor \nabla _{i}\right \rfloor$, it is equivalent to selecting a subset : ${\{S^{\prime }_{i}\cup \{t_{i}\}|S^{\prime }_{i}\subseteq J^{\prime }_{i}, t_{i}\in J^{\prime }_{i}\setminus S^{\prime }_{i}, card(S^{\prime }_{i})=\left \lfloor \nabla _{i}\right \rfloor }\}$ with the corresponding objective value ${\sum }_{j\in S^{\prime }_{i}}\widehat {a}_{ij} x_{j}^{*}+(\nabla _{i}-\left \lfloor \nabla _{i}\right \rfloor )$ $\widehat {a}_{it_{i}} {x}_{j}^{*}$ [18].

The model Eqs. 62-64 is nonlinear when x is considered as variable, nonetheless, by using its duality, it can be linearly expressed. By strong duality, since problem Eq. 62-64 is feasible and bounded for all ∇_i, then the duality is also feasible and bounded:

$$ \min \nabla_{i}z_{i}+\sum\limits_{j \in J^{\prime}_{i}} p_{ij} $$

(65)

subject to:

$$ z_{i}+p_{ij}\geq \widehat {a}_{ij}x_{j}^{*} \qquad \forall j \in J^{\prime}_{i} $$

(66)

$$ p_{ij} \geq 0 \qquad \forall j\in J^{\prime}_{i} $$

(67)

$$ z_{i} \geq 0 $$

(68)

Finally, we replace the protection function with the dual model Eqs. 65-68, then, the robust model is as follows:

$$ \max \sum\limits_{j=1}^{n}c_{j} x_{j} $$

(69)

subject to:

$$ \sum\limits_{j=1}^{n} \overline{a}_{ij} x_{j}+ z_{i}\nabla_{i}+\sum\limits_{j \in J^{\prime}_{i}} p_{ij} \leq b_{i} \qquad \forall i $$

(70)

$$ z_{i}+p_{ij} \geq \widehat{a}_{ij}x_{j} \qquad \forall i,j\in J^{\prime}_{i} $$

(71)

$$ x_{j} \geq 0 \qquad \forall j $$

(72)

$$ p_{ij} \geq 0 \qquad \forall i,j\in J^{\prime}_{i} $$

(73)

$$ z_{i} \geq 0 \qquad \forall i $$

(74)