Discussion :

[Eric Pasquier]

Bonjour,

Il y a plusieurs années, on m´a soumis un problème. Il s´agit d´un probème d´allocation de ressources. Je n´ai jamais su comment le résoudre d´une façon élégante.
Vu le bon niveau que je viens de lire ici, je me permet de le soumettre à vos suggestions.

Dans un hôpital, 3 équipes d´infirmières se relaient:
- une équipe du matin, 3 personnes, 8 heures d´affilées, à partir de 06h00;
- une équipe de l´après midi, 3 personnes, 8 heures d´affilées, à partir de 13h00;
- une équipe de nuit, 2 personnes, 11 heures d´affilées, à partir de 20h00;
- chaque équipe est en recouvrement 1 heure pour le passage des informations des malades;
- il n´est pas possible de faire plus de 2 nuits de suite;
- il est nécessaire d´un délai légal minimum de 12h00 entre les nuits et les matins.

Jusqu´ici, j´ai fait un moteur qui prend d´un coté les "besoins" (horaires à remplir) et qui regarde les ressources une par une en testant les règles.
Ca fait un peu moche de tester toutes les solutions pour en trouver une.

Comment peut-on résoudre ce type de problème ?
J´ai commencé à voir des algo sur les graphes, mais je nage un peu sur le type d´algorithme à utiliser.

Je connais plusieurs autres problèmes similaires :
- gestions de plus de 1200 conseillers de clientèle (réponse téléphonique, télémarketing, recouvrement de facture)
- gestions des plannings scolaires des professeurs et des classes de cours
- gestions des avions d´une compagnie aérienne (à mon avis un peu plus compliqué vu que les avions ne reviennent pas forcément à leur point de départ)
- etc ...

J´espère vous avoir intéressé.
Eric.

P.S.: je ne cherche pas un produit commercial. C´est juste pour le plaisir.

[RDM]

C'est typiquement le genre de problème réglés par les techniques de programmation par contraintes (en angalis Constraint Solving Problems ou Constraint Solving Programs).

petite introduction:
http://www.laas.fr/~lopez/publis/Contraintes-GRP.pdf

bon point de départ pour approfondir

[Sarbacane]

Salut,
Intuitivement, ce probleme m'evoque l'algorithme du Banquier de Dijkstra. Bien que differants les deux problemes ont pour point commun: La necessite d'avoir un etat sable du systeme apres l'allocation des ressources. En effet dans notre cas, il s'agit de garantir la possibilite de creer les deux prochaines equipes chaque fois qu'une nouvelle est creee. Ceci impose:
1.) La determination du nombre minimun de personnel requis,
2.) La creation d'algorithme(s) "Proactifs" capables de nous renseigner sur la stabilite du system apres chaque modification.

Tantative de resolution du point 2.)

Soit P l'ens du personel de guarde et N le nombre de ce personel. Soit E l'ens des equipes. Alors a chaque Ei on peut associer un Hi tel que Hi soit l'horaire de l'equipe Ei, Chaque Hi etant de la un intervalle de TimeStamp( Date + Heure(debut,fin)). On peut creer un vecteur D(Disponibilite) de N elts telque chaque Di represente l'instant a partir duquel l'infirmier(e) i es disponible. Chaque Di tenant compte d'eventuele delai legal minimum entre 2 tours de guarde. Nous avons besoin d'une variable Boolean ES ( Etat Stable ) et de 2 fonctions:
i) TGroup Creer_Group(const int NumGroup)
ii) Bool EtatStable(TGroup Ungroup,const int NumGroup).
ou TGroup est un Vecteur de 3 elts contenant l'identite des infirmier(e)s diponibles pour la creation d'un groupe G.(G est donc de Type TGroup). Nous pouvons alors ecrire:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
TGroup Creer_Group(const int NumGroup){
/*
 * TGroup Creer_Group(const int NumGroup)
 * Tante de creer une equipe de 2 ou 3 personnes pour un tour de Garde
 * Teste si la creation de ce group est oportun.
 * SIOUI
 *   Calcule l'Horaire du groupe (Hi = Date + laps de temps de travail )
 *   Ajoute a E le nouveau group et son Horaire
 *   change le Satus de D en fonction de Hi et des delais requis
 * SINON
 *   Laisse le system ds son etat actuel
 *
 * PARAMETRES
 *  Entree:
 *    NumGroup ={1=> (6H-14H,debut=6H); 2=>(13-21H,..); 3=>(20H-7H,...)} permet de deduire les variable debut et Hi
 *
 *  Sortie:
 *    CurrentGroupe Vecteur de 3 elts contenant l'id de 2 ou 3 personnes d'une equipe de garde.
 *      CurrentGroupe =(-1,-1,-1) ==> personne n'est disponible
 *      CurrentGroupe =(x,y,z) ==> une equipe de 3 personnes
 *      CurrentGroupe =(x,y,-1)==> une equipe de 2 personnes
 *    toute autre valeure serait consideree inconcistante donc equivalente a (-1,-1,-1)
*/
  TGroup CurrentGroupe =(-1,-1,-1);
  Bool ES = false;
  SI ( NumGroup < 2 ou NumGroup > 3 ) Alors Rien A faire ==> FIN
    //Equipe de 6H Ou de 13H
  SI NumGroup = ( 1 ou 2){
      Choisir dans D ts le personel dont la disponibilite correspond a debut// (soit k le nbr de ces disponibles)
      Si (k < 3 ) Impossible ==> FIN
      Creer un ens Gi des Arrangement de 3 dans k //soit n lenombre de ces Arrangements
        //Essayer au besoins ts les Gi
      Pour i allant de 0 a n-1{
         CurrentGroupe = Gi;//pour m allant de 0 a 2 CurrentGroupe[k]= Gi[m]
      ES = EtatStable(CurrentGroupe,D,(NumGroup+1)%3);
	  //stabilite garantie
      SI (ES){
	  Ajouter a E le Couple (CurrentGroupe,H);//H se deduit de la date et de NumGroup
	  Modifier(D,CurrentGroupe);//en tenant compte d'eventuele delai legal minimum
       }
       SINON{//stabilite non garantie pas de modif
	Inpossible ==> FIN
       }
      }//fin du parcourt des Gi
  }
    //NumGroup = 3<==> Equipe de 20H
  SI_NON{
     Choisir dans D ts le personel dont la disponibilite correspond a debut// (soit k le nbr de ces disponibes)
     Si (k < 2 ) Impossible ==> FIN
     Creer un ens Gi des Arrangement de 2 dans k //soit n lenombre de ces Arrangements
        //Essayer au besoins ts les Gi
     Pour i allant de 0 a n-1{
       CurrentGroupe = Gi;//pour m allant de 0 a 1 CurrentGroupe[k]= Gi[m]
       ES = EtatStable(CurrentGroupe,D,(NumGroup+1)%3);
       SI (ES){
         Ajouter a E le Couple (CurrentGroupe,H);//H se deduit de la date et de NumGroup
         Modifier(D,CurrentGroupe);//en tenant compte d'eventuele delai legal minimum
       }
       SINON{//stabilite non garantie pas de modif
         Inpossible ==> FIN
       }
     }//fin du parcourt des Gi
  }
  Retourner(CurrentGroupe);
}

EtatStable(..) verifie si la creation des 2 prochaines equipes de guarde est possble.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
Bool EtatStable(TGroup Ungroup,unEtat,const int NumGroup){
  TGroup CurrentGroupe =(-1,-1,-1);
  TEtat  CurrentEtat= unEtat;
  Bool ES = false;
  int i,prochaineGarde;
  CurrentEtat:=Modifier(CurrentEtat,Ungroup);//en tenant compte d'eventuele delai legal minimum
  SI NumGroup = 0{//Garde 3==>(20H-7H)
    Choisir dans CurrentEtat ts le personel dont la disponibilite correspond a debut// (soit k le nbr de ces disponibes)
    Si (k < 2 ) Retourne(false)//FIN
    Creer un ens Gi des Arrangement de 2 dans k //soit n lenombre de ces Arrangements
	//Essayer au besoins ts les Gi
    Pour i allant de 0 a n-1{
      CurrentGroupe = Gi;//pour m allant de 0 a 1 CurrentGroupe[k]= Gi[m]
      prochaineGarde = (NumGroup+1)%3;
      ES = EtatStable(CurrentGroupe,CurrentEtat,prochaineGarde)
      SI (ES){
        Retourne(ES);
      }
    }//i allant de 0 a n-1
  }
  SI NumGroup = 1ou 2{//Garde 1/2 <==>(6H-14H/(13H-21H))
    Choisir dans CurrentEtat ts le personel dont la disponibilite correspond a debut// (soit k le nbr de ces disponibes)
    Si (k < 3 ) Retourne(false);//FIN
    Creer un ens Gi des Arrangement de 3 dans k //soit n lenombre de ces Arrangements
	//Essayer au besoins ts les Gi
    Pour i allant de 0 a n-1{
      CurrentGroupe = Gi;//pour m allant de 0 a 1 CurrentGroupe[k]= Gi[m]
      prochaineGarde = (NumGroup+1)%3;
      ES = EtatStable(CurrentGroupe,CurrentEtat,prochaineGarde)
      SI (ES){
        Retourne(ES);
      }
    }//i allant de 0 a n-1
  }
}

Bon voila c'est un peu brouillon tout cela (40 minutes d'edition en ligne ca fatigue:-) ) mais je tennais a commencer par crainte de ne plus n'interesser au sujet. Je le rediterais des que j'aurais un peu de temps ou qu'il y aura de lacunes a combler.

Dites moi s'il (l'algo) a de graves manquements ...
Je le trouve pas conscis avec des structures de donnees un peu trop lourdes mais ce n'est qu'un debut peut etre qu'il s'ammeliorea avec le temps !

Cia!

[Eric Pasquier]

RDM, j´ai bien regardé le document.
Je ne connaissais pas le nom de cette technique, mais c´est finalement exactement ce que j´ai fait dans mon moteur actuel.
Il reste néanmoins un problème, savoir si une solution choisie aujourd´hui ne va pas entrainer un blocage demain, alors qu´une autre aurait peut être fonctionnée ...

Je n´ai pas encore analysé le msg de "Sarbacanne", mais j´étais pratiquement sûr qu´une technique de parcours de graphe était une bonne solution.

Je vais encore chercher.

[RDM]

La prog par contraintes (PPC) est faites pour trouver une solution selon les contraintes que tu as. Le problème doit être statique. ca ne s'applique pas aux classes de problèmes dynamique !
Si les données changes, il faut recalculer la solution.
tu peux avoir plusieurs solutions et essayé de trouver celle optimale en rajoutant des contraintes d'optimisation (minimalisation/maximisation de cout)