View
107
Download
1
Category
Preview:
Citation preview
Approches heuristique pour la programmation des mises au
point médicales en ambulatoire
Cordier Jean-PhilippeRiane Fouad
This paper is part of Research Program IAP 6/09 « Higher Education and Research »
of the Belgian Federal Authorities
Plan
• Contexte
• Description du système
• Les politiques d’allocation des heures d’arrivée
• Ré-optimisation des plannings
• Résultats
• Conclusion et perspectives
Stratégique
Tactique
Opérationnel
Rendement des mises au point
Qualité du service aux patients
Taux des patients ambulatoires
Organisation des services
Ordonnancement des rendez-vous
Système de prise de rendez-vous
Contexte de l’étude
• Contexte global de la gestion hospitalière• Un hôpital de taille moyenne• Un grand ensemble d’examens médicaux• Un besoin d’organisation des mises au point des
patients
Contexte de l’étude
• Le coût :
• La qualité :– Les engagements des patients– L’allocation des lits– Le temps d’attente pour la réalisation
d’une mise au point
Attractivité de l’hôpital
Description du système
Service
Service
GroupeGroupe
• Examen
• Examen
• Examen
• Examen
• Examen
• Examen
• Examen
GroupeGroupe
Calendrier
Calendrier
Calendrier
Calendrier
Prescription d’une mise
au point
Ambulatoire
Hospitalisation
?
Solution ProposéeService
Service
GroupeGroupe
• Examen
• Examen
• Examen
• Examen
• Examen
• Examen
• Examen
GroupeGroupe
Calendrier
Prescription d’une mise
au point
Ambulatoire
Hospitalisation
?
09:15
Allocation des heures d’arrivée
• Politique aléatoire équilibrée d’allocation
Allocation des heures d’arrivée
Patient i
Ei = {1,2,3,4,9}
Précédence(1,2); (1,3); (1,4); (1,9)(1,9); (2,9); (3,9); (4,9)(2,4) Séquences
[1,2,3,4,9]
[1,2,4,3,9]
[1,3,2,4,9]
RAND
LEFT
Allocation des heures d’arrivée
Patient i
Ei = {1,2,3,4,9}
Précédence(1,2); (1,3); (1,4); (1,9)(1,9); (2,9); (3,9); (4,9)(2,4) Séquences
[1,2,3,4,9]
[1,2,4,3,9]
[1,3,2,4,9]
RAND
LEFT
Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 11Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 11Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 10
Allocation des heures d’arrivée
Patient i
Ei = {1,2,3,4,9}
RAND
LEFTRIGHT
Séquences
[1,2,3,4,9]
[1,2,4,3,9]
[1,3,2,4,9]
Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9
Précédence(1,2); (1,3); (1,4); (1,9)(1,9); (2,9); (3,9); (4,9)(2,4)
Allocation des heures d’arrivée
Rand Mixte Left Right1. Selection d’une séquence s2. Test “Left Right” et un test “Right Left”3. Compare les deux sur le temps de séjour4. Selection le meilleur ou de manière alternative
en cas d’égalité
Le résultat de cette étape:• Le planning d’une journée• Chaque patient connait son heure d’arrivée
Etape suivante: un modèle gloable
Allocation des heures d’arrivée
Algorithme Glouton
• Politique goutonnes d’allocation des heures d’arrivée
Algorithme Glouton
Patient i
Ei = {1,2,3,4,9}
GREEDY
LEFT
Séquences
[1,2,3,4,9]
[1,2,4,3,9]
[1,3,2,4,9]
Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9
Précédence(1,2); (1,3); (1,4); (1,9)(1,9); (2,9); (3,9); (4,9)(2,4)
Algorithme Glouton
Patient i
Ei = {1,2,3,4,9}
GREEDY
LEFT
Séquences
[1,2,3,4,9]
[1,2,4,3,9]
[1,3,2,4,9]
Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9Ex Proc1 1 2 2 3 1 4 3 9 2
makespan = 9
Précédence(1,2); (1,3); (1,4); (1,9)(1,9); (2,9); (3,9); (4,9)(2,4)
Modèle : notations
i = 1, …, n indice des patientsj,k = 1, …, m indice des examenst = 1, …, T indice du temps
ri heure d’arrivée du patient i
Ci durée optimale du checkup du patient i
cht capacité du groupe h au temps t
Aijk un grand entier
pij temps de l’examen j
ρijk maximun entre le délai et letemps de trajet entre j et k
Dépend de la classe du patient i
CL
CR
Modèle : les ensembles
Ensemble des examens du patient iEi = {1, …, mi}
Ensemble des paires d’examens dont l’ordre est fixéEfi = {(j,k)}
Ensemble des paires d’examens dont l’ordre n’est pas fixéEdi = {(j,k),(k,j)}
Groupe h d’examensGh
Modèle : les variables
Un vecteur par couple patient-examen sur l’horizon de tempsxijt = 1 si le patient i commence l’examen j au temps t
Un couple de variables binaires par couple d’examens sans précédence imposéezijk = 1 si le pastient i passe l’examen j avant l’examen k
Les domaines de définition des variables
Modèle: les contraintes
Fin de journée et début de la journée patient
Contrainte de capacité
Modèle: les contraintes
Contrainte de précédence
Contraintes disjonctives
Algorithme Glouton
Algorithme Glouton
Modèle global : les variables
One variable by patient for his inconvenienceπi ≥ 1 inconvenience of patient i
One variable for the maximum of all inconvenienceπ ≥ 1 maximum of inconvenience of all patients
Domaines de définition de ces variables
Modèle global: Objectifs
Minimiser le désagrément moyen de tous les patient d’une même journée
Minimiser le désagrément maximum de tous les patients d’une même journée
Modéle
Etude de cas
• Basé sur le cas d’un hôpital partenaire• 30 examens sélectionnés• 12 groupes d’examens• 4 classes de patients
• 150 patients testés par journée
Generation Old New
Mobility Good 1 2Limited 3 4
Résultats
Expérimentation
A désagrément équivalent
Conclusion et perspectives
Développements futures
– Résoudre les problème de temps de calcul
• Metaheuristiques: algorithme génétique, ...
• Heuristiques: adapter notre modèle global
– Modèle de simulation pour tester nos solutions
– Intégrer le post traitement aux modèles
Merci
Des questions?
Contexte global
• Hospital is a service maker– The patient is an actor of the care production
– The cares are not simply for the health (physical, psychological and social)
• The evolution of the Health care environment:– Increase of activity (ageing population, the increase of
pathology)
– The care and the patient pathway complexity
– The lack of human and financial resources
– The raise of quality requirement (control by the stakeholders and the patient demand
Résultats
Expérimentation 1
Anova
Résultats
Optimisation globale du planning
Désagrément moyen Désagrément maximum
Recommended