Discussion :

[larnicebafteur]

Bonjour,

je suis à la recherche d'algorithme ou de noms de méthodes pour organiser le complexe problème de l'organisation d'une réunion parents/professeurs.

En quelques mots, voici le problème et les nombreuses contraintes :
- chaque parent donne une plage horaire qui est à respecter
- chaque parent indique quels enseignants il souhaite rencontrer, avec différentes priorités
- les enseignants indiquent aussi des priorités pour les parents qu'ils souhaitent rencontrer
- le planning des parents doit être le plus compact possible

A partir de toutes ces contraintes, à respecter au mieux, le but est de planifier l'ensemble des rencontres.

Plusieurs logiciels effectuent déjà ce genre de problème, et j'aimerais bien étudier ce problème d'un peu plus près.
J'ai essayé de trouver des noms de méthodes pour résoudre ce problème, mais en général je tombe sur des discussions où les réponses sont très vagues, jamais rien de concret. On tombe parfois sur des articles très théoriques, des thèses, ... mais jamais rien de très pratique, cela reste très général et flou.

Quelqu'un a des idées précises sur les méthodes à utiliser ?

Dans le domaine éducatif, il y a aussi le problème tout aussi complexe de la réalisation des emplois du temps dans un établissement scolaire, qui sont réalisés par des logiciels spécialisés.
Je ne sais pas si ce sont les mêmes méthodes qui y sont utilisées aussi ou pas, mais j'ai l'impression que c'est un peu le même genre de problème.

Merci d'avance.

[Galet]

Bonjour Larcnicebafteur,
Le sujet est ardu. Celui de l'élaboration des plannings a déjà été abordé sur le forum.

Tu trouveras surement ton bonheur du côté des parcours de graphes.
Je vais regarder dans mes archives pour tenter de te trouver les articles les plus clairs à ce sujet parmis une literrature abondante...
Bien l'bonjour,

[dourouc05]

J'ai essayé de trouver des noms de méthodes pour résoudre ce problème, mais en général je tombe sur des discussions où les réponses sont très vagues, jamais rien de concret. On tombe parfois sur des articles très théoriques, des thèses, ... mais jamais rien de très pratique, cela reste très général et flou.

Probablement as-tu vu les mots clés "MIP", "LP", "MILP" (ou les versions en français : PNE, PL, PLNE), "programmation mathématique", "programmation par contraintes" ? Tu ressors en général avec un modèle mathématique, tu utilises après un logiciel spécifique pour trouver la solution optimale. (Les méthodes utilisées sont souvent : simplexe, séparation et évaluation - branch-and-bound -, propagation de contraintes.)

[larnicebafteur]

Bonjour,

j'ai en effet trouvé les noms de beaucoup de méthodes, des articles sur ce genre de problèmes, des thèses, ...
J'ai pourtant un bon niveau en mathématique et en programmation, mais je trouve que cela reste toujours très théorique, donc très vague.

J'aurais aimé une approche plus concrète, avec des pistes pour attaquer ce type de problème.

Rien que la modélisation du problème n'est pas évidente, au niveau des vœux et des contraintes, comment les formuler et les modéliser d'un point de vue des données dans un programme informatique ?

Ensuite, l'ensemble des vœux n'étant pas possible à respecter, que certaines contraintes sont à respecter impérativement, et d'autres contraintes étant à respecter "au mieux", dans quelle direction aller ?

Après un peu de réflexion, je suppose qu'il faut initialiser le planning des rencontres avec certains des vœux, mais lesquels et en quelle quantité ?
Puis, je pense qu'il faut ajouter les rendez-vous un par un, mais comment s'y prendre "au mieux" ?
Et une fois qu'on a placé un maximum de rendez-vous, il faut probablement optimiser l'ensemble, en tentant des permutations sans doute, mais comment pour que cela soit efficace ?

Et la qualité des placements de ces rendez-vous doit se faire en minimisant une ou plusieurs fonctions objectifs, mais que prendre pour celles-ci ?

Bref, autant de questions très concrètes pour lesquelles je ne trouve aucune réponse. Plusieurs logiciels réalisent ce type de problème, donc les réponses à ces questions existent, j'aurais aimé en trouve quelques unes, afin de ne pas tout réinventer, de partir dans les bonnes directions, d'éviter les méthodes qui ne sont pas efficaces.
C'est la partie modélisation, choix de la fonction-objectif, et les principes à utiliser qui me manquent, et ceux ayant déjà travaillé sur ce problème ont forcément des pistes.
En ce qui concerne les dizaines de méthodes théoriques de résolution de problème complexes, non-linéaires, et tout ce qu'on veut, j'ai beaucoup de noms, mais lesquelles sont vraiment efficaces et effectivement utilisées pour mon problème ?

[tbc92]

Tu parles d'une fonction objectif à minimiser ou maximiser, cette fonction, c'est toi qui la définis.

Voici une fonction qu'on va chercher à maximiser
- chaque parent donne une plage horaire qui est à respecter : Pour chaque parent, si l'ensemble des rendez-vous tient dans cette plage horaire, rien à signaler, sinon X points de malus (X à ta convenance, selon l'importance que tu donnes à ce critère).
- chaque parent indique quels enseignants il souhaite rencontrer, avec différentes priorités : Y points positifs pour chaque rendez-vous effectivement proposé, avec Y variable selon la priorité. Si un rendez-vous avec un prof prioritaire n'est pas dans la plage horaire demandée, malus, par contre, pas de malus si c'est un rendez-vous avec un prof non prioritaire.
etc etc.

Quand tu as défini cette fonction, un outil permet d'explorer toutes les combinaisons, et de garder celles qui donnent le résultat optimal.
Un outil développé basiquement utiliserait la force brute, en explorant systématiquement toutes les combinaisons. Mais ça peut être très long.
Les outils du marché vont optimiser ça, par je ne sais quels moyens.

[larnicebafteur]

En effet, c'est bien à moi de définir une fonction objectif, et j'ai déjà quelques idées sur ce qu'il faut qu'elle contienne.

La recherche exhaustive de toutes les solutions n'est pas envisageable pour ce genre de problème. Le nombre de variables et de contraintes est bien trop important, il faudrait un temps de plusieurs fois l'âge de l'univers pour tout explorer.

En venant ici exposer ce problème, c'était dans l'espoir que quelqu'un connaisse ce problème d'assez près, pour me donner des pistes qui fonctionnent.
Il existe plusieurs manières de stocker les données, plusieurs choix de fonctions-objectif, plusieurs méthodes d'initialisation de la recherche, plusieurs méthodes de recherche d'une solution acceptable, plusieurs méthodes d'optimisation d'une solution pour en trouver une meilleure, ...
Et parmi toutes ces méthodes, il y en a très probablement certaines qui ne fournissent pas de bonnes solutions, et d'autres qui sont plus adaptées.
Ainsi, une personne s'étant déjà penché de près sur ce problème aurait pu m'orienter vers quelques chose qui marche effectivement.

J'ai trouvé des dizaines et des dizaines de discussions là-dessus, mais c'est toujours très vague, plein de gens viennent juste donner leur avis ou répètent ce qu'ils ont trouvé en 5 min de recherche sur Google, et on passe des heures à lire des échanges qui ne mènent à rien.

[tbc92]

Tu demandais "...en minimisant une ou plusieurs fonctions objectifs, mais que prendre pour celles-ci" , ne reproche pas aux gens de répondre à cette question.

Un temps de traitement proche de l'âge de l'univers ... n'exagérons pas. Disons plusieurs heures.

Il y a un problème assez similaire, c'est celui de parcours-Sup. Je n'ai pas trop le temps de rechercher, mais je me souviens d'une vidéo qui expliquait assez bien l'algorithme. Les volumes de données à traiter sont beaucoup plus importants que ce qu'on peut avoir pour une réunion parents-profs, mais tu as des contraintes en plus.