View
114
Download
0
Category
Preview:
Citation preview
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
),,()(
Recommended