Ordonnancement d’un bloc Ordonnancement d’un bloc opératoire :opératoire :

résolution par la résolution par la programmation par programmation par

contraintescontraintes

A. Hanset, N. Meskens, O. Roux,Louvain School of Management & FUCAM, Mons, Belgique

GISEH 2010, septembre

22

Premier étage

Programme opératoire réalisable sur une journéeProgramme opératoire réalisable sur une journée

Second étage

Problème de planification du bloc

opératoire

Problème d’ordonnancement

journalier

Assigner un ensemble

d’interventions à chaque jour de la

semaineDéterminer l’ordre

final des opérations, par jour et par salle

d’opérations

DDescription escription généralegénérale - - MéthodologieMéthodologie

Un ensemble d’interventions non programméesUn ensemble d’interventions non programmées

3

Planification et ordonnancement d’opérations

RRevue de la littératureevue de la littérature

La majorité des articles prennent en compte la disponibilité des chirurgiens

Mais peu d’articles prennent en compte

• des ressources renouvelables ou non qu’elles soient

matérielles ou humaines

• les priorités des opérations

• les préférences des chirurgiens

• les affinités entre membre d’une équipe chirurgicale

• expérimentation sur des cas réels

Dexter et al. (2002) Pham et al. (2008) Beliën et al. (2007)

Fei et al. (2007, 2008, 2009) Jebali et al. (2006) Cardoen et al. (2008, 2010)

Guinet et Chaabane (2003) Augusto et al. (2007) Santibanez et al. (2007)

Chaabane et al. (2007, 2008) Denton et al. (2007) Marcon et Dexter (2007)

Kharraja et al. (2005) Hans et al. (2008) Van Oostrum et al. (2008)

Testi et al. (2007, 2009) Roland et al. (2006, 2007, 2010) Hammami et al. (2007)

…

4

NNotre problématiqueotre problématiqueOrdonnancement

Ressources humaines

(chirurgiens, infirmières,

anesthésistes)

Préférences, affinités,

disponibilités

Ressources matérielles

Renouvelables ou non,

disponibilités

Modularité

En vue de s’adapter aux

particularités des hôpitaux

Préférences

Opérations

Salles

Anesthésistes Matériel

b

e

Chirurgiens

InfirmièresCoeur

Affini

tés

Dé

dié

es

Block Scheduling

m

5

TType de programmationype de programmation

Block scheduling

Planning où des plages horaires (blocs) ont été

définies pour certain(e)s spécialités ou chirurgiens

rencontré majoritairement dans les hôpitaux visités

13 h 00

12 h 00

17 h 00

16 h 00

15 h 00

14 h 00

9 h 00

10 h 00

11 h 00

.. h ...

Salle d’Op. 1 Salle d’Op. 2

Durée d’ouverture pour deux salles d’opérations

But: Trouver un ordonnancement réalisable en tenant compte des contraintes humaines et matérielles

6

• On suppose les temps opératoires connus

• Chaque patient, en attente d’opération, est assigné un chirurgien à l’avance

• Les ressources matérielles et humaines ne sont pas toujours disponibles

• Les urgences ne sont pas prises en compte

• Quand une opération est commencée, elle ne peut être interrompue (aucune préemption)

HypothèsesHypothèses::

DDescription généraleescription générale

7

PPCPPC

La programmation par contraintes

Problèmes d’optimisation combinatoire

Particulièrement dédié au problème d’ordonnancement

Nombre de variables important

Nombre de contraintes important

Profite du morcellement de l’espace de recherche

Rapide pour trouver une solution réalisable

Ordonnancement d’un bloc opératoire hautement contraint

88

PPCPPC

OTR(o,t,r)

t

r

o

0 0 0 0 1 1 1 0 0 0 0

t

d(o)

Modélisation des opérationsUne opération de durée d(o)La matrice binaire OTR(o,t,r)

0 0 1 1 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1

1 1 0 0 0 0 0 0 0 0 0

t

o

99

PPCPPCModélisation des contraintes

Une opération doit se dérouler surd(o) intervalles de temps consécutifs

0 0 1 1 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0 0

0 0 0 1 1 1

0 0 1 1 1

0 1 1 1

1 1 1

Exemple : opération de durée d(o)=3

T

t

R

r

odrtoOTR11

)(),,(

Oo ..1

1)(

),,(1)(

1

1)(

1

od

rioOTRodj

jiR

r

odT

j

Oo ..1

0 0 0 0 0 0 1 0 0 0 0

t

r

0=

0=

0=1=

0 0 0 1 1 1 1 0 0 0 0

1010

PPCPPC

t

r

o

Modélisation des contraintes

Deux opérations ne peuvent passe superposer dans une salle

0 0 1 1 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1

1 1 0 0 0 0 0 0 0 0 0

TtRr ..1,..1

O

o

rtoOTR1

1),,(

=1 =1 =0=1=1

11

11

1111

11

111

11

1111

11

111

11

PPCPPC

t

r

o

Modélisation des contraintes

Deux opérations d’un mêmechirurgien ne peuvent passe superposer dans le temps

1 1 1

1 1 1

ss or

rtoOTR 1),,(

TtSs ..1,..1

=1 =1 =1=1 =0

1212

PPCPPC

t

r

o

Modélisation des contraintes

Contraintes relatives au débutde l’opération (au plus tôt et au plus tard)

0 0 1 1 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1

1 1 0 0 0 0 0 0 0 0 0

)(

)(

21)().(

),,(.

)( oLSod

ododrtoOTRt

oEStr

ES(o) LS(o)

o

1313

PPCPPC

t

r

o

Modélisation des contraintes

Contraintes relatives à des ensembles d’opérations1 1

1 1 1

1 1

11

11

111

11

11

111

mb oo 21 ,

em oo 21 ,

Ensemble d’opérations au début

Ensemble d’opérations en fin

)(

2

1)().(),,(.

)(

2

1)().(),,(.

2

22

12

1

1

11

11

1

od

ododrtoOTRt

od

ododrtoOTRt

T

t

R

r

T

t

R

r

1414

STR(s,t,r)

t

r

s

La matrice binaire STR(s,t,r)

),,( rtsSTR so

rtoOTR ),,(

RrTtSs ..1,..1,..1

PPCPPCLien entre STR(s,t,r) et OTR(o,t,r)

Exprime que le chirurgien s opère à certains moments dans les salles .

1515

PPCPPCModélisation des contraintes

Disponibilités des chirurgiens

),,(),,( rtsMrtoOTR S

o s

),,( 1 rtsM S

RrTtSs ..1,..1,..1

0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 0 0 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 0 0 1 1 1 1 0

0 0 0 0 0 0 0 0 0 0 0

t

r

Un chirurgien (dans plusieurs salles)

1616

PPCPPCModélisation des contraintes

Disponibilités des infirmières

),(),,( tsMrtnNTR N

o

),( 1 tnM N

RrTtNn ..1,..1,..1

1 1 1 1 0 0 1 1 1 1 0

t

Une infirmière

Disponibilités des anesthésistes

),(),,( taMrtaATR A

o

),( 1 taM N

RrTtAa ..1,..1,..1

1 1 1 1 0 0 1 1 1 1 0

t

Un anesthésiste

1717

La matrice d’affinité APP(p1,p2)

Chir.

1

Chir.

2

… Chir.

N

Anes

t. 1

Anes

t. 2

… Anes

t. N

Inf.

1

Inf.

2

… Inf.

N

Chir. 1 9 8 0 9 7 8Chir. 2 7 7 6 7 7 7…Chir. N 5 6 8 0 9 9Anest. 1 1 1 1 8 8 8Anest. 2 2 1 2 7 8 8…Anest. N 1 0 0 7 7 0Inf. 1 3 4 4 8 8 8 5 8Inf. 2 5 5 3 3 8 9 8 7…Inf. N 4 6 6 9 8 9 8 3

Chir.

1

Chir.

2

… Chir.

N

Anes

t. 1

Anes

t. 2

… Anes

t. N

Inf.

1

Inf.

2

… Inf.

NChir. 1 1 1 0 1 1 1Chir. 2 1 1 1 1 1 1…Chir. N 0 1 1 0 1 1Anest. 1 0 0 0 1 1 1Anest. 2 0 0 0 1 1 1…Anest. N 0 0 0 1 1 0Inf. 1 0 0 0 1 1 1 0 1Inf. 2 0 0 0 0 1 1 1 1…Inf. N 0 1 1 1 1 1 1 0

1. Ordonnancer au plus tôt

2. Minimisation du Makespan

C’est-à-dire la minimisation de l’heure de fermeture du bloc opératoire

3. Minimiser les heures supplémentaires

4. Maximiser les affinités 1818

MultiObjectifsMultiObjectifs

1919

• Programmation en java avec une bibliothèque dédiée (CHOCO)

• Jeux de données réelles

ImplémentationImplémentation

2020

RRésultats expérimentauxésultats expérimentauxExemple de résultat

5 interventions, 3 chirurgiens, 2 salles d’opérations, 3 infirmières, 3 lits de réveil

Tableau 20 : Variantes des jeux de données

Config/module Operations Block scheduling

Chirurgien Priorités Matériel/Infirmières/Anesth.

Affinités

CONF1 X X

CONF2 X X X

CONF3 X X X

CONF4 X X X

CONF5 X X X

CONF6 X X X X X X

CONF1 CONF2 CONF3 CONF4 CONF5 CONF6  

Ordo. au plus tôt Tps (sec.) 454,067 188,411 312,177 131,353 935,379 15,236[Int. Tps pondéré] Optimum 335 419 534 446 375 419

Makespan Tps (sec.) 21,592 1,316 2,721 161,209 20,546 14,863[Int. Tps] optimum 7 10 9 7 9 10H. Supplémentaire Tps (sec.) 25,046 2,812 2,843 6,970 3,710 10,773[Int. Tps] optimum 1 8 3 2 3 4

Affinités Tps (sec.)206,239 28,379 44,197 45,457 60 407,201

optimum 1146 1448 1404 1430 1384

21

CConclusions & perspectivesonclusions & perspectivesConclusions

• Obtention d’un ordonnancement réalisable en tenant compte de contraintes humaines et matérielles

• Modèle modulaire implémenté en CHOCO permet l’intégration d’un maximum de contraintes intègre les contraintes communes aux problèmes étudiés rendu possible grâce à la programmation par contraintes validé sur des données réelles

• Le modèle est alimenté par notre base de données capable d’accueillir les éléments du système d’information de l’hôpital cible

• Les mesures de performance classiques (makespan, charge, …) sont disponibles au travers des matrices vues comme des diagrammes de Gantt

22

CConclusions & perspectivesonclusions & perspectives

Perspectives• Recueil de données réelles sur le

matériel• Comparer avec un modèle

mathématique classique

2323

Préférences

Opérations

Salles

Anesthésistes Matériel

b

e

Chirurgiens

InfirmièresCoeur

Affini

tés

Dé

dié

es

Block Scheduling

m

2424

Merci de votre attention

RRésultats expérimentauxésultats expérimentaux

2626

PPCPPCProgrammation par contraintes

• L’idée est d’utiliser les contraintes du problème de façon active pour réduire la taille de l’espace de recherche.

Essais Solution réalisable

2727

Programmation par contraintes• Appelé propagation de contraintes

Recherche en profondeur d’abord+ « Backtracking »

PPCPPC

2828

PPCPPCModélisation des contraintes

Ressource non-renouvelable Quantité

Plateaux stériles disponibles (Type 1) 1M

Plateaux stériles disponibles (Type 2) 2M

Produits anesthésiant (Type 1) 3M

Produits anesthésiant (Type 2) 4M

Produits anesthésiant (Type 3) 5M

Quantité de ressource renouvelable }16...1{t }32...17{t }48...33{t

Infirmière (Type 1) tM1

tM1 tM1

Infirmière (Type 2) tM 2

tM 2 tM 2

Infirmière (Type 3) tM 3

tM 3 tM 3

Anesthésiste (Type 1) tM 4

tM 4 tM 4

Anesthésiste (Type 2) tM 5

tM 5 tM 5

2929

PPCPPCModélisation des contraintes

Mobilisation des ressources non-renouvelables

k

k

R

r

O

o t

ok MrtoOTRod

m

1 1

),,()(

kTt ,..1

Mobilisation des ressources renouvelables

kt

TodtMin

t

R

r

O

o

ok MroOTRod

m

),1)((

1 1

),,()(