Bonjour à tous,
Je travaille à la conception d'un logiciel pour résoudre une répartition de place de stage selon des voeux et je voulais savoir s'il y avait une approche logique déjà connu pour résoudre ces problèmes.
Voici les conditions :
1/ Un étudiant doit faire un stage dans une des 4 spécialités S1 S2 S3 S4
2/ Un étudiant peut choisir entre 4 hôpitaux H1 H2 H3 H4
3/ Un étudiant peut choisir entre 4 période de stages P1 P2 P3 P4
4/ Un étudiant peut exprimer plusieurs choix dont certains "concurrent"/cumulatif par ex. mon 1er choix en spécialité S1 est : pour l’hôpital H1 en P1+P2 et à l’hôpital H3 en P3 (on peut imaginer ajouter un classement entre ces choix cumulatif simultané)
5/ Le but est de maximiser le nombre d'étudiant avec leur 1er choix, les places étant limités dans chacun des hôpitaux
J'ai déjà discuté cette question dans le forum algorithmique et nous sommes arrivé à :
1/ Je réalise un tirage pour chaque possibilité où il y a plus d'étudiants que de places
2/ Si un étudiant est tiré au sort dans plusieurs stages je le réaffecte dans le stage qui est le moins demandé pour augmenter le taux de satisfaction
3/ Je continue jusqu'à ce qu'il n'y ait plus de réattribution
4/ Les étudiants qui n'ont pas leur 1er choix sont tirés au sort à part pour leur 2ème choix puis nième choix jusqu'à ce qu'il est une attribution d'un 1er lieu de stage (ils n’ont pas eu leur 1er choix ont les favorises pour leur 2ème choix)
5/ Je passe au 2ème choix de tout le monde (excepté ceux distribué au point 4/ => on prend le 1er choix non satisfait de ceux-là) et ainsi de suite
De plus, si un étudiant choisit toutes une période pour une spécialité (ex. pour S1 : H1P3+H2P3+H3P3+H4P3) on estime que cette période est importante pour lui => on ne le réaffecte pas s'il est tiré au sort dans cette période.
Idem pour les hôpitaux si il choisit tout un hôpital pour une spécialité (ex. pour S1 : H1P1 + H1P2 + H1P3+H1P4).
Un éclairage plus "logicien" est le bienvenu si cela vous inspire
Bonne fin de journée !
Manu
-----