# Mixed Integer Linear and Constraint Programming for Dual-resource Scheduling with Synchronization in Emergency Departments

Jessica Florencia, Lorraine Trilling, Thierry Moyaux, Ikram Lafnoune, Andrea Mantoan, Ludovica Maria Pomilio, Guillaume Bouleux, Vincent Cheutet

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Jessica Florencia, Lorraine Trilling, Thierry Moyaux, Ikram Lafnoune, Andrea Mantoan, et al.. Mixed Integer Linear and Constraint Programming for Dual-resource Scheduling with Synchronization in Emergency Departments. 11th International Conference on Control, Decision and Information Technologies (CoDIT 2025), Jul 2025, Split, Croatia. hal-05290044

HAL Id: hal-05290044

https://hal.science/hal-05290044v1

Submitted on 30 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Mixed Integer Linear and Constraint Programming for Dual-resource Scheduling with Synchronization in Emergency Departments

Jessica Florencia<fnref n="1" />, Lorraine Trilling<fnref n="1" />, Thierry Moyaux<fnref n="1" />, Ikram Lafnoune<fnref n="2" />, Andrea Mantoan<fnref n="3" />, Ludovica Maria Pomilio<fnref n="3" />, Guillaume Bouleux<fnref n="1" /> and Vincent Cheutet<fnref n="1" />

**Abstract**—Emergency Departments (EDs) must operate in environments characterized by uncertainty and resource constraints. One of their critical challenges is dual-resource scheduling, that is, synchronizing two resources at the same time on a task. For example, taking a blood sample from a child patient requires two nurses, one to take the sample and another to prevent the patient from moving. Addressing this challenge requires structured approaches capable of ensuring both synchronization and prioritization based on patient urgency. This study explores two distinct optimization models for dual-resource scheduling in EDs, namely, a Mixed Integer Linear Programming (MILP) and a Constraint Programming (CP). The MILP model leverages a linear formulation to globally optimize scheduling and resource synchronization, while the CP model exploits constraint satisfaction techniques to handle task dependencies and resource constraints. We test both models on the same case study. Their comparison highlights key differences in computational complexity, variable representation and constraint formulation. The results demonstrate that neither model consistently outperforms the other, but rather, their effectiveness depends on instance size and problem-specific characteristics.

## I. INTRODUCTION

Emergency Departments (EDs) are fundamental components of healthcare systems, providing continuous medical care for patients requiring urgent attention. However, EDs often face severe operational challenges, including overcrowding, unpredictable patient arrivals, and limited resource availability [1], [2]. Such challenges may result in delays in patient treatment, increased staff workload, and suboptimal resource utilization, ultimately affecting the quality of care provided [1]. Therefore, efficient resource scheduling and allocation are essential to ensure timely and effective patient management in such a dynamic environment.

Traditional scheduling models in healthcare typically focus on assigning a single resource, such as a doctor or nurse, to a specific task for a patient [3]. However, many medical

procedures in real-world emergency care require simultaneous coordination of multiple resources. For example, specific pediatric emergency procedures may require the presence of two nurses at the same time to ensure efficient and safe task execution, such as when administering treatments or performing complex medical assessments. Despite the critical need for synchronized resource allocation, existing scheduling models rarely incorporate dual-resource constraints (considered here as the availability of two resources of the same type to perform a task), limiting their applicability to realistic ED scenarios.

Consequently, the purpose of this article is to propose and compare two models for dual-resource scheduling; one model is in Mixed Integer Linear Programming (MILP), and the other one is in Constraint Programming (CP). The primary objective of this research is to analyze the strengths and weaknesses of both models in handling dual-resource constraints, assessing their computational complexity, flexibility and solution quality in an instance of scheduling.

The remainder of this paper is structured as follows. Section II reviews the relevant literature on resource scheduling and multi-resource synchronization in EDs. Section III introduces the problem and our two models. Section IV describes the test instance and the results obtained by both models. Finally, Section V concludes the study, highlighting potential future research directions.

## II. LITERATURE REVIEW

### A. Literature in health care

The Nurses Scheduling Problem (NSP) has been widely studied over the last decades [4]. The goal of NSP is the creation of individual schedules by assigning a number of shifts with predefined start and end times to nurses. Over the last decades, various approaches have been developed to address the complexity of NSP, ranging from manual methods to advanced optimization algorithms [4], such as Mixed Integer Linear Programming (MILP), column generation, meta-heuristics and Constraint Programming (CP). Strömgre [5] specifically reviewed the literature on Nurse Rostering with CP, which is a technique particularly relevant for highly constrained problems such as staff scheduling. MILP and CP have been used to solve the NSP, either separately in order to compare them [6], or combined [7].

The problem we tackle in this article aims to assign nurses to patients and tasks over time (and not to full shifts), considering synchronization of resources, and in this sense, differs significantly from the classical NSP. In a previous

<footnote>*This work contributes to JUNEAU project that is funded by ANR (Agence Nationale de la Recherche – France) "ANR-22-CE46-0010-01". A CC-BY public copyright license has been applied by the authors to the present document and will be applied to all subsequent versions up to the Author Accepted Manuscript arising from this submission, in accordance with the grant's open access conditions.</footnote>

<footnote n="1">¹INSA Lyon, Université Lumière Lyon 2, Université Claude Bernard Lyon 1, Université Jean Monnet Saint-Etienne, DISP UR4570, Villeurbanne, 69621, France firstname.familname@insa-lyon.fr</footnote>

<footnote n="2">²INSA Lyon, Villeurbanne, 69621, France firstname.familname@insa-lyon.fr</footnote>

<footnote n="3">³Department of Economics, Management, and Industrial Engineering, Politecnico di Milano, Italy firstname.familname@mail.polimi.it</footnote>
work, we conducted research on improving dynamic resource scheduling in the ED. More precisely, Florencia et al. [3] model the scheduling of nurses to patients in a pediatric ED as a MILP but, conversely to this article, this previous work considers that every patient requires both a single task in his pathway, and a single resource (nurse) for this task. Thus, the complexity of the real-world setting, with nurse synchronization, is not fully addressed. Next, Mezouari et al. [8] propose a MILP in which a patient requires several tasks, like in this article. Several resources may also be assigned to a task, but this is done differently from this article: The tasks in their MILP can be assigned to a single resource only, but several tasks can be constrained to start at the same time on the same patient. Conversely to our MILP but similarly to our CP, their MILP models the time as discrete.

The two models proposed below in this article synchronize two resources of the same type (nurses, which belong to a same set, even if our constraints enforce that the nurse doing the first task of a patient will also take part in all the following tasks of this patient). On the contrary, other articles synchronize resources of two different kinds. First, Saddikuti and Gudavalleti [9] propose a MILP for scheduling two types of resources, viz., medical staff and emergency beds. Next, Di Mascolo et al. [10] propose a MILP to optimize the scheduling and routing of two types of nurses when they must visit their patients at their home in given time windows. More precisely, these authors do not address an ED but Home Health Care, and they synchronize both a nurse and an auxiliary nurse (who are thus drawn from two different sets) to visit a given patient at the same time.

The literature specifically addressing dual-resource synchronization in the context of EDs is sparse. Consequently, the next subsection further extends the scope of this review in order to draw inspiration for our models.

## B. Literature in manufacturing

As scheduling tasks in healthcare systems could be considered as a particular case of scheduling in production systems, we present some work in manufacturing close to ours.

For instance, Magalhães and colleagues [11] developed a model addressing the Dual-Resource Constrained Flexible Job Shop Scheduling Problem, an extension of the traditional Flexible Job Shop Scheduling Problem (DRC-FJSSP). Their work introduces the constraint that each machine must be supervised by an operator during its operation. While their research focuses on manufacturing, we adapted their dual-resource synchronization concept to our context, interpreting the “machine” and “operator” as analogous to the two nurses required simultaneously for certain tasks in the ED. Given the computational complexity of the DRC-FJSSP, Magalhães et al. proposed several meta-heuristic solutions, such as genetic algorithms, simulated annealing, and variable neighborhood search, to reduce computational time while maintaining solution quality.

Almeder and Almada-Lobo [12] compare two MILPs to synchronize manufacturing resources: One is based on

the capacitated lot-sizing problem and the second on the general lot-sizing and scheduling model. Their second MILP is the closest to our scheduling MILP, but their context of manufacturing implies hypotheses different from an ED, e.g., their MILP considers costs, setup times, and inventory levels with backlogs. Moreover, their MILP considers time as discrete, like our CP, but unlike our MILP.

Constraint Programming, with its ability to handle global constraints and non-linear constraints, has proved its effectiveness in solving many scheduling problems [13], [14]. To the best of our knowledge, the use of constraint programming to solve dual-resource scheduling problems involving the synchronization of resources is innovative [15].

The aim of this article, in the literature sense, is to fill the gap between extremely specific and wide articles on ED resource synchronization and the simpler and more direct approach of the dual resource constraint approach in manufacturing systems.

## III. OUR MILP AND CP MODELS FOR NURSE SCHEDULING IN ED

We now introduce our two models to schedule one or several nurses for some tasks of child patients in a pediatric ED, referred to as patients for the rest of the paper and identified with index *c* in the mathematical model. Subsection III-A first introduces the problem and notations common to both models. Next, Subsection III-B details our MILP, and Subsection III-C our CP.

### A. Problem description and hypotheses common to both MILP and CP models

The primary aim of the problem is to efficiently allocate and synchronize the available nursing resources across various tasks required for patient care, ensuring that the critical needs of patients are met in a timely and organized manner. The tasks for one patient could require one nurse (first consultation, simple drug administration, ...) or several nurses (blood draws, complex drug administration, placing complex medical devices...), have a specific time duration and need to be done in a defined sequence. The objective is to minimise the waiting time of the patients, from arrival to the first task and the waiting time between tasks, weighted by their level of urgency.

It was chosen to focus the analysis on a particular, simplified scenario in order to obtain clear results that could then be applied to more complex scenarios. Therefore, we make the following two main hypotheses:

*   **Deterministic model:** The model operates under the assumption that all input data, such as patient arrival times, urgency (triage level), treatment sequence with durations of each task, and resource availability, are known in advance and do not change over time. This allows for a structured optimization process without accounting for uncertainty or real-time adjustments.

*   **Same nurse for a given patient:** To ensure continuity of care and minimize disruptions, each patient is assigned
to a single nurse for the entire duration of their treatment. This nurse will perform the sequence of tasks required by the patient care. For tasks requiring more than one nurse, additional nurses will be assigned and then released after the task is completed. This constraint enhances patient-nurse interaction, minimizes handover inefficiencies, and ensures a higher quality of care.

The constraints of both models are hard constraints that need to be satisfied. Both our MILP and CP models share the following notations:

**Indices & sets:**

$\mathcal{N}$ Set of the indices of nurses

$\mathcal{N}$ Number of nurses (cardinality of $\mathcal{N}$)

$n$ Index of a nurse, i.e., Nurse $n \in \mathcal{N} = \{1, \dots, N\}$

$c$ (Child) Patient $c \in \mathcal{C} = \{0, \dots, C\}$

$t$ Task $t \in \mathcal{T} = \{1, \dots, T\}$, $T$ is the highest index of tasks in a sequence for a patient

**Parameters:**

$r_c$ Arrival time (release date) of Patient c

$p_{c,t}$ Processing time of Task $t$ for Patient c

$u_c$ Triage level (urgency) for Patient c

$q_{c,t}$ Number (quantity) of nurses required by Task $t$ of Patient c

## B. Model in Mixed Integer Linear Programming (MILP)

The following equations are the MILP to assign (i) the same nurse for all the tasks of a given patient and (ii) another nurse for some of these tasks.

**Decision variables:**

$s_{c,t,n}$ Start time of Task $t$ of Patient $c$ done by Nurse $n$, continuous variable $\in \mathbb{R}$

$x_{c,t,n}$ = 1 if Nurse $n$ is assigned to Task $t$ of Patient $c$, 0 otherwise

$k_{c_1,t_1,c_2,t_2,n}$ = 1 if Task $t_1$ of Patient $c_1$ is performed before Task $t_2$ of Patient $c_2$ by Nurse $n$, 0 otherwise

**MILP mathematical model:**

$$ \min \sum_{c \in \mathcal{C}} \left[ \frac{1}{u_c} \cdot \left( \left( \sum_{n \in \mathcal{N}} s_{c,1,n} \right) - r_c \right) \right] + \sum_{c \in \mathcal{C}} \sum_{t \in \mathcal{T}} \left[ \frac{1}{u_c} \cdot \left( \frac{\sum_{n \in \mathcal{N}} s_{c,t+1,n}}{q_{c,t+1}} - \frac{\sum_{n \in \mathcal{N}} s_{c,t,n}}{q_{c,t}} - p_{c,t} \right) \right] \quad (1) $$

subject to

$$ \sum_{n \in \mathcal{N}} x_{c,t,n} = q_{c,t} \quad \forall c \in \mathcal{C}, t \in \mathcal{T} \quad (2) $$

$$ s_{c,t+1,n} + M(1 - y_{c,1,n}) \geq s_{c,t,n} + p_{c,t} \cdot x_{c,t,n} \quad (3) $$
$$ \forall c \in \mathcal{C}, n \in \mathcal{N}, t \in \{1, \dots, T-1\} $$

$$ x_{c,1,n} \leq x_{c,t,n} \quad \forall c \in \mathcal{C}, n \in \mathcal{N}, t \in \{2, \dots, T\} | p_{c,t} > 0 \quad (4) $$

$$ s_{c,1,n} \geq r_c \cdot x_{c,1,n} \quad \forall c \in \mathcal{C}, n \in \mathcal{N} \quad (5) $$

$$ s_{c,t,n_1} \leq s_{c,t,n_2} + M(2 - (x_{c,t,n_1} + x_{c,t,n_2})) \quad (6) $$

$$ \forall c \in \mathcal{C}, t \in \{2, \dots, T\}, n_1 \in \mathcal{N}, n_2 \in \mathcal{N}, n_1 \neq n_2 $$

$$ s_{c,t,n_2} \leq s_{c,t,n_1} + M(2 - (x_{c,t,n_1} + x_{c,t,n_2})) \quad (7) $$
$$ \forall c \in \mathcal{C}, t \in \{2, \dots, T\}, n_1 \in \mathcal{N}, n_2 \in \mathcal{N}, n_1 \neq n_2 $$

$$ s_{c_1,t_1,n} + p_{c_1,t_1} \cdot x_{c_1,t_1,n} - s_{c_2,t_2,n} \leq M(1 - k_{c_1,t_1,c_2,t_2,n}) \quad (8) $$
$$ \forall n \in \mathcal{N}, c_1 \in \mathcal{C}, t_1 \in \mathcal{T}, c_2 \in \mathcal{C}, t_2 \in \mathcal{T} | (c_1, t_1) \neq (c_2, t_2) $$

$$ k_{c_1,t_1,c_2,t_2,n} + k_{c_2,t_2,c_1,t_1,n} = 1 \quad \forall n \in \mathcal{N}, c_1 \in \mathcal{C}, \quad (9) $$
$$ t_1 \in \mathcal{T}, c_2 \in \mathcal{C}, t_2 \in \mathcal{T} | (c_1, t_1) \neq (c_2, t_2) $$

$$ s_{c,t,n} \geq M \cdot y_{p,t,n} \quad \forall n \in \mathcal{N}, c \in \mathcal{C}, t \in \mathcal{T} \quad (10) $$

The objective function (1) minimizes both the waiting time from arrival to the first task and the waiting time between tasks, considering the urgency of the patients' condition. Constraint (2) ensures that the number of nurses assigned to perform task $t$ matches the number of nurses required by this task. Specifically, for each Patient $c$ and Task $t$, the sum of assigned nurses must be equal to the required number of nurses $q_{c,t}$. This guarantees that each task is adequately staffed and the total nursing capacity is correctly allocated. Constraint (3) ensures that the start time of a task $t+1$ for Patient $c$ cannot be earlier than the completion of the preceding Task $t$ for nurse $n$, only if nurse $n$ treated the task $t$ of Patient $c$ (the big $M$ is used to linearize and ensure this condition is satisfied). The transition time between tasks is determined by the operational duration $p_{c,t}$ of Task $t$, ensuring a logical sequence in the execution of medical procedures. In order to maintain continuity of care, Constraint (4) ensures that a Patient $c$ is treated by the same Nurse $n$ throughout their entire stay. If a nurse is assigned to the first task of a patient, they must also be assigned to all subsequent tasks required by this patient. Constraint (5) enforces that the first task of Patient $c$ cannot start before their arrival time. It ensures that no treatment is scheduled before the patient has actually arrived at the ED.

Some tasks require two nurses to work together. Constraint (6) ensures that for a dual-resource task, the start time is synchronized for both nurses. If two Nurses $n_1$ and $n_2$ are assigned to the same Task $t$, their start times must be equal, preventing inconsistencies in task execution. Constraint (7) complements (6) by ensuring that if a dual-resource task is assigned to two nurses, the start time must be the same from the perspective of both nurses. This eliminates scheduling mismatches that could otherwise disrupt the workflow. Both constraints (7) and (6) involve the use of a big $M$ technique to linearize the constraints, $M$ being a large value allowing to remove the constraints if the two nurses $n_1$ and $n_2$ are not assigned to patient $c$.

To prevent overlapping tasks for a single nurse, disjunctive constraints are used: Constraint (8) ensures that if a nurse is assigned to two different tasks for different patients, these tasks must be scheduled sequentially. The start time of one task must be after the completion of the other, preventing scheduling conflicts. Here again, we introduce a big $M$ to remove the constraint if the nurse does not perform task $t_1$ of Patient $c_1$ before Task $t_2$ of Patient $c_2$. When two tasks involving different patients are assigned to the same
nurse, Constraint (9) ensures that one task must be scheduled before the other. It introduces a binary variable $k_{c_1,t_1,c_2,t_2,n}$ to enforce a strict ordering, guaranteeing that tasks are not scheduled simultaneously. Lastly, constraint (10 ensures that the value of the start time of task $t$ of Patient $c$ performed by nurse $n$ is 0 if nurse $n$ does not perform the task $t$ on Patient $c$.

### C. Model in Constraint Programming (CP)

We now describe the same model, but expressed in CP. CP authorizes to use non-linear constraints, such as “if...then...” constraints, or *disjunctive* constraints, very useful in implementing sequencing problems.

**Decision variables:**

$s_{c,t}$ Start time of Task $t$ of Patient $c$

$e_{c,t}$ Completion (end) time of Task $t$ of Patient $c$

$x_{c,t,n}$ Start time of Task $t$ of Patient $c$ performed by Nurse $n$. (This variable only exists when task $t$ is assigned to a nurse $t$, which is specific to CP. If it is not the case, the variable does not take any value and occurs($x_{c,t,n}$) = 0)

All decision variables can take discrete values in a set of possible start and end times. We consider that those times are expressed in minutes.

**CP mathematical model:**

$$ \min \sum_{c \in \mathcal{C}} \frac{1}{u_c} \cdot \left[ s_{c,1} - r_c + \sum_{t \in \mathcal{T}} (s_{c,t+1} - s_{c,t} - p_{c,t}) \right] \quad (11) $$

subject to

$$ s_{c,1} \geq r_c \quad \forall c \in \mathcal{C} \quad (12) $$

$$ e_{c,t} = s_{c,t} + p_{c,t} \quad \forall c \in \mathcal{C}, t \in \mathcal{T} \quad (13) $$

$$ s_{c,t+1} \geq e_{c,t} \quad \forall c \in \mathcal{C}, t \in \{1, \dots, T-1\} \quad (14) $$

$$ \begin{array}{l} \text{if occurs}(x_{c,t,n}) = 1 \text{ then } x_{c,t,n} = s_{c,t} \quad \forall c \in \mathcal{C}, \\ \qquad \qquad \qquad \qquad \qquad t \in \mathcal{T}, n \in \mathcal{N} \end{array} \quad (15) $$

$$ \sum_{n \in \mathcal{N}} \text{occurs}(x_{c,t,n}) = q_{c,t} \quad \forall c \in \mathcal{C}, t \in \mathcal{T} \quad (16) $$

$$ \begin{array}{l} \text{disjunctive}([x_{c,t,n}|c \in \mathcal{C}, t \in \mathcal{T}], \\ \qquad [p_{c,t}|c \in \mathcal{C}, t \in \mathcal{T}]) \quad \forall n \in \mathcal{N} \end{array} \quad (17) $$

$$ \begin{array}{l} \text{if occurs}(x_{c,t-1,n}) = 1 \text{ then occurs}(x_{c,t,n}) = 1 \quad \forall c \in \mathcal{C}, \\ \qquad n \in \mathcal{N}, t \in \mathcal{T} | t+1 \in \mathcal{T} \land t-1 \in \mathcal{T} \land q_{c,t-1} \le q_{c,t} \end{array} \quad (18) $$

$$ \text{if occurs}(x_{c,t+1,n}) = 1 \text{ then occurs}(x_{c,t,n}) = 1 \quad (19) $$

$$ \forall c \in \mathcal{C}, n \in \mathcal{N}, t \in \mathcal{T} | t+1 \in \mathcal{T} \land q_{c,t} \ge q_{c,t+1} $$

$$ \begin{array}{l} \text{if occurs}(x_{c,1,n}) = 1 \text{ then occurs}(x_{c,t,n}) = 1 \\ \qquad \forall c \in \mathcal{C}, n \in \mathcal{N}, t \in \{2, \dots, T\} \end{array} \quad (20) $$

The objective function in (11) is the same as in the MILP in (1), even if it looks different. In particular, the division by $q_{c,t}$ in (1) corrects the fact that a patient is counted for each of their nurses – such a correction is not necessary in

(11). Constraint (12) ensures that no patient's first task starts before their arrival time, preventing premature scheduling. Constraint (13) defines the duration of each task by setting its end time as the sum of its start time and processing time, ensuring well-defined execution periods. Constraint (14) enforces task precedence by requiring that a task cannot begin until the previous one has finished, maintaining a logical sequence of operations. (15) ensures that if a nurse is assigned to a task, their assignment aligns with the start time of this task, which prevents inconsistencies in scheduling. (16) guarantees that the number of assigned nurses exactly matches the required number for each task, ensuring proper staffing. (17) prevents nurses from being assigned to overlapping tasks, enforcing a non-overlapping constraint so that no nurse is scheduled for multiple tasks at the same time. (18) ensures continuity in nurse assignments when the required number of nurses remains the same or increases, that is, if a nurse was assigned to the previous task of a patient, then they should continue in the next task of this patient. (19) is the reciprocal constraint of (18), that is, (19) models that if a nurse is assigned to a later task of a patient and the required number of nurses decreases or remains the same, then this nurse should have been assigned to the previous task as well. Finally, (20) ensures that if a nurse is assigned to the first task of a patient and the subsequent tasks require more than one nurse, then the same nurse must continue with this patient for all tasks, ensuring consistency in care.

## IV. EXPERIMENTATION

We now show our experiment of both MILP and CP on the same instances. We first describe this case study, then our experimental results.

### A. Case study

We consider several instances with different patient numbers (10, 12, 15, 18, and 20 patients) to compare the two models. Each patient has up to 3 treatment tasks. There are 4 nurses available to treat patients. These medium-sized scenarios were chosen to ensure that the core constraints were correctly enforced while maintaining computational feasibility. In the MILP, we set $M = 1,000$.

This comparative study aims to analyze the strengths and weaknesses of both MILP and CP models to determine which approach is better suited for the dual-resource scheduling problem in an ED. Given the operational context of an ED, the primary goal is not absolute optimality but rather achieving a high-quality feasible schedule within a reasonable computation time. To align with practical constraints, the solver (Gurobi) was configured with a 10-minute time limit, prioritizing solution feasibility over exhaustive optimization. More precisely, our MILP is implemented in Python 3.11.5 with library PuLP 2.9.0 to call Gurobi 12.0.1, and our CP in MiniZinc 2.8.7 is configured to also call Gurobi.

### B. Results and discussion

The first result explored is the Gantt charts of the nurse schedule, as shown in Figure 1 for MILP and CP models. The
<figure><img src="image_3.png" /><figcaption>Fig. 1. Gantt chart obtained from MILP model (Objective Function: 98) and CP model (Objective Function: 97).</figcaption></figure>

Gantt charts illustrate the start time and assignment of each task for each patient. The different colors represent varying urgency levels based on standard triage classifications, with red representing triage level (urgency) 1 (the most urgent) and blue representing triage level 5 (the least urgent). This urgency level was explicitly incorporated into the objective functions, influencing the prioritization of patient scheduling.

From the Gantt chart, it can be seen that the key constraint for our model, the dual-resource synchronization, is evident in the scheduling results: For example, in the schedule from MILP model, Patient 5's third task (called 5.3) is scheduled to be performed by Nurses 2 and 4 simultaneously, while the CP schedule shows that our CP assigns Task 5.3 to Nurses 1 and 2 as shown in Figure 1. In addition, a crucial assumption in the model was verified, which is continuity in patient care. This means that a patient should be treated by the same nurse throughout their ED journey. This is confirmed in the schedule generated by both models: For instance, our MILP model has Patient 1 entirely managed by Nurse 4 and our CP model by Nurse 1.

We can also evaluate the models from the objective function value, *i.e.*, weighted waiting time (WWT) and the total waiting time (WT) as shown in Table I. From this table, it seems that neither model constantly outperforms the other in terms of solution quality. We can see that CP produces a smaller objective function and total WT for smaller instances, while the MILP model performs better and generates smaller WWT and total WT for bigger instances. Besides, neither of the models achieves an optimal solution within the chosen time limit of 10 minutes.

Next, we also observe the computation time performance of our two models in producing the results. We set various time limits on the solver, ranging from 10 seconds to 10 minutes, and then capture the result each time. The result is shown in Figure 2 for the instances with 12 patients. MILP begins with a lower initial solution, then slowly approaches

<table><caption>TABLE I
OBJECTIVE FUNCTION (WWT) AND TOTAL WAITING TIME (WT)
RESULTS (IN MINUTES)</caption><thead><tr><th rowspan="2">Nb Patient (C)</th><th colspan="2">MILP</th><th colspan="2">CP</th></tr><tr><th>WWT</th><th>Total WT</th><th>WWT</th><th>Total WT</th></tr></thead><tbody><tr><td>10</td><td>98.4</td><td>350</td><td>97</td><td>325</td></tr><tr><td>12</td><td>128.7</td><td>346</td><td>114</td><td>302</td></tr><tr><td>15</td><td>234.1</td><td>484</td><td>272</td><td>592</td></tr><tr><td>18</td><td>266.9</td><td>758</td><td>304</td><td>752</td></tr><tr><td>20</td><td>361.2</td><td>977</td><td>411</td><td>937</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Performance Comparison of MILP and CP</figcaption></figure>

the near-optimal solution. On the other hand, CP begins with a worse initial solution, but improves its solution faster (in 30 seconds). These observations on the comparisons of the performance of both models underline that the choice between MILP and CP should not be framed in absolute terms but rather examined from multiple perspectives, considering their distinct characteristics and trade-offs.

In addition to the results observed, one of the most impressive differences examined between the two models lies in the number of variables involved. For instance, with
10 patients and 4 nurses, *the MILP utilizes up to 3,840 variables, while the CP operates with only 62 variables.* This significant discrepancy highlights the computational complexity of MILP, which requires handling variables with up to five indices (*cf.*, $k_{c1,t1}$, $k_{c2,t2}$, ..., $k_{c_n,t_n}$), increasing the burden on the solver. Conversely, CP allows for a more compact representation of constraints, leading to a more intuitive formulation and potentially faster constraint propagation.

However, a key advantage of MILP stems from its extensive literature support, as most of the relevant studies referenced in the literature section employ MILP formulations. This wealth of research provides a solid theoretical foundation and well-established methodologies that can be leveraged for model development and improvement. Furthermore, MILP benefits from the ability to incorporate continuous variables, which is particularly relevant in the context of time-based scheduling. This allows for a more precise representation of key performance measures, making it an important aspect to consider when selecting a modeling approach.

Shortly, this comparative analysis suggests that the choice between MILP and CP should be made based on *problem size, computational feasibility and model interpretability*. While *CP offers a more compact and constraint-focused formulation, MILP remains a powerful alternative due to its rich theoretical background and the ability to handle continuous variables*, which is crucial for time-sensitive optimization problems.

## V. CONCLUSIONS

The optimization of resource scheduling in complex environments such as Emergency Departments (EDs) is crucial to ensuring effective and efficient patient care. This study addresses the challenge of resource allocation and synchronization by introducing two models for dual-resource scheduling, one represented in Mixed Integer Linear Programming (MILP) and another in Constraint Programming (CP). The conducted analysis highlights the importance of optimization models capable of effectively addressing the operational challenges of EDs. By integrating realistic constraints, such as assigning the same nurse to a patient throughout their entire stay, these models contribute not only to optimize resource utilization but also to improving the quality of care.

Our experiments seem to indicate that neither of our MILP and CP is always the best. Our MILP seems better for large sizes of instances, and our CP for small instances. MILP for scheduling has a larger literature, but CP has models both smaller and easier to understand.

Future developments of this study open several doors for further research. Firstly, the integration of heuristic methodologies may provide near-optimal solutions within significantly shorter computational times. This is requested for a deployment in real life because rescheduling all patients when a new one arrives can hardly excess a few minutes. Of course, such a rescheduling needs some adaptations in our models in order not to postpone the currently ongoing tasks. Additionally, testing and evaluating the proposed models on

real-scale data would allow for a more detailed analysis of their performance and behavior in practical settings. Another promising direction is the incorporation of additional constraints to account for even more realistic scenarios, such as workload balancing and staff fatigue. Finally, since EDs often represent the first step in a patient's hospital journey, future research could focus on the downstream process following ED admission, exploring its impact on hospital resource management and patient outcomes.

## REFERENCES

[1] Ruth Luscombe and Erhan Kozan. Dynamic resource allocation to improve emergency department efficiency in real time. *European J. of Operational Research*, 255(2):593-603, 2016.

[2] Benoit Morel, Guillaume Bouleux, Alain Viallon, Maxime Maignan, Luc Provoost, Jean-Christophe Bernadac, Sarah Devidal, Sylvie Pillet, Aymeric Cantais, Olivier Mory, et al. Evaluating the increased burden of cardiorespiratory illness visits to adult emergency departments during flu and bronchiolitis outbreaks in the pediatric population: Retrospective multicentric time series analysis. *JMIR Public Health and Surveillance*, 8(3):e25532, 2022.

[3] Jessica Florencia, Thierry Moyaux, Lorraine Trilling, Guillaume Bouleux, and Vincent Cheutet. Towards improving dynamic resource scheduling in the context of digital twin of emergency department. *IEEE Trans. on Automation Science and Engineering*, pages 1-13.

[4] Edmund Burke, Patrick De Causmaecker, Greet Vanden Berghe, and Hendrik Van Landeghem. The state of the art of nurse rostering. *J. Scheduling*, 7:441-499, 11 2004.

[5] Oliver Strömgren. Usage of constraint programming for nurse rostering problems - A literature study. Final thesis, Linköpings universitet, Sweden, 2015.

[6] Lorraine Trilling, Alain Guinet, and Dominique Le Magny. Nurse scheduling using integer linear programming and constraint programming. In *Proc. of 12th IFAC Symposium on Information Control Problems in Manufacturing*, IFAC Proc. Volumes, volume 39, page 671-676, 2006.

[7] Kjartan Kastet Klyve, Ilankaikone Senthooran, and Mark Wallace. Nurse rostering with fatigue modelling. *Health Care Manag Sci*, 26:21-45, 2023.

[8] Lahcene Mezouari, Lucas Wicher, Jean-Paul Boufflet, and Aziz Moukrim. Scheduling in an emergency department, linear formulation and heuristic approach. In *9th Int. Conf. on Control, Decision and Information Technologies (CoDIT)*, pages 1547-1552. IEEE, 2023.

[9] Venkataramanaiah Saddikuti and Pavan Kumar Gudavalleti. Dual resource scheduling in trauma care centre with time varying patient demand. In *Proc. of 26th Int. Conf. on Production Research*, page 867-883. Springer, 2023.

[10] Maria Di Mascolo, Marie-Laure Espinouse, and Can Erdem Ozkan. Synchronization between human resources in home health care context. In *Proc. of the Int. Conf. on Health Care Systems Engineering*, pages 73-86. Springer, 2013.

[11] Ricardo Magalhães, Susana Vieira, and João Sousa. Threat elimination algorithm for dual resource constrained flexible job shop scheduling problems. In *Proc. 10th IFAC Conf. on Manuf. Modelling, Manag. & Control (MIM)*, volume 55, page 2288-2293, Nantes, France, 2022.

[12] Christian Almeder and Bernardo Almada-Lobo. Synchronisation of scarce resources for a parallel machine lotsizing problem. *Int. J. of Production Research*, 49(24):7315-7335, 2011.

[13] Carla Juvin, Laurent Houssin, and Pierre Lopez. Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty. In *Int. Conf. on Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, pages 354-369. Springer, 2023.

[14] Bahman Naderi, Rubén Ruiz, and Vahid Roshanaei. Mixed-integer programming vs. constraint programming for shop scheduling problems: new results and outlook. *INFORMS Journal on Computing*, 35(4):817-843, 2023.

[15] Aidin Delgoshaei, Mohd Khairol Anuar Mohd Ariffin, Sepehr Maleki, and Zulkifle Leman. Review evolution of dual-resource-constrained scheduling problems in manufacturing systems: modeling and scheduling methods' trends. *Soft computing*, 27(24):18489-18528, 2023.