Sommaire

Introduction
Contexte de la problématique hospitalière
Méthodologie et modélisation
3.1. Modélisation mathématique du problème
3.2. Méthodes de résolution existantes
Approches métaheuristiques pour l’ordonnancement
4.1. Algorithme de recherche Tabou
4.2. Algorithme de Recuit Simulé
4.3. Algorithme Génétique
4.4. Systèmes Multi-Agents
Simulation des résultats et comparaison des algorithmes
Approche par Apprentissage par Renforcement (RL)
6.1. Principe du Q-Learning
6.2. Application au problème d’ordonnancement
Conclusion
Introduction

Les services d’urgences hospitalières sont confrontés à des défis logistiques majeurs liés à
l’afflux imprévisible de patients et à la limitation des ressources disponibles (personnel,
matériel, lits). La logistique hospitalière vise à gérer au mieux ces flux de patients et
d’informations afin d’offrir des soins optimaux tout en respectant des contraintes
organisationnelles strictes.

Les urgences fonctionnent 24h/24 et sont souvent le point d’entrée principal des patients à
l’hôpital, ce qui les place en situation de tension permanente. En effet, on observe
fréquemment un déséquilibre entre la demande croissante de soins en urgence et les
ressources disponibles pour y répondre. Ce déséquilibre impacte directement la qualité de
prise en charge : augmentation du temps d’attente, engorgement des unités, stress du
personnel et baisse de la satisfaction des patients.

Dans ce contexte, optimiser l’ordonnancement des patients aux urgences est un levier
important pour améliorer l’efficacité du service. Cependant, ce problème s’avère complexe
et de nature NP-difficile, car il comporte de nombreuses contraintes et un environnement
dynamique et incertain.

Chaque patient doit suivre un certain nombre d’opérations (examens, interventions,

analyses) impliquant possiblement différentes compétences médicales (types de
ressources), devant être réalisées dans un ordre donné. De plus, l’ordre des interventions
pour un même patient doit être respecté (par ex. un patient doit d’abord passer un examen
d’imagerie avant une intervention chirurgicale). Ces contraintes d’ordonnancement couplées
à l’imprévisibilité du flux de patients rendent le problème difficile à résoudre par des
approches exactes classiques dès que la taille du problème augmente.

Face à ces difficultés, on se tourne vers des méthodes avancées d’optimisation. Ce rapport
présente un projet de recherche qui explore plusieurs approches pour améliorer
l’ordonnancement des patients aux urgences : des métaheuristiques (Recherche Tabou,
Recuit Simulé, Algorithme Génétique, Systèmes Multi-Agents) et une approche par
Apprentissage par Renforcement (Q-Learning). Nous détaillerons le contexte hospitalier du
problème, la modélisation et la méthodologie employée, puis les principes des algorithmes
utilisés. Nous comparerons ensuite les performances obtenues à l’aide de résultats de
simulation, avant de discuter l’apport potentiel de l’apprentissage par renforcement. Enfin,
nous conclurons sur les contributions, limites et perspectives de ce travail.
Contexte de la problématique hospitalière

Le service des urgences est un système complexe où convergent en temps réel de multiples
patients avec des besoins variés, devant être traités par un personnel et des équipements
limités. La problématique centrale réside dans la gestion de la tension entre la charge de
travail (nombre de patients, gravité des cas, taux d’occupation des salles) et la capacité du
service (nombre de médecins et d’infirmiers, lits et équipements disponibles). Lorsque la
demande excède la capacité, il en résulte un engorgement : allongement des temps
d’attente, patients traités sur des brancards, redirection vers d’autres hôpitaux, etc.

Plusieurs indicateurs permettent de suivre cette tension : le nombre de patients pris en

charge (par heure/jour), le taux d’occupation des salles, les délais d’attente moyens, la
durée de séjour aux urgences, ou encore le nombre de patients quittant le service sans avoir
été vus. Ces indicateurs reflètent l’équilibre (ou le déséquilibre) entre charge et capacité du
service et un déséquilibre prolongé peut conduire à un phénomène de saturation des
urgences, désormais bien connu sous le terme de “crise des urgences”.

Pour remédier à ces problèmes, les hôpitaux cherchent à optimiser l’organisation interne
des urgences. Cela passe notamment par une meilleure planification de l’enchaînement des
soins pour chaque patient en fonction des ressources disponibles (ordonnancement). Un
ordonnancement efficace vise à réduire les temps d’attente inutiles, à augmenter l’utilisation
des ressources sans créer de surcharge, et à prioriser les patients de manière appropriée
selon la gravité. Cependant, le caractère dynamique et incertain des urgences (arrivées
aléatoires de patients, durée variable des actes, urgences vitales imprévisibles) complexifie
la tâche. On a donc besoin de solutions capables d’adapter rapidement le planning aux
changements et de fournir des solutions satisfaisantes en un temps de calcul raisonnable.

3.1 Modélisation mathématique du problème

Pour étudier le problème, nous avons tout d’abord formalisé une modélisation mathématique
simplifiée de l’ordonnancement aux urgences. Dans notre modèle, nous considérons un
ensemble de patients P={1,2,3,…,n} arrivés sur une période T donnée. Chaque patient $i$
doit suivre une séquence d’opérations $O_{i1}, O_{i2}, \dots, O_{im}$ (par exemple :
examens, analyses, interventions), chacune nécessitant une ou plusieurs compétences (ou
ressources) parmi un ensemble $C = {C1, C2, \dots, C_k}$. Une compétence peut
représenter un type de médecin (radiologue, urgentiste…), un équipement médical (scanner,
IRM…), ou une salle spécifique. Chaque opération $O_{ij}$ a une durée fixe (par exemple 3
unités de temps dans nos simulations). Les contraintes principales du modèle sont les
suivantes :
Les opérations d’un même patient doivent être exécutées dans l’ordre (ordre préétabli par le
protocole médical)
file-rzq49mfx3yy5rn36rfq4uy
. Autrement dit, pour chaque patient $i$, $O_{i2}$ ne peut débuter qu’une fois $O_{i1}$
terminée, etc.
Une compétence ne peut traiter qu’une opération à la fois : si deux opérations requièrent la
même compétence (par ex. le même médecin spécialiste), elles ne peuvent pas se
chevaucher dans le temps sur cette ressource
file-rzq49mfx3yy5rn36rfq4uy
. En revanche, deux opérations de patients différents peuvent être effectuées en parallèle
sur des compétences différentes (ex: un patient au scanner pendant qu’un autre est en
chirurgie).
L’objectif principal de l’optimisation est de minimiser le makespan, c’est-à-dire la durée totale
nécessaire pour compléter toutes les opérations de tous les patients
file-rzq49mfx3yy5rn36rfq4uy
. Minimiser le makespan revient à essayer de finir de traiter l’ensemble des patients le plus
tôt possible, ce qui réduit l’engorgement. Secondairement, on cherche à minimiser les
conflits et temps d’attente – c’est-à-dire éviter que des patients ou des ressources restent
inactifs trop longtemps – et à équilibrer la charge sur les différentes compétences (ne pas
surutiliser certaines ressources pendant que d’autres restent inutilisées). En résumé, notre
problème peut s’apparenter à un problème d’ordonnancement d’atelier ouvert (open-shop
scheduling), où chaque “job” (patient) est une suite de tâches à effectuer dans un ordre
donné, et chaque tâche requiert une ou plusieurs “machines” (compétences) spécifiques. Ce
type de problème est NP-difficile, ce qui justifie l’utilisation d’approches approximatives pour
le résoudre.
3.2 Méthodes de résolution existantes
Plusieurs approches ont été explorées dans la littérature pour optimiser l’ordonnancement
hospitalier, chacune ayant ses avantages et limites
file-rzq49mfx3yy5rn36rfq4uy
file-rzq49mfx3yy5rn36rfq4uy
. Les méthodes classiques d’optimisation exacte (telles que la programmation linéaire en
nombres entiers – PLNE) peuvent fournir des solutions optimales pour des instances de
petite taille bien structurées, mais elles deviennent rapidement inapplicables lorsque le
nombre de patients et de ressources croît, du fait de l’explosion combinatoire du problème.
Des approches de programmation stochastique intègrent l’incertitude (par ex. distribution de
la durée des opérations ou des arrivées de patients) dans le modèle, mais elles nécessitent
de connaître les distributions de probabilité et sont computationnellement très lourdes
file-rzq49mfx3yy5rn36rfq4uy
. La simulation est une autre technique utilisée pour évaluer différentes stratégies
d’organisation dans un environnement virtuel reproduisant le fonctionnement des urgences.
Elle permet de tester des scénarios complexes sans risque pour le réel et d’obtenir des
indicateurs de performance. Cependant, la simulation seule ne fournit pas directement de
solution optimisée – elle sert plutôt à évaluer une politique donnée
file-rzq49mfx3yy5rn36rfq4uy
. Compte tenu de la complexité du problème, les métaheuristiques se révèlent
particulièrement pertinentes. Ce sont des algorithmes d’optimisation approximés qui
explorent intelligemment l’espace des solutions afin de trouver de bons compromis en un
temps raisonnable, sans garantir d’optimalité. Parmi celles-ci, la Recherche Tabou, le Recuit
Simulé et les Algorithmes Génétiques ont été largement étudiés en ordonnancement. Ces
méthodes se distinguent par leur mécanisme d’exploration : Tabou évite les retours en
arrière en mémorisant les mouvements interdits (tabous)
file-rzq49mfx3yy5rn36rfq4uy
, le Recuit Simulé accepte parfois des solutions moins bonnes pour s’échapper des optima
locaux
file-rzq49mfx3yy5rn36rfq4uy
, et l’Algorithme Génétique s’inspire de l’évolution naturelle pour recombiner des solutions et
en sélectionner les meilleures
file-rzq49mfx3yy5rn36rfq4uy
. Plus récemment, des approches innovantes telles que les Systèmes Multi-Agents (SMA)
ou les algorithmes inspirés de la nature (colonies de fourmis, essaims de particules) ont
émergé. Un SMA met en œuvre plusieurs agents autonomes coopérant ou compétant pour
construire une solution, offrant une grande adaptabilité et une capacité de collaboration
file-rzq49mfx3yy5rn36rfq4uy
file-rzq49mfx3yy5rn36rfq4uy
. Cependant, ces approches peuvent être complexes à modéliser et paramétrer
correctement. Des approches hybrides combinant plusieurs méthodes ont également été
proposées pour tirer parti des forces de chacune
file-rzq49mfx3yy5rn36rfq4uy
. Dans ce projet, nous avons concentré nos efforts sur les métaheuristiques Tabou, Recuit
Simulé, Algorithme Génétique, et sur une réflexion autour d’un Système Multi-Agents. Ces
choix sont motivés par leur capacité à gérer les environnements dynamiques et incertains
tout en fournissant des solutions de bonne qualité dans des temps de calcul limités
file-rzq49mfx3yy5rn36rfq4uy
. Les sections suivantes présentent en détail le fonctionnement de chacun de ces
algorithmes et leur adaptation à notre problématique d’ordonnancement.
Approches métaheuristiques pour l’ordonnancement
4.1 Algorithme de recherche Tabou
Principe général : La Recherche Tabou (Tabu Search) est une métaheuristique itérative de
recherche locale qui vise à éviter les boucles et les optima locaux en mémorisant les
dernières solutions visitées dans une liste dite tabou. L’algorithme part d’une solution initiale
(éventuellement générée aléatoirement), puis, de proche en proche, il explore les solutions
voisines en appliquant des mouvements (modifications locales de la solution courante). À
chaque itération, on accepte la meilleure solution voisine même si elle est moins bonne,
mais on interdit (met tabou) pour un certain nombre d’itérations les mouvements inverses
pour ne pas revenir en arrière
file-rzq49mfx3yy5rn36rfq4uy
. Cela permet de diversifier la recherche et d’explorer de nouvelles zones de l’espace des
solutions. Adaptation au problème : Pour notre problématique, une solution peut être
représentée par un planning détaillant l’ordre de réalisation de toutes les opérations (avec
l’affectation des compétences et les séquences par patient). Un mouvement voisin typique
consiste à échanger deux opérations de patients différents dans la séquence, tout en
respectant l’ordre interne de chaque patient (contrainte d’ordre strict) – par exemple,
intervertir un examen du patient A avec une analyse du patient B dans la séquence, ce qui
modifie le planning global. La fonction objectif calcule le makespan (temps total) de la
solution et éventuellement des pénalités si des contraintes sont violées. L’algorithme Tabou
va donc chercher à réduire le makespan tout en évitant de retomber sur des séquences déjà
explorées grâce à la liste tabou
file-rzq49mfx3yy5rn36rfq4uy
file-rzq49mfx3yy5rn36rfq4uy
. Paramètres : Les principaux paramètres incluent la taille de la liste tabou
(combien de solutions ou mouvements passés on garde en mémoire) et le
nombre maximal d’itérations sans amélioration avant d’arrêter. Un mécanisme
d’aspiration peut être utilisé pour outrepasser le tabou si une solution voisine est
vraiment meilleure que la meilleure trouvée jusqu’alors. Le bon réglage de ces
paramètres est important pour les performances (une liste tabou trop courte
peut laisser revenir trop vite à un optimum local, trop longue peut brider la
recherche). Résultats observés : L’algorithme Tabou s’est révélé très efficace
pour réduire rapidement le makespan. Sur nos instances de test (par exemple 10
patients, 6 compétences), on observe une diminution notable du makespan dès
les premières itérations. Par exemple, dans une simulation, le planning initial
produisait un makespan équivalent à 14 unités de temps, et la recherche tabou
l’a réduit à 12 unités. Cette réduction rapide (≈ –15%) s’accompagne d’une
élimination quasi-complète des conflits de ressources (chevauchements) grâce
aux échanges d’opérations qui désaturent les compétences surchargées. La
Figure 1 illustre un exemple de planning initial aléatoire pour 10 patients et 6
compétences, tel qu’engendré par une solution initiale naïve. On voit que
certaines compétences (lignes) restent inactives sur des périodes (bandes
blanches) tandis que d’autres enchaînent les tâches jusqu’à la fin (ex: Comp1 se
termine en dernier vers $t=15$). Après optimisation par Tabou, le planning est
resserré et ces périodes creuses sont comblées, ce qui permet de terminer plus
tôt.

Figure 1 : Exemple de planning initial (aléatoire) pour 10 patients sur 6 compétences.

Chaque couleur correspond à un patient différent, et chaque ligne représente l’agenda d’une
compétence (ressource). Des cases blanches indiquent des temps où la ressource est
inactive. Dans cet exemple, le temps total d’ordonnancement (makespan) est de 15 unités
de temps. Un autre avantage de Tabou est sa capacité à maintenir une charge de travail
homogène entre compétences : il tend à équilibrer le nombre d’opérations par ressource en
déplaçant les tâches de manière à utiliser les ressources moins occupées. Son temps de
calcul est relativement faible pour des instances modérées, car il converge en général en
peu d’itérations vers une bonne solution. En revanche, il peut être sensible aux paramètres
(taille de liste tabou, critère d’arrêt) et nécessite un ajustement empirique.
4.2 Algorithme de Recuit Simulé
Principe général : Le Recuit Simulé (Simulated Annealing) est une métaheuristique inspirée
du processus de refroidissement du métal en métallurgie. Il s’agit d’une recherche locale qui
accepte parfois des solutions moins bonnes pour échapper aux optima locaux, avec une
probabilité qui diminue au fil du temps. Concrètement, on définit une température initiale
suffisamment élevée qui correspond à un haut degré de hasard dans l’acceptation des
mouvements défavorables. Au début, l’algorithme peut explorer librement en acceptant
certaines détériorations de la solution (ce qui permet de sauter hors des minima locaux)
file-rzq49mfx3yy5rn36rfq4uy
. Puis la température décroît progressivement selon un facteur de refroidissement, réduisant
la probabilité d’accepter de mauvais mouvements, jusqu’à ce que l’algorithme se fige autour
d’un optimum local une fois “froid”
file-rzq49mfx3yy5rn36rfq4uy
. Adaptation au problème : Pour notre ordonnancement, le Recuit Simulé commence aussi
par un planning initial (généré aléatoirement ou via une heuristique). À chaque itération, on
génère un voisin du planning courant (par exemple en déplaçant une opération à un autre
endroit ou en échangeant deux opérations comme pour Tabou). Si ce voisin améliore le
makespan, il est accepté; sinon, il peut être accepté avec une probabilité $p = \exp(-\Delta /
T)$ où $\Delta$ est la dégradation du critère et $T$ la température courante. Ainsi, au début
(température haute), même des solutions nettement moins bonnes peuvent être acceptées,
ce qui favorise l’exploration large de l’espace des plannings
file-rzq49mfx3yy5rn36rfq4uy
. Au fur et à mesure que $T$ diminue, le critère se durcit et seuls de légers reculs peuvent
encore être acceptés. Les paramètres clés à régler sont la température initiale $T_0$ (elle
doit être choisie pour qu’au début ~80% des mouvements défavorables soient acceptés,
typiquement), le taux de refroidissement (par exemple multiplier $T$ par 0,97 à chaque
itération, ce qui correspond à une diminution de 3%
file-rzq49mfx3yy5rn36rfq4uy
) et les critères d’arrêt (par exemple un nombre maximum d’itérations ou une température
plancher). Ces paramètres ont une grande influence sur le résultat et nécessitent une
calibration fine. Résultats observés : Le Recuit Simulé a montré une bonne exploration de
l’espace des solutions, parfois meilleure que Tabou pour échapper à certains optima locaux
grâce à l’acceptation transitoire de solutions moins performantes. Sur nos tests, il a pu
légèrement surpasser Tabou en qualité finale dans quelques cas, mais au prix d’un temps
de calcul plus élevé dû à un plus grand nombre d’itérations. Typiquement, on observe une
réduction progressive du makespan : il descend par paliers au fur et à mesure du
refroidissement, sans rebonds puisque les détériorations acceptées deviennent de plus en
plus rares. Le Recuit gère bien les conflits en explorant largement des plannings très
différents, et il s’adapte aux contraintes complexes en ayant la possibilité de temporairement
violer certaines contraintes (par ex. accepter un chevauchement mineur qui sera corrigé plus
tard), ce qui permet parfois de sortir des impasses pour ensuite les résoudre. Toutefois, il
faut veiller à ce que la température ne refroidisse pas trop vite pour laisser le temps
d’explorer suffisamment – un refroidissement mal calibré peut conduire à une convergence
prématurée. En pratique, notre implémentation avec $T_{init}=100$, refroidissement $0.99$
par étape et $2000$ itérations max a donné de bons résultats, le makespan final étant
proche de celui obtenu par Tabou (écart < 5% dans la plupart des cas), mais avec un temps
CPU un peu plus important.
4.3 Algorithme Génétique
Principe général : Les Algorithmes Génétiques (AG) s’inspirent de la théorie de l’évolution
biologique. Ils maintiennent une population de solutions (plannings) qui évolue au fil des
générations. À chaque génération, les solutions sont évaluées selon la fonction objectif (ici
le makespan principalement). On sélectionne alors les meilleures (survivants) et on génère
de nouvelles solutions en croisant entre elles des solutions existantes (échanges de
segments de planning, analogues au mélange de chromosomes) et en appliquant des
mutations aléatoires (petites modifications aléatoires d’un planning). L’espoir est que la
recombinaison de bonnes solutions produise une descendance encore meilleure, tout en
maintenant de la diversité grâce aux mutations. Adaptation au problème : Pour représenter
un planning en tant que chromosome, il faut trouver un encodage adapté. Nous avons choisi
de représenter chaque solution par une séquence ordonnée de toutes les opérations, avec
un identifiant pour le patient et l’opération, ce qui s’apparente à une permutation contrainte.
Afin de conserver la faisabilité (ordre interne des opérations de chaque patient), on utilise un
opérateur de croisement spécifique qui préserve ces précédences : par exemple, on peut
prendre un préfixe du séquençage de la mère et compléter avec les opérations restantes
dans l’ordre où elles apparaissent chez le père (order crossover modifié pour contraintes)
file-rzq49mfx3yy5rn36rfq4uy
. Les mutations peuvent consister à échanger deux opérations adjacentes ou à insérer une
opération à un autre endroit, de manière aléatoire, tout en veillant à ne pas casser l’ordre
des opérations d’un même patient. Les paramètres à fixer comprennent la taille de
population initiale, le nombre de générations à simuler, le taux de croisement (probabilité de
croiser deux parents) et le taux de mutation. Par exemple, nous avons utilisé une population
de 20 plannings initiaux (générés aléatoirement), sur 2000 générations, avec un taux de
croisement de 0,75 et de mutation de 0,025. Ces valeurs ont été choisies empiriquement en
se basant sur la littérature et quelques tests préliminaires. Résultats observés : L’algorithme
génétique a l’avantage d’explorer en parallèle de multiples solutions, ce qui le rend robuste
sur des cas dynamiques et moins susceptible de rester piégé dans un optimum local unique.
Sur nos instances, il a effectivement permis de trouver des plannings différents de ceux
obtenus par Tabou ou Recuit. Cependant, la convergence est relativement lente : on a
constaté qu’il fallait de nombreuses générations pour obtenir une amélioration sensible du
makespan. Par exemple, le GA a initialement une réduction rapide (les premières
générations éliminent les pires conflits), mais ensuite le progrès se fait par petites touches
au fil des croisements. Au final, la qualité obtenue était modérément meilleure que l’initial,
mais parfois légèrement inférieure à Tabou ou Recuit pour un temps de calcul équivalent.
Dans nos tests, l’AG a pu réduire le makespan d’environ 10-15% par rapport au planning
initial, ce qui est bien mais un peu en deçà des 15-20% obtenus via Tabou dans le même
temps. Ce comportement concorde avec la littérature, où les AG peuvent être moins
performants sur de petites instances, mais s’adaptent bien à des environnements évolutifs
(par exemple, si de nouveaux patients arrivent, on peut intégrer leur tâches dans la
population et relancer l’évolution). L’AG offre aussi une grande flexibilité pour intégrer de
nouveaux critères dans la fonction d’évaluation (on pourrait par exemple y inclure la
minimisation du temps d’attente moyen ou l’équité de traitement entre patients). Sa
sensibilité aux paramètres est notable : un mauvais réglage du taux de mutation ou de la
population peut conduire soit à une convergence prématurée (population trop homogène)
soit à une stagnation (trop de diversité empêche d’affiner). Dans l’ensemble, l’algorithme
génétique est apparu comme une approche complémentaire intéressante, capable de fournir
des solutions diversifiées, mais demandant plus de temps pour atteindre la performance de
Tabou ou du Recuit Simulé sur notre cas.
4.4 Systèmes Multi-Agents
Principe général : Un Système Multi-Agents (SMA) implique plusieurs agents intelligents
interagissant dans un environnement commun pour résoudre un problème complexe.
Appliqué à l’optimisation, on peut imaginer que chaque agent représente par exemple une
solution candidate, ou une partie de la solution, et que ces agents coopèrent ou entrent en
compétition afin d’améliorer collectivement la solution. Les agents peuvent partager des
informations, adapter leur comportement, et se répartir les tâches. Cette approche
décentralisée est inspirée de phénomènes naturels ou sociologiques (colonies, marchés,
etc.), et elle est réputée pour sa forte adaptabilité – les agents peuvent réagir
individuellement aux changements de l’environnement – et sa capacité à explorer
simultanément plusieurs trajectoires de solution. Adaptation au problème : Pour notre projet,
nous avons envisagé un SMA où chaque agent serait une métaheuristique travaillant sur un
planning. Par exemple, un agent-Tabou, un agent-Recuit, un agent-Génétique, etc., chacun
cherchant une solution optimale selon sa stratégie. Ces agents pourraient échanger des
informations sur leurs meilleures solutions trouvées (par exemple, partager un fragment de
planning particulièrement efficace)
file-rzq49mfx3yy5rn36rfq4uy
. On peut également imaginer des agents associés à chaque compétence ou à chaque
patient, qui négocient l’ordre de passage des opérations : un agent-ressource essaye de
minimiser son temps d’inactivité, tandis qu’un agent-patient essaye de minimiser son temps
d’attente, et ils trouvent un compromis via un protocole d’interaction. Dans le cadre de notre
implémentation, nous avons surtout étudié un scénario où les agents sont des “jumeaux
numériques” des algorithmes : ils exécutent chacun leur métaheuristique en parallèle sur
des solutions différentes, et à intervalle régulier, ils comparent leurs résultats. Le système
peut alors adapter les stratégies : par exemple, si l’agent-Tabou obtient de très bons
résultats, les autres peuvent décider de ré-initialiser leur population autour de la solution du
Tabou (phénomène de coopération). Inversement, si tous stagnent, chaque agent peut
changer certains paramètres (température pour Recuit, taux de mutation pour GA, etc.) ou
explorer de nouveaux mouvements
file-rzq49mfx3yy5rn36rfq4uy
file-rzq49mfx3yy5rn36rfq4uy
. Ainsi, le SMA agit comme une couche meta qui orchestre plusieurs méthodes en parallèle.
Avantages et limites : Le SMA apporte une grande flexibilité face aux scénarios complexes
ou changeants : chaque agent peut se spécialiser dans un aspect (par ex. un agent pourrait
se focaliser sur réduire les conflits pendant qu’un autre réduit le makespan) et l’ensemble
peut s’adapter en temps réel si de nouveaux patients arrivent ou si une ressource devient
indisponible (panne, absence d’un médecin). C’est une approche prometteuse notamment
pour les situations dynamiques et pour intégrer de la robustesse (par ex. tolérance aux
données incertaines, un agent détecte si une solution devient invalide et les autres
réagissent)
file-rzq49mfx3yy5rn36rfq4uy
file-rzq49mfx3yy5rn36rfq4uy
. Néanmoins, la complexité de modélisation est élevée : il faut définir les règles d’interaction,
le protocole de communication entre agents, la fonction d’évaluation partagée, etc. Si ces
éléments sont mal calibrés, le SMA peut avoir du mal à converger (agents en conflit) ou au
contraire se comporter comme un seul agent équivalent (pas de gain par rapport à une
seule métaheuristique). De plus, la mise au point et le débogage d’un SMA sont plus
difficiles du fait de l’asynchronisme et de l’aléatoire introduit par les interactions. Faute de
temps, nous avons principalement élaboré le concept sans aboutir à une implémentation
complète. Les résultats escomptés seraient au minimum équivalents aux meilleures
métaheuristiques prises individuellement, avec l’espoir d’une amélioration supplémentaire
grâce à la synergie (par ex. atteindre une solution de makespan 11 là où chaque algorithme
seul bloquait à 12). Cela reste une piste à approfondir dans de futurs travaux.
Simulation des résultats et comparaison des algorithmes
Pour évaluer ces différentes approches, nous avons développé une simulation en Python
permettant de générer des instances aléatoires du problème (patients, opérations,
compétences) et d’appliquer les algorithmes Tabou, Recuit Simulé et Génétique. Les
instances types comportent $n=10$ patients, chacun ayant jusqu’à 5 opérations à effectuer,
nécessitant parmi 6 compétences disponibles. Chaque opération dure 3 unités de temps (s’il
nécessite une compétence) et certaines opérations peuvent être vides (par exemple un
patient n’a que 3 opérations effectives sur 5 étapes prévues, les autres étant sans
compétence donc sans durée) – ceci modélise des étapes éventuellement annulées ou très
courtes. On part en général d’un planning initial aléatoire où les opérations sont
ordonnancées naïvement (par ex. dans un ordre aléatoire respectant juste l’ordre des
patients). La Figure 1 présentée plus haut montrait un exemple de tel planning initial. On y
observe un makespan de 15 (unité de temps) dans cet exemple particulier, avec des
ressources finissant à des temps différents et des inactivités visibles. Chaque algorithme a
ensuite été exécuté sur ces instances, et nous avons comparé la performance finale
obtenue (en termes de makespan minimal) ainsi que la vitesse de convergence. Le Tableau
1 ci-dessous synthétise qualitativement les résultats obtenus et les caractéristiques
observées pour chaque méthode : Tableau 1 – Comparaison des approches
métaheuristiques sur un cas d’ordonnancement de patients aux urgences (10 patients, 6
compétences)
Critère Algorithme Tabou Recuit Simulé (RS) Algorithme Génétique
Optimisation du makespan Réduction rapide et significative du makespan
(par ex. 14 → 12) en quelques itérations. Réduction progressive grâce à une
exploration large des solutions (amélioration graduelle tout au long du
refroidissement). Réduction modérée, dépendante du nombre de générations;
amélioration notable surtout à long terme.
Gestion des conflits Élimine efficacement les chevauchements : minimise strictement les
conflits de ressources (ordonnancements sans doublons sur une même compétence).
Évite en grande partie les conflits grâce à l’exploration de configurations variées
(peut accepter temporairement un conflit pour en sortir ensuite). Parvient à minimiser les
conflits sur plusieurs générations, bien que quelques conflits mineurs puissent persister
initialement.
Équilibrage des ressources Tend à équilibrer la charge : chaque compétence traite un
nombre de tâches similaire (charge homogène) grâce aux échanges de tâches. Atteint un
certain équilibre via l’ajustement progressif des solutions (réduit l’inactivité des ressources
au fil des itérations). Explore de nombreuses répartitions possibles : obtient un équilibrage
flexible, affiné au fil des générations par sélection naturelle.
Flexibilité face aux contraintes Efficace surtout si les contraintes sont fixes et bien
définies (meilleures performances sur un problème stable). S’adapte mieux aux contraintes
complexes ou changeantes (peut intégrer de nouvelles conditions en cours de route grâce à
l’exploration aléatoire). Explore des solutions sous différentes contraintes via la
diversité de la population; potentiellement robuste même si l’environnement change pendant
l’évolution.
Temps de calcul Très rapide : bonne solution atteinte en peu d’itérations (en
seconds/minutes pour $n=10$). Dépend des paramètres : un refroidissement lent
augmente le temps (peut être plus long que Tabou si beaucoup d’itérations nécessaires).
Plusieurs générations requises pour converger, donc temps plus important (peut
nécessiter minutes supplémentaires comparé à Tabou/RS).
Simplicité de paramétrage Paramètres relativement simples (taille liste tabou, itérations)
mais choix crucial de ces valeurs. Demande une calibration fine de la température initiale
et du schéma de refroidissement pour bien performer. Sensible à la taille de population
et taux de mutation/croisement – nécessite ajustements empiriques, sinon convergence non
garantie.
Adaptabilité (scénarios complexes/dynamiques) Convient à des problèmes de taille
modérée; peut nécessiter adaptation pour des scénarios très dynamiques (pas conçu pour
modifier la solution en cours de route sans relancer). Performant sur des scénarios
complexes : gère bien la complexité et peut potentiellement s’adapter à de légers
changements en continuant le [Link] pour des cas dynamiques : la population peut
intégrer progressivement de nouvelles données (nouveaux patients) et y adapter les
solutions.
En complément de ce tableau, la Figure 2 illustre la convergence typique de l’algorithme
Tabou sur une instance de test. On y trace la valeur du meilleur makespan trouvé en
fonction des itérations. On constate une forte diminution dans les premières étapes, puis un
plateau une fois la solution stabilisée autour du minimum trouvé. Ce comportement en
“escalier” est caractéristique : Tabou améliore par à-coups quand il trouve une meilleure
solution, et explore latéralement lorsqu’il est dans un plateau (jusqu’à trouver un nouveau
voisin prometteur).

Figure 2 : Exemple de convergence de la recherche Tabou. La courbe montre le meilleur

makespan trouvé en fonction des itérations. On observe des améliorations franches au
début (chutes de la courbe) puis un palier lorsque l’algorithme atteint une solution quasi-
optimale. Chaque saut correspond à la découverte d’une solution voisine améliorant le
record actuel. Dans l’ensemble, nos expériences confirment que la Recherche Tabou offre
le meilleur compromis rapidité/efficacité pour ce problème particulier, réussissant très vite à
ordonnancer les tâches de manière à gagner du temps (baisse du makespan) tout en évitant
les conflits. Le Recuit Simulé est presque aussi performant en qualité finale et apporte
davantage de robustesse vis-à-vis des optima locaux, au prix d’un temps de calcul un peu
accru. L’Algorithme Génétique, lui, donne des résultats honorables et très flexibles, mais
demande un nombre d’itérations (générations) plus important pour atteindre une solution de
qualité comparable – ce qui, pour des instances statiques de taille modérée, le rend un peu
moins compétitif. Toutefois, le GA pourrait surpasser les autres si l’on complexifie le
problème (plus de patients, arrivées en temps réel) grâce à sa capacité à évoluer et à
s’adapter en continu. Quant au Système Multi-Agents, faute de résultats quantitatifs
complets, nous ne l’avons pas inclus dans le tableau. Néanmoins, on peut anticiper qu’il
tirerait profit des points forts de chaque approche. Par exemple, un SMA combinant Tabou
et Recuit pourrait probablement obtenir un makespan aussi bas que le meilleur des deux,
voire légèrement mieux, en exploitant la diversification du Recuit et l’intensification du Tabou
simultanément. L’enjeu est de vérifier que le surcoût de coordination entre agents ne vient
pas annuler ces gains.
Approche par Apprentissage par Renforcement (RL)
Enfin, une partie exploratoire de ce projet a concerné l’application de l’Apprentissage par
Renforcement (Reinforcement Learning – RL) à notre problème d’ordonnancement. L’idée
est d’utiliser un agent apprenant capable d’améliorer sa politique d’ordonnancement au fil de
l’expérience, sans supervision directe, en interagissant avec un environnement simulant les
urgences.
6.1 Principe du Q-Learning
Le Q-Learning est l’un des algorithmes de RL les plus connus. Il se base sur le formalisme
des Processus de Décision Markovien (MDP), où à chaque étape, l’agent observe un état
$s$ de l’environnement, choisit une action $a$, ce qui le fait passer dans un nouvel état $s'$
tout en recevant une récompense $r$ associée à la transition
file-2napbpfrhbesjdjdh4eza2
file-2napbpfrhbesjdjdh4eza2
. Le but de l’agent est de maximiser la récompense totale cumulée au cours du temps. Dans
le Q-Learning, l’agent apprend une fonction de valeur $Q(s,a)$ estimant l’utilité de faire
l’action $a$ dans l’état $s$. A chaque interaction, il met à jour cette valeur selon la règle de

𝑄
Bellman :

new
𝑠
(

𝑎
,

𝑄
←

𝑠
(

𝑎
,

𝛼
+

𝑟
[

𝛾
+

max

𝑎
⁡

𝑄
′

𝑠
(

𝑎
,

′
)

𝑄
−

𝑠
(

𝑎
,

)
]
Q
new

(s,a)←Q(s,a)+α[r+γmax
a
′

Q(s
′
 ,a
′
)−Q(s,a)] où $\alpha$ est le taux d’apprentissage (learning rate) et $\gamma$
le facteur d’actualisation qui pondère l’importance des récompenses futures
file-2napbpfrhbesjdjdh4eza2
. Ce processus d’apprentissage incrémental, répété sur de très nombreux épisodes, finit
(théoriquement) par faire converger $Q(s,a)$ vers la valeur réelle de la politique optimale.
Un aspect crucial est le dilemme exploration/exploitation : l’agent doit à la fois exploiter les
actions qu’il pense bonnes (pour récolter des récompenses) et explorer de nouvelles actions
pour améliorer ses connaissances
file-2napbpfrhbesjdjdh4eza2
. En pratique, on utilise souvent une stratégie $\epsilon$-gourmande : avec probabilité $1-\
epsilon$ l’agent choisit l’action ayant le meilleur $Q$ connu (exploitation), et avec probabilité
$\epsilon$ il choisit une action aléatoire (exploration). $\epsilon$ est souvent décroissant au
fil du temps pour favoriser l’exploitation une fois l’agent suffisamment entraîné.
6.2 Application au problème d’ordonnancement
Pour appliquer le RL à l’ordonnancement des urgences, il faut définir :
L’état $s$ : une représentation pertinente de la situation du système à un instant donné.
D’après notre problématique, un état pourrait inclure par exemple le nombre de patients en
attente, la liste des opérations en cours ou prêtes à démarrer, et la disponibilité des
compétences à cet instant. On peut aussi y inclure l’heure actuelle, ou des indicateurs
comme le temps d’attente moyen actuel, etc. Plus l’état est informatif, plus l’agent pourra
prendre de décisions fines, mais cela augmente la taille de l’espace d’états (donc la
complexité d’apprentissage).
L’action $a$ : que peut faire l’agent pour agir sur l’ordonnancement ? Plusieurs choix de
granularité sont possibles. Une action pourrait être de sélectionner le prochain patient à
prendre en charge (décider quel patient sort de la salle d’attente), ou de sélectionner la
prochaine opération à lancer si plusieurs sont possibles. Une autre vision, inspirée de notre
projet, est de faire de l’agent un méta-décideur qui, à chaque étape de replanification, choisit
quel algorithme d’optimisation utiliser (Tabou, RS ou GA) et avec quels paramètres. Cette
approche fait de l’agent un superviseur des métaheuristiques : il apprend par exemple que
dans tel contexte (beaucoup de patients en attente, ressources saturées), l’algorithme
Tabou avec un certain réglage est le plus efficace, etc.
La récompense $r$ : il faut traduire nos objectifs en signal de récompense. Un choix naturel
est de définir $r$ comme la réduction du makespan ou du temps d’attente suite à l’action.
Par exemple, si l’agent décide de traiter un certain patient en premier et qu’ensuite le temps
d’attente moyen diminue, on donne une récompense positive proportionnelle à cette
amélioration. À l’inverse, toute violation de contrainte (comme un conflit de ressource ou le
dépassement d’un délai critique) peut être pénalisée via une récompense négative (malus).
L’enjeu est d’équilibrer correctement les récompenses pour orienter l’agent vers le
comportement désiré. Une autre possibilité est de ne donner une récompense significative
qu’à la fin d’un épisode (par ex. $r = -,$makespan final), ce qui est plus proche de
l’optimisation globale du planning mais rend l’apprentissage plus difficile (sparse reward).
Avec ces éléments, on plonge l’agent dans une simulation de l’environnement des
urgences : au fil du temps (discrétisé), l’agent observe l’état (patients et ressources) et prend
des décisions d’ordonnancement. Par exemple, l’agent peut apprendre une politique qui
décide quel patient passer en priorité en fonction de l’état (peut-être qu’il apprendra à
toujours traiter en premier les patients dont les opérations sont courtes pour fluidifier le
système, ou au contraire prioriser les cas graves). Au début, ses décisions seront aléatoires
et possiblement mauvaises, mais au fil des épisodes (simulations répétées), il va ajuster ses
$Q$ valeurs et s’améliorer. On peut s’inspirer d’applications du RL sur des problèmes
similaires, comme le fameux Vehicle Routing Problem (VRP). Par exemple, dans le cours de
référence
file-2napbpfrhbesjdjdh4eza2
, il est mentionné que l’apprentissage par renforcement a été utilisé pour apprendre dans
quel ordre appliquer des mouvements de recherche locale dans un VRP. Autrement dit,
l’agent RL apprenait une méta-stratégie de résolution : “dans telle situation du VRP,
appliquer d’abord le 2-opt puis un or-opt” etc. De façon analogue, pour nos urgences, un
agent RL pourrait apprendre à sélectionner dynamiquement l’heuristique appropriée en
fonction de la situation
file-2napbpfrhbesjdjdh4eza2
. Par exemple, s’il “voit” qu’il y a beaucoup de conflits de ressources à résoudre, il pourrait
choisir une étape Tabou ciblée sur les conflits; s’il voit que la planification est déjà assez
bonne, lancer un GA pour explorer de nouvelles solutions; s’il reste très peu de temps (état
proche de la fin), se contenter d’ajustements mineurs, etc. Un point important dans
l’implémentation est la gestion de l’exploration/exploitation. Au début, on fixe un $\epsilon$
assez élevé (par ex. $\epsilon=0.3$) pour que l’agent essaye divers ordonnancements.
Progressivement, on pourra réduire $\epsilon$ (par ex. $\epsilon \to 0.1$) pour qu’il stabilise
son comportement optimal connu tout en gardant un peu d’exploration aléatoire pour pallier
d’éventuels changements (par ex. un influx inhabituel de patients, ce qui modifierait la
dynamique habituelle). On peut aussi adapter d’autres paramètres d’apprentissage : le taux
$\alpha$ peut être diminué au cours du temps pour un apprentissage plus stable, et le
facteur $\gamma$ réglé en fonction de l’horizon de temps considéré (par ex. si on valorise
beaucoup la performance finale globale, on met $\gamma$ proche de 1 pour tenir compte
des récompenses futures lointaines). À ce stade, notre travail sur le RL a été
essentiellement conceptuel et inspiré par la littérature. Nous n’avons pas intégré un agent
RL opérationnel dans la simulation du fait de la complexité et du temps d’entraînement
requis. Néanmoins, l’intérêt potentiel d’une telle approche est clair : un agent RL pourrait
être entraîné sur des milliers de scénarios simulés d’urgences, et en dégager des stratégies
optimales d’ordonnancement adaptatives. Une fois entraîné, il pourrait être déployé en
temps réel pour assister les responsables des urgences dans la prise de décision (ou
automatiser une partie de la gestion). De plus, coupler RL et métaheuristiques ouvre la voie
à des approches hybrides où l’agent apprend à orchestrer différentes heuristiques selon le
contexte. C’est une perspective prometteuse que nous suggérons d’explorer davantage en
prolongement de ce projet.
Conclusion
Ce projet a permis d’explorer différentes approches d’optimisation pour améliorer
l’ordonnancement des patients dans un service d’urgences hospitalières. Dans un premier
temps, nous avons formalisé le problème et mis en évidence son importance : en optimisant
l’enchaînement des soins (réduction du makespan, suppression des temps morts et des
conflits de ressources), on peut espérer désengorger partiellement les urgences et améliorer
la qualité de prise en charge. La complexité du problème (NP-difficile, contraintes multiples,
environnement incertain) justifie l’usage de méthodes avancées. Trois algorithmes
métaheuristiques (Tabou, Recuit Simulé, Génétique) ont été implémentés et testés. Le
Tabou s’est distingué par sa rapidité de convergence et sa capacité à fournir rapidement un
très bon planning (makespan réduit, conflits éliminés). Le Recuit Simulé a confirmé sa
faculté à éviter les minima locaux et à s’adapter à des contraintes complexes, obtenant des
résultats comparables au Tabou avec un peu plus de temps de calcul. L’Algorithme
Génétique a offert une approche populationnelle intéressante, générant des solutions
variées et robustes, mais atteignant son plein potentiel sur des horizons plus longs (plus de
générations). Le tableau comparatif a synthétisé ces observations, soulignant que chaque
méthode a ses points forts : Tabou pour l’intensification rapide, Recuit pour l’exploration
efficace, Génétique pour la diversité et l’adaptabilité. Nos simulations ont montré des gains
significatifs d’ordonnancement par rapport à une planification naïve, avec par exemple une
réduction du temps total d’environ 15% dans un cas type (Tabou passant le makespan de
14 à 12). Ces améliorations se traduiraient concrètement par des patients traités plus
rapidement et des ressources moins inactives. Nous avons également discuté l’apport
potentiel d’un Système Multi-Agents qui combinerait plusieurs heuristiques ou agents
décisionnels. Bien que non implémenté entièrement, un SMA bien conçu pourrait
théoriquement surpasser chaque algorithme pris isolément, grâce à la coopération et à
l’adaptation entre agents. C’est une piste prometteuse pour les situations très dynamiques
(arrivées continues de patients, événements imprévus) où la décentralisation de la décision
et la réactivité des agents seraient précieuses. Enfin, nous avons exploré une approche par
Apprentissage par Renforcement (Q-Learning). Même si les travaux sont préliminaires,
l’idée d’entraîner un agent à apprendre la meilleure manière d’ordonnancer (ou d’arbitrer
entre différentes stratégies d’ordonnancement) ouvre des perspectives innovantes. Un tel
agent pourrait à terme ajuster en temps réel les décisions en fonction de l’état du service, et
continuer de s’améliorer avec l’expérience accumulée. Par exemple, un agent RL
supervisant le choix des algorithmes d’optimisation pourrait automatiser la sélection de la
meilleure méthode pour la situation courante, réalisant ainsi un système auto-adaptatif pour
la gestion des urgences. Limites : Il convient de noter que notre travail est une étape
exploratoire sur un cas simplifié. Certaines simplifications (durées fixes, nombre de patients
limité, pas de nouvelles arrivées en cours de planning, etc.) devraient être levées pour
appliquer ces approches en conditions réelles. De plus, les métaheuristiques fournissent des
solutions satisfaisantes mais pas nécessairement optimales ; dans un contexte critique
comme les urgences, il faut s’assurer que ces solutions respectent bien toutes les
contraintes médicales et de sécurité. L’implémentation d’un agent RL nécessiterait un
volume important de données de simulation et soulève la question de l’explicabilité des
décisions prises (important pour faire confiance à une IA en milieu médical). Perspectives
d’amélioration : À court terme, on pourrait envisager d’hybrider les approches – par exemple
utiliser la solution Tabou comme point de départ du Recuit Simulé ou du Génétique, ou
intégrer un petit Recuit à chaque mutation du GA – afin de combiner leurs forces.
L’extension du modèle pour prendre en compte la priorité des patients (gravité) serait
également cruciale : il faudrait alors adapter l’objectif (minimiser un temps d’attente pondéré
par la gravité plutôt que le seul makespan). D’un point de vue système, connecter le modèle
à des données réelles d’un service d’urgences permettrait de tester la pertinence des
solutions proposées et d’effectuer des ajustements en fonction des retours terrain. Enfin, le
développement d’un prototype d’agent RL mériterait d’être poursuivi : avec les bons états et
récompenses, il pourrait apprendre des règles de dispatching efficaces (par ex. toujours
utiliser telle ressource dès qu’elle est libre pour tel type de patient, etc.) difficilement visibles
à l’œil nu. En combinant optimisation et apprentissage, on peut espérer concevoir à terme
un système d’aide à la décision intelligent capable d’évoluer avec le service et d’optimiser en
continu l’ordonnancement des patients, contribuant ainsi à des urgences plus fluides et
efficientes. En conclusion, ce projet a mis en lumière l’intérêt des méthodes d’optimisation
avancées pour les urgences. Il a fourni des solutions d’ordonnancement améliorées et
ouvert la voie à de nouvelles stratégies (multi-agents, RL) pour aller encore plus loin. Bien
que de nombreux défis restent à relever pour une application en conditions réelles, les
résultats obtenus sont encourageants et suggèrent que ces approches pourraient, à terme,
devenir des composantes clés des systèmes de gestion hospitalière de nouvelle génération.