1 Introduction

The private healthcare has been in a continual growth over recent years. Indeed, more people are now using private healthcare facilities rather than public, though the costs in the latter are much more affordable. Moreover, medical tourism is thriving, and patients are travelling from developed countries (largely from the United States, Canada, and Western Europe) to less developed ones mainly in Asia and Latin America for reduced-wait time and/or high-quality medical care at affordable prices [1].

To meet this growing demand, many private healthcare facilities have emerged and global competition is strengthened. In this context, private healthcare facilities increasingly strive for optimising their resource utilisation and thus improving their care services quality while increasing their profits. For that aim, they usually focus on the optimization of the most cost-intensive and productive unit: the operating theatre.

In practice, there are two types of surgery operations: elective operations that are planned in advance, and non-elective or emergency operations that arrive unexpectedly and need to be performed urgently. In both cases, patients can be hospitalized for either less than 24 h (called outpatients) or several days (called inpatients).

Unlike the public sector where surgeons work for a specific hospital, in the private sector, surgeons are independent service providers and may refer their patients to several private healthcare facilities. Thus, to increase the clinic workload, surgeon’s dependent processes have to be facilitated (e.g., surgery scheduling processes) [2].

In this paper, we investigate the Integrated Elective Surgery-Scheduling Problem (IESSP) that arises in a privately operated healthcare facility. Moreover, we consider the entire surgery process that comprises the following three phases [3, 4]:

  • The pre-operative phase: It commonly includes patients’ admission and allows performing tests, preoperative fasting, patient preparation, etc.

  • The per-operative phase: It begins when the patient is transferred to the operating theatre and covers her/his stay there until her/his transfer to the corresponding hospital bed. During this phase, surgery operation and recovery care are performed.

  • The post-operative phase: It refers to the management of the patient cares after a surgery. It starts when the patient is transferred to her/his hospital bed and lasts until she/he leaves it.

The contribution of this paper is twofold:

  1. 1.

    The integration of the hospital beds management within the daily operating theatre scheduling problem: Most previous research focus on the operating theatre scheduling in the context of public healthcare hospitals. They consider diverse human and material resource constraints related to the operating theatre but do not consider hospital ward capacity. Consequently, the generated schedules may be infeasible when the beds are scarce resources as patients may not be admitted for bed shortage. Thus, the hospital ward should be managed efficiently together with the operating room scheduling to increase the number of accepted surgical cases and reduce the number of refused admissions. In the private context, managing the hospital beds and the operating theatre simultaneously is becoming compulsory since it may increase their profits and improve the quality of their services for both patients and surgeons.

  2. 2.

    The development of effective and flexible MILP models to solve exactly the IESSP: The scheduling problem is known to be NP-hard and is commonly solved using approximate methods or sophisticated exact approaches. In this paper, we develop two effective mixed integer linear models that can be efficiently solved to optimality using a commercial software package without requiring the implementation of tailored and sophisticated algorithms. The first model is a network-flow MILP that uses the same variable to express the two problem decisions: patient sequencing and resource assignment. The second model is an assignment based MILP that defines two different variables that express these two decisions separately. Moreover, the proposed models are flexible and can be readily modified to accommodate several extensions. Thus, they may open the door for the development of new efficient solution methodologies to model uncertainty and robustness features in healthcare scheduling problems.

This paper is organized as follows: Section 2 presents a review of the literature pertaining to the surgery-scheduling problem. Section 3 describes the considered integrated elective surgery-scheduling problem. Section 4 introduces two mixed integer linear models and provides some extensions. In Section 5, computational experiments are presented and discussed. Finally, Section 6 draws conclusions and gives some perspective topics.

2 Literature review

Patient and healthcare-resource planning and scheduling problems have been extensively studied and referenced in traditional Operational Research journals during these last decades. In particular, operating theatre has deserved special attention since it is considered to be the main engine of the hospital.

Two major optimization problems are addressed: (1) operating room planning (ORP), also called advanced scheduling that consists on assigning a surgery date to patients, and (2) operating room scheduling (ORS), also called allocation scheduling that deals with the assignment of patients to operating rooms and their sequencing.

More specifically, according to the operating theatre resource management strategy, three different surgery management procedures have been studied [5]:

  • Block scheduling: A preliminary timetable called master schedule is established in order to allocate time slots to surgeons, groups of surgeons or medical specialties.

  • Open scheduling: Patients are scheduled without any specialty related restriction.

  • Modified block scheduling: It is an intermediate strategy that combines the block and open scheduling strategies.

In the literature, the operating room planning and scheduling problems are addressed jointly or separately. In the former case, the two problems are usually considered in a sequential manner using two-phase approaches [5–8]. In the first phase, mathematical formulations are proposed for the ORP problem and in the second phase, heuristic approaches are devised for the ORS problem. In more recent research works, the operating room planning and scheduling problems are addressed simultaneously [9–12]. For a recent review, refer to Cardoen et al. [13] and Francesca and Rosita [14].

The operating room scheduling is a common problem in healthcare sector. Different variants have been investigated, dealing with divers human and material resources (i.e. recovery beds, porters, nurses, etc.) in order to meet specific requirements of the real world healthcare systems. However, this problem is known to be very difficult to solve, especially for real size instances, and most of the papers propose tailored-heuristic approaches.

Guinet and Chaabane [6] develop an extended version of the Hungarian method to assign patients to operating rooms on a medium term. They consider operating rooms and recovery beds. In Fei et al. [5, 7], the daily ORS deals with the availability of operating rooms and recovery beds under respectively open and block scheduling strategies. The problem is modeled as a flow shop-scheduling problem and then solved using a hybrid genetic algorithm. Jebali et al. [8] describe a heuristic approach that solves the ORS problem while considering operating rooms, recovery beds and Intensive Care Unit.

Pariente et al. [15] derive an exact solution for the daily ORS problem in a block scheduling system. They propose a MILP that accounts for the availability of both operating rooms and surgeons, while maximizing the number of treated patients during the planning horizon.

Xiang et al. [4], Guoet et al. [16], and Beliäen and Demeulemeester [17] develop an integrated approach for building nurse and surgery schedules. They model the problem using integer programming and derive solutions using ant colony approach, genetic algorithm and branch-and-price algorithm respectively.

Cardoen et al. [18] consider operation rooms and recovery beds’ availability as well as instruments’ availability, patients’ priority and surgeons’ preferences. They formulate the problem as a multi-objective MILP and solve it using a branch-and-price-based approach. In the same vein, Meskens et al. [19] investigate a similar problem where instruments’ availability is replaced by surgical team affinities and availability. They model and solve the problem using a constraint programming approach. This same variant of the ORS is studied later by Wang et al. [20]. The authors develop and compare two models using MILP and constraint programming respectively. Augusto et al. [21] study the transfer of patients between hospital beds and operating rooms, the cleaning activities of operating rooms as well as the surgery and the recovery activities. They propose a nonlinear mathematic formulation that they solve using a Lagrangian relaxation-based method. Zhao and Li [22] investigate the operating room availability and the sequence-dependent setup times between surgeries. They describe and compare two programs: a mixed integer nonlinear program (MINLP) and a constraint program.

Recently, stochastic optimization started to emerge to address uncertainty issues. Min and Yih [23] study the elective surgery-scheduling problem with uncertain surgery operations (surgery durations, surgical intensive care unit availability) over multi-periods. They propose a stochastic MILP that minimizes patient costs and expected overtime costs. The problem is then solved using a sampling-based approach. Wang et al. [24] consider uncertain surgery durations and emergency demands. They present an integer-programming problem that minimizes the total expected operating cost including fixed costs related to the number of open operating rooms and expected costs of variable overtime. A column-generation-based heuristic algorithm is devised to solve the problem.

Hans et al. [25] propose constructive and local search heuristics to solve the robust surgery-scheduling problem in block scheduling strategy. The objective is to improve operating room scheduling and reduce the risk of overtime and thus patients’ cancellation.

In public healthcare facilities, dynamic generation of patient schedules having various priorities is modelled by Patrick et al. [26] as a Markov decision process. The model is solved using approximate dynamic programming and the solutions quality is analysed through simulation.

Simulation approaches have been investigated for the ORS problem. Persson and Persson [27] address the patient surgery scheduling problem at a hospital in Sweden under specific medical, economic and time constraints. To prevent long queues, patients are allowed to be scheduled at other hospitals according to the Swedish health policy. The authors develop a hybrid simulation and integer-programming approach for solving the problem. Simulation is also used in Patrick and Puterman [28] to improve resource utilization for diagnostic services through flexible inpatient scheduling. López et al. [29] and Prudtikul and Pathomsiri [30] adopt simulation models to analyse the impact of various improvement strategies. Saremi et al. [31] propose three simulation-based tabu search methods for outpatient scheduling in operating theatre with stochastic service times.

To the best of our knowledge, hospital bed capacity constraints are not yet considered when solving ORS problem although they have crucial impact on the number of operated surgery cases and consequently on the hospital profit. However, some research works deal with the hospital bed-planning problem that assigns beds to patients. Wang et al. [32] investigate the bed allocation problem and implement a dynamic dispatching approach. They maximize the hospitalization profit and minimize the bed supplementing cost with both acute and ordinary inpatients. Thompson et al. [33] study a practical bed-planning problem and present an admission decision support system based on finite-horizon Markov decision process model. They implement their system for a hospital ward and prove to bring significant revenue. Ben Bachouch et al. [34] present a decision support tool based on an integer linear model for hospital bed planning with various constraints (incompatibility between pathologies, segregated rooms, continuity of care, etc.). Holm et al. [35] describe a discrete event simulation approach for the allocation of hospital beds in order to minimize crowding. They also develop optimization algorithms for analyzing the simulation model output based on prevalence and incidence of crowding bed usage.

We notice that the literature pertaining to surgery scheduling focuses on the operating theatre and its human and material resources management. However, there is no previous work that considers the entire surgery process. Moreover, most developed approaches are approximate in nature and literature about exact methods is scarce. In this paper, we build an integrated surgery schedule that takes into account hospital beds, operating rooms and recovery beds. We propose two effective MILP that can be solved to optimality in a reasonable computation time using a commercial software package.

3 Problem statements

The Integrated Elective Surgery-Scheduling Problem consists on sequencing a fixed number of patients and assigning them to resources, over a 1 day period, while considering pre-operative, per-operative and post-operative phases.

In the pre-operative phase, ward admission is performed and patients are assigned to hospital beds. In the per-operative phase, patients are transferred to the operating theatre where they are assigned to operating rooms and then to recovery beds. Finally, in the post-operative phase, patients return to the hospital beds.

A specific feature of the private healthcare sector is that surgeons are independent service providers and are not engaged by the healthcare facility. Consequently, patients choose their surgeon and decide together where and when the surgery will be performed. Thus, when scheduling surgeries, the availability of surgeons and their preferences regarding the day and the time of their surgeries, should be taken into account.

Moreover, in a private healthcare facility, most patients do not need staying for a long period at the hospital ward and thus most of them are outpatients or inpatients requiring only one overnight stay.

Furthermore, the hospital ward is usually composed of single-bed rooms available in a limited number. Consequently, the assignment of patients to hospital beds does not require the integration of the commonly handled incompatibility constraints between man and women, pathologies, etc. Besides, in order to optimize the use of these beds, patients may be assigned to different rooms in the pre-operative and post-operative phases, which allows the use of their rooms by other patients when they are in the operating theatre. However, additional rooms’ cleaning and disinfection operations will be required.

In order to optimise the surgery process resources and to shorten the patient’s waiting time in the healthcare facility, the patients’ average length of stay is minimized. However, an optimal solution may schedule outpatients in the evening and inpatients in the morning, leading more patients to stay overnight in the healthcare facility. Consequently, less beds will be available for the next day activity and surgeries may be cancelled for beds shortage. To overcome this drawback, we investigate the minimization of patients’ overnight stays. Indeed, this may schedule outpatients early in the day so less patients are likely to stay overnight in the healthcare facility and thus more free beds will be available for the next day activity.

In this study, we consider small to medium-sized private healthcare facilities where most cases are outpatients. Moreover, we make the following assumptions:

  • Emergency cases are not taken into account;

  • Human and instruments resources are always available whenever they are needed;

  • The operating theatre comprises identical multifunctional rooms without any specialty’s restriction. Therefore, the open scheduling strategy is adopted;

  • The surgery operation time, the recovery time and the length of stay before and after the surgery are known in advance, although they are subject to uncertainties in practice;

  • The surgery operation time comprises the time for preparing the patient (e.g., anaesthesia) in the operating room as well as the surgical act time;

  • Each patient is associated to a specific surgeon;

  • The availability of each surgeon is known in advance. It is expressed through a time-window during which the surgeon is available at the healthcare facility;

  • The operating theatre is open all day (24 h/24 h);

  • The hospital ward is composed of single-bed rooms available in a limited number.

This problem can be modelled as a three-stage hybrid flow shop-scheduling problem that uses four different resources (see Fig. 1): Hospital beds, operating rooms, surgeons and recovery beds. Furthermore, the problem exhibits the following additional features:

Fig. 1
figure 1

Patient’s flow through the surgery process

Full size image

  • Patients flow recirculation: patients can be assigned to different hospital rooms in the pre-operative and post-operative phases. Thus, resources of the hospital ward (Stage 1) are used twice through the surgery process;

  • Resource synchronization: In the operating room (Stage 2), the surgery operation requires two different resources simultaneously: operating rooms and surgeons;

  • Dedicated resources: Each patient is operated by a pre-assigned surgeon who referred her/him to the healthcare facility;

  • Blocking constraints: There is no buffer between stages. Resources of a stage remain blocked even when the required cares are completed until resources of the next stage become available.

According to [36], the two stage-hybrid flow shop-problem with one machine in the first stage and two or more machines in the second stage is an NP-hard problem in the strong sense. Thus, our problem is NP-hard in the strong sense as well.

Throughout the past three decades, several works have dealt with the hybrid flow shop-scheduling problem, leading to the development of exact and approximate methods. We refer the lecture to [37] for a comprehensive survey.

However, quite a few papers have been interested in the hybrid flow shop-scheduling problem with recirculation. Bertel and Billaut [38] present an industrial scheduling problem that they model as a three-stage hybrid flow shop-problem with recirculation. They develop a liner program and a genetic algorithm for its solution. Boudhar and Meziani [39] consider a two-stage hybrid flow shop-problem with one machine in the first stage and two identical parallel machines in the second stage. Jobs can be recirculated a fixed number of times in the second stage. They propose a linear program and several heuristics to solve it.

Similarly, few researches investigate scheduling problems with dedicated machines. Lin and Liao [40] consider a two-stage hybrid flow shop-problem with sequence-dependent setup times in stage 1, dedicated machines in stage 2 and due date constraints. They develop heuristics that minimize the weighted maximal tardiness time. Yang [41] propose a new complexity proof of the two-stage hybrid flow shop-scheduling problem with dedicated machines in stage 2. He shows that the problem is unary NP-complete.

In this paper, we present two mixed integer linear programs for the IESSP modelled as a three-stage hybrid flow shop-problem with recirculation, resource synchronization, dedicated machines and blocking constraints.

4 MILP formulations

Prior to presenting the two MILP formulations, we introduce the following notation.

4.1 Notation

In order to take into account the recirculation on the hospital ward (Stage 1), we duplicate it into two separate stages denoted by Stage 1 and Stage 4. We also duplicate its resources into two sets: R 1 and R 4 that correspond to hospital rooms assigned before and after surgeries, respectively.

Moreover, for a better understanding of the model, we define an extra stage for the surgeons, denoted by Stage 5.

Sets:

I :

set of stages indexed by i and i’, I = {1, 2, …, 5}

S :

set of surgeons, indexed by s

J :

set of patients, indexed by j and k

J s :

set of patients associated to surgeon s∈S, J s  ⊂ J

R i :

set of available resources at Stage i, indexed by l. We notice here that R 1  = R 4 and R 5  = S.

Data:

p ij :

time to provide care at Stage i to patient j.

Tstart s and Tfinish s :

the earliest start time and the latest finish time for surgeon s∈S to perform surgeries, respectively. They express the availability and/or the time preferences of surgeon s∈S. These time limits can be further specified for each patient j∈J s if necessary. In this case, we define Tstart sj and Tfinish sj as the earliest start time and the latest finish time for surgeon s∈S to operate patient j∈J s , respectively.

M :

a big positive value.

4.2 Network-flow model

The first model is a network-flow MILP that uses the same variable X to express the decisions related to patient sequencing and assignment to resources. The decision variables are defined as follows:

X ijk :

equals 1 if in Stage i, a same resource is assigned to patient k immediately after patient j, and 0 otherwise.

Xs ilj :

equals 1 if patient j is the first patient assigned to resource l of Stage i, and 0 otherwise.

Xt ij :

equals 1 if patient j is the last patient assigned to a resource in Stage i, and 0 otherwise.

Q 14 jk :

equals 1 if a same clinic room is assigned to patient k at Stage 4, after her/his surgery operation, immediately after patient j who is still in Stage 1, and 0 otherwise.

Q 41 jk :

equals 1 if a same clinic room is assigned to patient k in Stage 1, before her/his surgery operation, immediately after patient j who is in Stage 4, and 0 otherwise.

T ij :

expresses the arrival time of patient j at Stage i.

d ij :

defines the blocking/waiting time of patient j at Stage i.

Using these definitions, the network-flow mixed-integer program (NF_MILP) can be written as follows.

$$ \mathrm{N}\mathrm{F}\_\mathrm{MILP}:\mathrm{Minimise}\ \frac{1}{\left|J\right|}{\displaystyle \sum_j}\left({T}_{4j}+{p}_{4j}-{T}_{1j}\right) $$
(1)

Subject to

$$ \begin{array}{cc}\hfill {\displaystyle \sum_{l\in {R}_1}}X{s}_{1lk}+{\displaystyle \sum_{j\in J\backslash \left\{k\right\}}}{X}_{1jk}+{\displaystyle \sum_{j\in J\backslash \left\{k\right\}}}{Q}_{jk}^{41}=1\hfill & \hfill \forall\ k\in J\hfill \end{array} $$
(2)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{l\in {R}_4}X{s}_{4lk}}+{\displaystyle \sum_{j\in J\backslash \left\{k\right\}}X{s}_{4jk}}+{\displaystyle \sum_{j\in J}{Q}_{jk}^{14}}=1\hfill & \hfill \forall k\in J\hfill \end{array} $$
(3)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{l\in {R}_i}X{s}_{ilk}}+{\displaystyle \sum_{j\in J\backslash \left\{k\right\}}{X}_{ijk}}=1\hfill & \hfill \forall i\in \left\{2,3\right\},k\in J\hfill \end{array} $$
(4)
$$ \begin{array}{cc}\hfill X{s}_{5sk}+{\displaystyle \sum_{j\in {J}_s\backslash \left\{k\right\}}{X}_{5jk}}=1\hfill & \hfill \forall s\in S,k\hfill \end{array}\in {J}_s $$
(5)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{k\in J\backslash \left\{j\right\}}{X}_{1jk}}+{\displaystyle \sum_{k\in J}{Q}_{jk}^{14}}+X{t}_{1j}=1\hfill & \hfill \forall j\in J\hfill \end{array} $$
(6)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{k\in J\backslash \left\{j\right\}}{X}_{4jk}}+{\displaystyle \sum_{k\in J\backslash \left\{j\right\}}{Q}_{jk}^{41}}+X{t}_{4j}=1\hfill & \hfill \forall j\in J\hfill \end{array} $$
(7)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{k\in J\backslash \left\{j\right\}}{X}_{ijk}}+X{t}_{ij}=1\hfill & \hfill \forall i\in \left\{2,3\right\},j\in J\hfill \end{array} $$
(8)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{k\in {J}_s\backslash \left\{j\right\}}{X}_{5jk}}+X{t}_{5j}=1\hfill & \hfill \forall s\in S,j\in {J}_s\hfill \end{array} $$
(9)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{j\in J}X{s}_{ilj}}\le 1\hfill & \hfill \forall i\in I\backslash \left\{1,4\right\},l\in {R}_i\hfill \end{array} $$
(10)
$$ \begin{array}{cc}\hfill {\displaystyle \sum_{j\in J}}X{s}_{1lj} + {\displaystyle \sum_{j\in J}}X{s}_{4lj}\le 1\ \hfill & \hfill \forall\ l\in {R}_{1\ }\hfill \end{array} $$
(11)
$$ \begin{array}{cc}\hfill {T}_{2j}-{T}_{1j}={p}_{1j}+{d}_{1j}\hfill & \hfill \forall j\in J\hfill \end{array} $$
(12)
$$ \begin{array}{cc}\hfill {T}_{2j}={T}_{5j}\hfill & \hfill \forall\ j\in J\hfill \end{array} $$
(13)
$$ \begin{array}{cc}\hfill {T}_{3j}-{T}_{2j}={p}_{2j}+{d}_{2j}\hfill & \hfill \forall j\in J\hfill \end{array} $$
(14)
$$ \begin{array}{cc}\hfill {T}_{4j}-{T}_{3j}={p}_{3\mathrm{j}}+{d}_{3j}\hfill & \hfill \forall j\in J\hfill \end{array} $$
(15)
$$ \begin{array}{cc}\hfill M\left(1-{Q}_{jk}^{14}\right)+{T}_{4k}-{T}_{1j}\ge {p}_{1j} + {d}_{1j}\hfill & \hfill \forall j\in J,k\in J\hfill \end{array} $$
(16)
$$ \begin{array}{cc}\hfill M\left(1-{Q}_{jk}^{41}\right)+{T}_{1k}-{T}_{4j}\ge {p}_{4j} + {d}_{4j}\hfill & \hfill \forall j\in J,k\in J,\ \mathrm{j}\ne \mathrm{k}\ \hfill \end{array} $$
(17)
$$ \begin{array}{cc}\hfill M\left(1-{X}_{ijk}\right)+{T}_{ik}-{T}_{ij}\ge {p}_{ij}+{d}_{ij}\hfill & \hfill \forall i\in \mathrm{I}\backslash \left\{5\right\},j\in J,k\in J\hfill \end{array} $$
(18)
$$ \begin{array}{cc}\hfill M\left(1-{X}_{5jk}\right)+{T}_{5k}-{T}_{5j}\ge {p}_{5j}\hfill & \hfill \forall j\in J,k\in J,\ \mathrm{j}\ne \mathrm{k}\hfill \end{array} $$
(19)
$$ \begin{array}{cc}\hfill {T}_{5j}\kern0.5em \ge Tstar{t}_s\hfill & \hfill \forall s\in S,j\in {J}_s\hfill \end{array} $$
(20)
$$ \begin{array}{cc}\hfill {T}_{5j} + {p}_{5j}\le Tfinis{h}_s\hfill & \hfill \forall s\in S,j\in {J}_s\hfill \end{array} $$
(21)
$$ \begin{array}{cc}\hfill {T}_{4j}\le 1440\hfill & \hfill\ \forall j\in J\hfill \end{array} $$
(22)
$$ \begin{array}{cc}\hfill {T}_{ij}\ge 0\hfill & \hfill \forall i\in I,j\in J\hfill \end{array} $$
(23)
$$ \begin{array}{cc}\hfill {d}_{ij}\ge 0\hfill & \hfill \forall i\in I,j\in J\hfill \end{array} $$
(24)
$$ \begin{array}{cc}\hfill {X}_{ijk}\in \left\{0,\ 1\right\}\hfill & \hfill\ \forall i\in I,j\in J,\ k\in J, \mathrm{j}\ne \mathrm{k}\hfill \end{array} $$
(25)
$$ \begin{array}{cc}\hfill X{s}_{ilj}\in \left\{0,\ 1\right\}\hfill & \hfill \forall i\in I,l\in {R}_i,j\in J\hfill \end{array} $$
(26)
$$ \begin{array}{cc}\hfill X{t}_{ik}\in \left\{0,\ 1\right\}\hfill & \hfill \forall i\in I,\ k\in J\hfill \end{array} $$
(27)
$$ \begin{array}{cc}\hfill {Q}_{jk}^{14}\in \left\{0,\ 1\right\}\hfill & \hfill \forall j\in J,k\in J\hfill \end{array} $$
(28)
$$ \begin{array}{cc}\hfill {Q}_{jk}^{41}\in \left\{0,\ 1\right\}\hfill & \hfill \forall j\in J,k\in J,\mathrm{j}\ne \mathrm{k}.\hfill \end{array} $$
(29)

The objective function (1) minimises the patients’ average length of stay in the private healthcare facility. The number of patients’ overnight stays minimization will be discussed in Section 4.4.

Equations (2–9) are network-flow conservation constraints and guarantee that all patients are assigned to exactly one resource at each stage (see Figs. 2, 3, and 4).

Fig. 2
figure 2

Patients’ schedule at a hospital room: Constraints (16)

Full size image
Fig. 3
figure 3

Patients’ schedule at a hospital room: Constraints (17)

Full size image
Fig. 4
figure 4

Patients’ schedule at the hospital ward

Full size image

For the hospital ward, Constraints (2) require that each patient \( k\in J \) at the pre-operative phase (Stage 1) is either the first patient assigned to a specific resource \( \left({\displaystyle {\sum}_{l\in {R}_1}X{s}_{1lk}=1}\right) \), or has exactly one predecessor assigned to the same resource. This predecessor can be a patient at the per-operative phase (∑ j ∈ J\{k} X 1jk  = 1) or at the post-operative phase (∑ j ∈ J\{k} Q 41 jk  = 1). Constraints (3) impose similar restrictions for patients at the post-operative phase (Stage 4). Indeed, each patient \( k\in J \) at this stage is the first assigned to a specific resource \( \left({\displaystyle {\sum}_{l\in {R}_4}X{s}_{4lk}=1}\right) \), or has exactly one predecessor assigned to the same resource while being at the per-operative phase (∑ j ∈ J\{k} Q 14 jk  = 1) or at the post-operative phase (∑ j ∈ J\{k} X 4jk  = 1). Constraints (4) and (5) deal with Stages 2, 3 and 5 where each patient k ∈ J is either the first assigned to a specific resource or has exactly one predecessor assigned to the same resource.

Similarly, constraints (6–9) ensure that, at each stage, each patient is the last assigned to a resource or has exactly one successor assigned to the same resource.

Constraints (10) and (11) specify that each available resource be assigned to at most one first patient.

Constraints (12–15) link the start time of performing care to a patient at a specific stage, with her/his release time from the previous stage and the corresponding blocking time. Constraints (13) impose resource synchronisation at Stage 2 (operating rooms) and Stage 5 (surgeons) since they must be used simultaneously.

Constraints (16–19) prevent the overlapping of cares performed by a same resource to different patients.

Constraints (20) and (21) express the availability/preferences of each surgeon and Constraints (22) ensure that surgeries are performed in 1 day. Constraints (23–29) define the domains of the decision variables.

Figure 2 illustrates Constraints (16) imposed on the hospital ward (i.e. Stages 1 and 4). It shows that, if a same resource is assigned to patient k at the post-operative phase (i.e. Stage 4) immediately after patient j at the pre-operative phase (i.e. Stage 1) then variable \( {Q}_{jk}^{14} \) is set to 1 and constraint \( {T}_{4k}-{T}_{1j}\ge {p}_{1j}+{d}_{1j} \) holds.

Similarly, Fig. 3 illustrates Constraints (17). It shows that, if a same resource is assigned to patient k at the pre-operative phase (i.e. Stage 1) immediately after patient j at the post-operative phase (i.e. Stage 4) then variable Q 41 jk is set to 1 and constraint T 1k  − T 4j  ≥ p 4j  + d 4j holds.

In order to better explain patients sequencing and assignment to the hospital ward resources, we consider an example with 3 patients and 2 hospital rooms. Figure 4 presents a Gantt chart that illustrates a feasible patients’ schedule satisfying Constraints (2–3); (6–7) and (11).

In this example, non-zero decision variables related to patients’ sequencing and assignment in the hospital ward (Stage 1 and Stage 4) have the following values:

$$ \begin{array}{l}\mathrm{F}\mathrm{o}\mathrm{r}\;\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{m}\;1:X{s}_{113}=1,{X}_{132}=1,{Q}_{23}^{14}=1,X{t}_{43}=1.\hfill \\ {}\mathrm{F}\mathrm{o}\mathrm{r}\;\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{m}\;2:X{s}_{422}=1,{Q}_{21}^{41}=1,{Q}_{11}^{14}=1,X{t}_{41}=1.\hfill \end{array} $$

Each hospital room is assigned to a sequence of patients and each patient is assigned to one resource at the pre-operative phase and one resource at the post-operative phase.

4.3 Assignment model

The second model is an assignment-based MILP that extends the “standard” mathematical programming formulation of the hybrid flow shop-scheduling problem. Unlike the network-flow model (NF_MILP) where X variables express both patients’ sequencing and assignment to resources, the assignment-based model uses two different variables Y and W for these two decisions respectively, defined as follows:

Y ii ′ jk :

equals 1 if patient k in Stage i’ is scheduled after patient j in Stage i, and 0 otherwise where (i, i’) ∈ {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 4), (4, 1)}.

W ijl :

equals 1 if resource l of Stage i is assigned to patient j, and 0 otherwise

T ij :

expresses the arrival time of patient j at Stage i

d ij :

defines the blocking/waiting time of patient j at Stage i.

We notice here that X variables require consecutive patients to be served immediately one after the other by a same resource of a stage whereas Y variables are limited to the order of serving two patients in a specific stage. More specifically, X ijk equals one when a same resource is assigned to patient k immediately after patient j in Stage i, while \( {\boldsymbol{Y}}_{\boldsymbol{jk}}^{\boldsymbol{ii}} \) equals one when patient k is scheduled after patient j (and not necessarily immediately after patient j nor being served by a same resource) in Stage i.

Using these definitions, the assignment-based model (A_MILP) can be written as follows.

$$ \mathrm{A}\_\mathrm{MILP}:\mathrm{Minimise}\kern1em \frac{1}{\left|J\right|}{\displaystyle \sum_j}\left({T}_{4j}+{p}_{4j} - {T}_{1j}\right) $$
(30)

Subject to

(12–15), (20–24)

$$ \begin{array}{cc}\hfill {\displaystyle \sum_{l{R}_i}}{W}_{ijl}=1\ \hfill & \hfill \forall\ i\in I\backslash \left\{5\right\},\ j\in J\hfill \end{array} $$
(31)
$$ \begin{array}{cc}\hfill {W}_{5js}=1\hfill & \hfill \forall s\in S,j\in {J}_s\hfill \end{array} $$
(32)
$$ \begin{array}{cc}\hfill {T}_{ik}\ge {T}_{ij}+{p}_{ij}+{d}_{ij} - \mathrm{M} \times \left(1-{Y}_{jk}^{ii}\right)-\mathrm{M}\times \left(1-{W}_{ijl}\right)-\mathrm{M} \times \left(1-{W}_{ikl}\right)\hfill & \hfill \forall i\in I\backslash \left\{5\right\},\ l\in {R}_i,\ j\in J,k\in J,j\ne k\hfill \end{array} $$
(33)
$$ \begin{array}{cc}\hfill {T}_{5k}\ge {T}_{5j}+{p}_{5j}-\mathrm{M}\times \left(1-{Y}_{jk}^{55}\right)\hfill & \hfill \forall\ s\in S,j\in {J}_s,k\in {J}_s,j\ne k\hfill \end{array} $$
(34)
$$ \begin{array}{cc}\hfill {T}_{1k}\ge {T}_{4j}+{p}_{4j}+{d}_{4j}-\mathrm{M} \times \left(1-{Y}_{jk}^{41}\right) - \mathrm{M}\times \left(1-{W}_{1 kl}\right) - \mathrm{M}\times \left(1-{W}_{4jl}\right)\hfill & \hfill \forall\ l\in {R}_1,j\in J,k\in J,j\ne k\hfill \end{array} $$
(35)
$$ \begin{array}{cc}\hfill {T}_{4k}\ge {T}_{1j}+{p}_{1j}+{d}_{1j}-\mathrm{M} \times \left(1-{Y}_{jk}^{14}\right) - \mathrm{M}\times \left(1-{W}_{1 kl}\right)-\mathrm{M}\times \left(1-{W}_{4jl}\right)\hfill & \hfill \forall\ l\in {R}_1,\ j\in J,k\in J\hfill \end{array} $$
(36)
$$ \begin{array}{cc}\hfill {Y}_{jk}^{ii}+{Y}_{kj}^{ii}=1\hfill & \hfill \forall i\in I,\ j\in J,\ k\in J,j\ne k\hfill \end{array} $$
(37)
$$ \begin{array}{cc}\hfill {Y}_{jk}^{14}+{Y}_{kj}^{41}=1\hfill & \hfill \forall i\in I,\ j\in J,k\in J,j\ne k\hfill \end{array} $$
(38)
$$ \begin{array}{cc}\hfill {W}_{ijl}\in \left\{0,\ 1\right\}\hfill & \hfill \forall i\in I,l\in {R}_i,j\in J\hfill \end{array} $$
(39)
$$ \begin{array}{cc}\hfill {Y}_{jk}^{ii\prime}\in \left\{0,\ 1\right\}\hfill & \hfill \forall j\in J,k\in J,\ i\in I,\ i^{\prime}\in I,j\ne k.\hfill \end{array} $$
(40)

The objective function (30) is the same as (1). It minimises the patients’ average length of stay in the private healthcare facility. Constraints (12–15) and (20–24) are those defined for NF_MILP model.

Constraints (31) and (32) ensure that at each stage, each patient is assigned to exactly one resource.

Constraints (33–36) are similar to Constraints (16–19) and prevent the overlapping of cares performed by a same resource to any two patients.

Constraints (37) and (38) express the sequencing constraints between each pair of patients at a same stage and expressions (39) and (40) are the integrality constraints to be imposed on the variables.

4.4 Extensions

In this section, we present some possible extensions to the proposed models that cope with further realistic features.

4.4.1 Minimizing the patients overnight stays

In order to have enough free hospital beds for the next day activity, the number of patients who spend the night in the hospital should be minimised.

In practice, outpatients have to leave the hospital ward before a fixed time limit T limo (e.g., 7 pm) on the surgery day, whereas the inpatients spend at least one night at the hospital and have to leave the ward before a fixed time limit T limi (e.g., noon) of the hospital discharge day. To account for this feature, we denote by J o the set of outpatients and by J i the set of inpatients.

The minimization of the patients’ overnight stays requires considering the objective function (41) and Constraints (42–44) in both models NF_MILP and A_MILP, where N j is a binary variable that equals 1 if outpatient j spends a night at the hospital ward or inpatient j spends more than one night at the hospital ward, and 0 otherwise.

$$ \mathrm{Minimize}\;{\displaystyle \sum_{j\in J\ }}{N}_j $$
(41)
$$ \begin{array}{cc}\hfill {T}_{4j}+{p}_{4j}\le {N}_j \times \mathrm{M}+{T}_{limo\ }\hfill & \hfill \forall j\in {J}_{o\ }\hfill \end{array} $$
(42)
$$ \begin{array}{cc}\hfill {T}_{4j}+{p}_{4j}\le {N}_j \times \mathrm{M}+{T}_{limi\ }\hfill & \hfill \forall j\in {J}_{i\ }\hfill \end{array} $$
(43)
$$ \begin{array}{cc}\hfill {N}_j\in \left\{0,\ 1\right\}\hfill & \hfill \forall j\in J\hfill \end{array} $$
(44)

4.4.2 Setup time sequence-dependent between surgeries

After each surgery, the operating room should be cleaned, disinfected and sterilized for the next surgery. Moreover, some surgeries need specific room preparation (e.g., installing specific equipment). These setup operations may depend on the sequence of surgery types.

To cope with this situation, for Stage 2 (operating rooms), Constraints (18) should be replaced by Constraints (45) in NF_MILP and Constraints (33) should be replaced by Constraints (46) in A_MILP.

$$ \begin{array}{cc}\hfill M\times \left(1-{X}_{2jk}\right)+{T}_{2k}-{T}_{2j}\ge {p}_{2j}+{d}_{2j}+{\alpha}_{jk}\hfill & \hfill \forall j\in J,k\in J,j\ne k\hfill \end{array} $$
(45)
$$ \begin{array}{cc}\hfill {\mathrm{T}}_{2\mathrm{k}}\ge {\mathrm{T}}_{2\mathrm{j}}+{\mathrm{p}}_{2\mathrm{j}}+{\mathrm{d}}_{2\mathrm{j}} + {\upalpha}_{\mathrm{jk}}-\mathrm{M}\times \left(1-{\mathrm{Y}}_{\mathrm{jk}}^{22}\right)-\mathrm{M}\times \left(1-{\mathrm{W}}_{2\mathrm{j}\mathrm{l}}\right)-\mathrm{M}\times \left(1-{\mathrm{W}}_{2\mathrm{k}\mathrm{l}}\right)\hfill & \hfill \forall l\in {R}_2,j\in J,k\in J,\ j\ne k\hfill \end{array} $$
(46)

where \( {\alpha}_{jk} \) is the setup time when the surgery of patient k is performed immediately after the surgery of patient j.

4.4.3 Allowing patient recovery in the operating room

At the end of the surgery operation, the patient is transferred to a recovery bed to wake up slowly under appropriate personal and equipment monitoring. However, if no recovery bed is available, the patient can wake up in the operating room until the discharge of a recovery bed or until she/he is transported back to the ward after her/his recovery.

To cope with this situation, Constraints (14) and (15) are replaced by Constraints (47) and (48) in both models NF_MILP and A_MILP. Also, for Stage 2 (operating rooms), Constraints (18) and (19) in NF_MILP are replaced by Constraints (49) and (50), respectively. Similarly, in A_MILP, Constraints (32) and (33) are replaced by Constraints (51) and (52), respectively. In addition, we append Constraints (53) to both models to limit the recovery in the operating room to its estimated time.

$$ \begin{array}{cc}\hfill {T}_{3j}-{T}_{2j}={p}_{2j}+{d}_{2j}+{r}_j\hfill & \hfill \forall j\in J\hfill \end{array} $$
(47)
$$ \begin{array}{cc}\hfill {T}_{4j}-{T}_{3j}={p}_{3\mathrm{j}}+{d}_{3j}-{r}_j\hfill & \hfill \forall j\in J\hfill \end{array} $$
(48)
$$ \begin{array}{cc}\hfill \mathrm{M}\left(1-{X}_{2jk}\right)+{T}_{2k}-{T}_{2j}\ge \kern0.5em {p}_{2j}+{d}_{2j}+{r}_j\hfill & \hfill \forall j\in J,k\in J,j\ne k\hfill \end{array} $$
(49)
$$ \begin{array}{cc}\hfill \mathrm{M}\left(1-{X}_{3jk}\right)+{T}_{3k}-{T}_{3j}\ge \kern1em {p}_{3j}+{d}_{3j}-{r}_j\hfill & \hfill \forall j\in J,k\in J,j\ne k\hfill \end{array} $$
(50)
$$ \begin{array}{cc}\hfill {T}_{2k}\ge {T}_{2j} + {p}_{2j}+{r}_j-\mathrm{M} \times \left(1-{Y}_{jk}^{22}\right)-\mathrm{M}\times \left(1-{W}_{2jl}\right)-\mathrm{M}\times \left(1-{W}_{2 kl}\right)\hfill & \hfill \forall l\in {R}_2,\ j\in J,k\in J,j\ne k\hfill \end{array} $$
(51)
$$ \begin{array}{cc}\hfill {T}_{3k}\ge {T}_{3j} + {p}_{3j}-{r}_j-\mathrm{M} \times \left(1-{Y}_{jk}^{33}\right)-\mathrm{M}\times \left(1-{W}_{3jl}\right) - \mathrm{M}\times \left(1-{W}_{3 kl}\right)\hfill & \hfill\ \forall l\in {R}_3,\ j\in J,k\in J,j\ne k\hfill \end{array} $$
(52)
$$ \begin{array}{cc}\hfill 0\le \kern0.5em {r}_j\ \le\ {p}_{3j}\hfill & \hfill \forall j\in J\hfill \end{array} $$
(53)

where \( {r}_j \) is a decision variable that indicates the recovery time spent by patient j in the operating room.

4.4.4 Performing the acts of the same surgeon successively

Surgeons may impose performing their surgeries successively to reduce their travel time to/from the healthcare facility as well as predictive errors in case durations and tardiness from scheduled start times. This requires scheduling the cases of a same surgeon in sequence [42, 43]. To deal with this situation, Constraints (19) are replaced by Constraints (54) in NF_MILP and Constraints (34) are replaced by Constraints (55) in A_MILP.

$$ \begin{array}{cc}\hfill\ {T}_{5k}{X}_{5jk} = \left({T}_{5j}+{p}_{5j}\ \right){X}_{5jk\ }\hfill & \hfill \forall s\in S,j\in {J}_s,k\in {J}_s,j\ne k\hfill \end{array} $$
(54)
$$ \begin{array}{cc}\hfill {T}_{5k}{Y}_{jk}^{55}=\left({T}_{5j}+{p}_{5j}\right){Y}_{jk}^{55}\hfill & \hfill \forall s\in S,j\in {J}_s,k\in {J}_s,j\ne k\hfill \end{array} $$
(55)

These nonlinear constraints can be linearized using the Reformulation Linearization Technique developed by Sherali and Adams in 1990 and 1994 [44, 45].

5 Computational experiments

To evaluate the performance of the proposed NF-MILP and A_MILP models, we conducted experiments on real-world data and on a set of randomly generated instances. Moreover, we investigated the minimization of two criteria: patients’ average length of stay and patients’ overnight stays.

The proposed models were solved using CPLEX 12.2 solver with the default setting. All the experiments were run on an Intel PC (R) Xeon (R) with a 3.30 GHz CPU processor and 8 GB RAM.

In the following paragraphs, we present the test-bed instances, then we discuss the computational effort required to solve them optimally. Finally, we investigate the impact of the objective function on the solution’s quality.

5.1 Test-bed instances

The computational study is carried out on two types of instances: (1) real-world instances provided by a Tunisian private clinic: Clinique Ennasr and (2) randomly generated instances.

5.1.1 Real-world instances provided by Clinique Ennasr

Clinique Ennasr is a private Tunisian clinic that is located in Tunis. It offers a range of clinical services corresponding to different medical and surgical specialties with a major on oncology. Its operating theatre comprises four identical operating rooms and four recovery beds. It employs a qualified nursing staff that along with well-dimensioned surgical facilities and instruments, allows the opening of the operating theatre all day long (24 h/24 h).

Clinique Ennasr provided us with six real-data instances that represent different surgical activity levels in 2014. Table 1 presents the main characteristics of these instances: Column 1 provides the instance number (Inst.). Column 2 gives the number of patients (# Patients). Column 3 indicates the number of surgeons (# Surgeons). The last column presents the number of patients per clinic room (\( \frac{\;\#\;\boldsymbol{Patients}}{\#\;\boldsymbol{Clinic}\;\boldsymbol{rooms}} \)).

Table 1 Real-world instances of Clinique Ennasr
Full size table

Real-world instance data specifies for each surgery case, the surgery date, the referred surgeon, the surgery specialty as well as pre-operative, surgery, recovery and post-operative times. This test-bed involves 20 clinic rooms that are available at the beginning of each day, on average.

We notice here that on a given day, each surgeon operates 1.9 cases on average. This reflects the real-world context of Clinique Ennasr and its private surgeons. Indeed, the clinic, as a private facility, collaborates with various surgeons of different specialties and surgeons as independent service provider conduct their surgeries in several healthcare facilities.

5.1.2 Generated data

In order to conduct further experiments, we generated two sets of 60 instances. The first set mimics the surgical activity of Clinique Ennasr while the second set simulates the activity of a larger surgery unit (see Table 2).

Table 2 Description of the surgical unit of the generated instances
Full size table

Table 2 presents, for each set of instances, the number of generated instances (# Instances), the number of operating rooms (# Operating rooms), the number of recovery beds (# Recovery beds) and the number of clinic rooms (# Clinic rooms).

In set 1, according to the Tunisian regulation that imposes to have at least as many recovery beds as operating rooms [46], the number of recovery beds is set to the number of operating rooms. However, in the state of the art, it is often recommended to have a number of recovery beds equal to 1.5 times the number of operating rooms [47], which is considered in set 2.

For each set of instances, we simulated various activity levels of the facility that correspond to different numbers of surgeries to be scheduled (see Table 3). Moreover, in order to draw the surgeons’ activity on a given day, we assigned randomly three surgery cases on average to each surgeon. However, we do not impose any preference/availability restriction for the surgeons.

Table 3 Main characteristics of the generated subsets of instances
Full size table

For each subset, we generated five instances with different processing times (per-operative times, operating times, recovery times and post-operative times). To estimate these times, we conducted an experimental study on historical data related to the surgery activity during 2014 at Clinique Ennasr. The results indicate that the processing times depend on three types of elective surgery cases:

  • Outpatients who can leave the hospital after their recovery, without overnight staying. They represent 40 % of the patients.

  • Medium length of stay inpatients who are required to spend only one night in the clinic. They represent 40 % of the patients.

  • Long length of stay inpatients who need to spend more than one night in the clinic. They represent 20 % of the patients.

According to the experimental study, we set the per-operative times to 2 h for outpatients and medium length of stay inpatients. However, for long length of stay inpatients, they usually enter the clinic a day before the surgery, and thus their per-operative time is set to only 10 min.

For surgery and post-operative times, we analysed the data using Minitab software [48] and we compared the P_value of different distributions functions. Table 4 presents the obtained results for the four best fitting distributions functions: Normal, Exponential, Lognormal and Gamma, for each patient type.

Table 4 P-value Results
Full size table

Table 4 shows that the best fitting probability distribution function is the lognormal distribution since it has the largest P_value exceeding the significance level α of 5 %. This result confirms previous works, where the surgery times are usually generated using a lognormal distribution ([8, 22, 49, 50]) or a Pearson III distribution [6].

Tables 5 and 6 provide the mean and the standard deviation of the considered lognormal distribution for surgery times and post-operative times, respectively.

Table 5 Characteristics of the lognormal distribution for surgery times
Full size table
Table 6 Characteristics of the lognormal distribution for post-operative times
Full size table

Moreover, in order to better estimate surgery and post-operative times, we propose to use a truncated lognormal distribution that imposes minimum and maximum values.

To validate the characteristics of the selected distribution functions, we presented them to the practicians of Clinique Ennasr who suggest minor rounding adjustments. The final characteristics of the truncated lognormal distribution for the surgery and post-operative times are displayed in Tables 7 and 8, respectively. The columns give the mean, the standard deviation, the minimum and the maximum values in minutes, respectively,

Table 7 Characteristics of the selected truncated lognormal distribution for surgery times
Full size table
Table 8 Characteristics of the selected truncated lognormal distribution for post-operative times
Full size table

For recovery times, we set them equal to surgery times for all inpatients and to surgery times minus 10 min for outpatients.

5.2 Computational results

To assess the empirical performance of the proposed formulations NF_MILP and A_MILP, we compared their computational time to solve the test-bed instances optimally.

We conducted three sets of experiments with different objective functions. The first set considers the minimization of patients’ average length of stay and the second set minimises the number of patients’ overnight stays. Finally, in the third set, patients’ average length of stay of patients is minimised with additional constraints on the maximal number of patients’ overnight stays.

In all our experiments, we pre-set the CPU time limit to 1 h.

In the subsequent paragraphs, the generated instances are denoted by I-s-n-k where s is the instance set number (s∈{1, 2}), n is the number of patients and k is the instance number (k∈{1, …, 5}).

5.2.1 The patients’ average length of stay minimization

In this set of experiments, the objective function of the Integrated Elective Surgeries’ Scheduling Problem (IESSP) minimises patients’ average length of stay. Tables 9 and 10 display the results of real-world instances and generated instances, respectively. The two first columns indicate the problem instance identification (Inst.) and the optimal patients’ average length of stay, in minutes (ALS * (min)). The next two columns provide the CPU times, in seconds required by NF_MILP (CPU_NF (s)) and A_MILP (CPU_A (s)) formulations, respectively. The last column indicates the CPU time improvement achieved by A_MILP against NF_MILP in percentage (CPU_IMP (%)) given by (56).

Table 9 Patients’ average length of stay minimisation for the real-world instances
Full size table
Table 10 Patients’ average length of stay minimisation for the generated instances
Full size table
$$ CPU\_ IMP\left(\%\right)=\frac{CPU\_NF-CPU\_A}{CP{U}_{NF}}\times 100 $$
(56)

*** indicates that no optimal solution was found within 1 h of computation time.

Tables 9 and 10 show that A_MILP model outperforms NF_MILP model. In Table 9, all the real-world instances are optimally solved in less than 21 min. NF_MILP model requires longer CPU times than A_MILP model, ranging from 8.07 s to 1208.92 s, whereas the CPU times of A_MILP model do not exceed 69.44 s. For the generated instances, Table 10 show that, within 1 h of CPU time, A_MILP model provides optimal solutions for all instances in less than 183.71 s in average, whereas NF_MILP model solves only 56.7 % of the instances within 361.10s in average.

It is worth mentioning that for the generated instances of set 2, and when the number of patients per clinic room is less than 1.2, NF_MILP model requires less CPU time than A_MILP model.

Not surprisingly, we observe that the CPU time increases as the number of patients and the number of patients per clinic room increase. Indeed, the problem becomes more constrained and thus more difficult to solve.

5.2.2 Number of patients’ overnight stays minimization

In this second set of experiments, the objective function of IESSP aims to minimise the number of patients’ overnight stays. Thus, we replace the objective function by expression (41) and append Constraints (42–44) in both models NF-MILP and A_MILP.

Tables 11 and 12 provide the results of real-world instances and generated instances, respectively. The two first columns indicate the problem instance identification (Inst.) and the optimal number of patients’ overnight stays (# PO*). The next two columns provide the CPU times, in seconds required by NF_MILP (CPU_NF (s)) and A_MILP (CPU_A (s)) formulations, respectively. The last column indicates the CPU time improvement achieved by A_MILP against NF_MILP in percentage (CPU_IMP (%)) and given by (56).

Table 11 Number of patients’ overnight stays minimization for real-world instances
Full size table
Table 12 Number of patients’ overnight stays minimization for the real-world instances
Full size table

Tables 11 and 12 confirm that A_MILP model consistently outperforms NF_MILP model. Indeed, A_MILP model solves to optimality all the real-world instances in less than 133.52 s of computation time, whereas NF_MILP solves only 66.7 % of these instances within the pre-set CPU time of 1 h. Moreover, NF_MILP model requires longer CPU times than A_MILP model except for the first instance.

For the generated instances, Table 12 show that, within 1 h of computation time, A_MILP model provides optimal solutions to 91.7 % of the instances while requiring 313.01 s of CPU time in average, whereas NF_MILP model solves only 21.7 % of the instances within 1679s of CPU time in average.

Besides, for the instances solved to optimality by both models, A_MILP provides solutions in less CPU time than NF_MILP for 82.3 % of the instances with 91.5 % of CPU time improvement in average.

Finally, here again, we observe that the CPU time increases as the number of patients and the number of patients per clinic room increase. More specifically, instances where the number of patients per clinic room exceeds 1.2 seem to be harder to solve by NF_MILP model.

5.2.3 Patients’ average length of stay minimization under patients’ overnight stays constraints

In this last set of experiments, we consider the minimization of both criteria: patients’ average length of stay and number of patients’ overnight stays. We apply a hierarchical approach to solve this multi-objective problem.

Since A_MILP model performs better than NF_MILP model, according to the two previous experiments, we use it for the multi-objective problem. Thus, we build the so-called MO_A_MILP model by appending to A_MILP model Constraints (42–44) as well as the following constraint (57),

$$ {\displaystyle \sum_j{N}_j=O{P}^{\ast }} $$
(57)

where OP* is the minimum number of patients’ overnight stays.

Constraint (57) enforces the number of patients’ overnight stays to be equal to its minimum value OP*.

Tables 13 and 14 display the computational results of the multi-objective model MO_A_MILP for the real-world instances and generated instances, respectively. The first column indicates the problem instance identification (Inst.). The two next columns give the optimal patients’ average length of stay in minutes (MO_ALS* (min)) and the CPU times in seconds (MO_CPU (s)). The last column indicates the gap between the patients’ average length of stay (MO_ALS*) obtained by the multi-objective problem MO_A_MILP and its minimum value (ALS*) provided by the A_MILP model.

Table 13 Multi-objective solutions for the real-world instances
Full size table
Table 14 Multi-objective solutions for the generated instances
Full size table
$$ GAP\_ALS\ \left(\%\right)=\frac{AL{S}^{*}-MO\_AL{S}^{*}}{AL{S}^{*}}\times 100 $$
(58)

In Tables 13 and 14, +++ indicates instances for which the minimum number of patients’ overnight stays OP* is unknown; and *** indicates unsolved instances within 1 h of computation time.

Tables 13 and 14 provide empirical evidence that A_MILP based models perform very well. Table 13 shows that all the real-world instances are optimally solved within less than 53.75 s. For the generated instances, the results of Table 14 indicate that, within the pre-set CPU time limit of 1 h, MO_A_MILP model provides optimal solutions to 81.7 % of the instances while requiring a CPU time of 140.27 s in average, ranging from 36.67 s to 524.52 s. Moreover, the solution of 8.3 % of the instances is not considered because we do not have the minimum number of patients’ overnight stays OP*.

Besides, appending constraints on the number of patients’ overnight stays has a little impact on the patients’ average length of stay. Indeed, for 89.8 % of the generated instances, patients’ average length of stay (MO_ALS*) provided by the hierarchical approach is equal to its minimum value (ALS*). For the other instances, patients’ average length of stay is increased by only 0.04 % in average.

6 Conclusions and future research

In this work, we focused on the optimal solution of the Integrated Elective Surgeries’ Scheduling Problem (IESSP) that arises in a privately operated healthcare facility. It consists on scheduling surgery cases over 1-day period while taking into account four main resources: Hospital beds, operating rooms, surgeons and recovery beds.

We modelled this problem as a three-stage hybrid flow-shop scheduling problem with recirculation, resource synchronization, dedicated machines, and blocking constraints. We developed two mixed integer linear programs that can be efficiently solved using a general-purpose MILP solver. The first program is based on network flow model (NF_MILP) and the second program is an assignment-based model (A_MILP). Both models are compact and can be easily extended to accommodate several specific restrictions of the real-world healthcare context.

Two objective functions were investigated: patients’ average length of stay and number of patients’ overnight stays minimization. First, we tested the two criteria separately and then we considered them simultaneously using a hierarchical approach.

The results of the computational experiments conducted on six real-world instances delivered by Clinique Ennasr and 60 instances generated randomly provide an empirical evidence that the assignment-based model (A_MILP) outperforms the network flow-based model (NF_MILP). Indeed, within 1 h of CPU time, A_MILP model gives optimal solutions for all real-world and generated instances in less than 188.49 s in average, whereas NF_MILP model solves all real-world instances but only 56.7 % of the generated instances within 348.37 s in average.

Moreover, the experimental results of the multi-objective problem validate the proposed hierarchical approach that minimises the patients’ average length of stay while setting the number of patients’ overnight stays to its minimum value. Indeed, patients’ average length of stay kept its minimum value for 92.5 % of the solved test-bed instances and has increased by less than 0.11 % for the remaining instances.

In practice, surgical process times are highly variable and uncertain. Thus, accounting for this random behaviour in patients’ scheduling is crucial. For future research, we aim to develop a stochastic approach based on the proposed deterministic assignment model (A_MILP).

Furthermore, in day-to-day operation, surgical process times are often subject to disruptions that perturb the optimized schedules and causes delays and cancellations. Thus, an interesting perspective is to build robust schedules having less likelihood to be damaged by unpredicted events. This is a topic of our ongoing research.