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.

[larnicebafteur]

Je ne reproche rien à personne, mais j'aimerais que les réponses viennent de personnes s'étant vraiment frotté à ce problème.
Car moi aussi, des idées, j'en ai plusieurs et on en trouve énormément en cherchant, mais pour savoir lesquelles sont efficaces, les personnes ayant déjà programmé ce problème sont les mieux informées.
Les forums sont pollués de messages inutiles, de personnes venant simplement donner leur opinion, ou qui renvoient vers d'autres sites en ayant juste tapé une recherche sur Google en à peine 30 secondes (comme si celui qui posait la question n'avait pas essayé avant), ou qui encore mieux remettent en cause le fait de poser une telle question ...

Pour l'âge de l'univers, je n’exagère pas.
Mon problème fait partie de la catégorie "NP-complet" en terme de complexité.
Dans la même catégorie, on y trouve le "simple" problème du voyageur de commerce. Avec à peine une vingtaine de villes, il faut plusieurs siècles pour explorer toutes les combinaisons. Et avec 100 villes, des milliards de milliards de milliards .... de fois l'âge de l'univers.
Dans mon problème, on trouve des centaines de parents, à associer avec quelques dizaines de profs, dans quelques dizaines de créneaux horaires, soit un nombre de combinaisons absolument colossal.
C'est pour cela que je cherche les bonnes méthodes de résolution qui permettent de trouver une "bonne" solution.

Bref, je vais en rester là pour mes explications, je pense avoir été clair.
Si quelqu'un a des idées concrètes et qui fonctionnent vraiment à proposer, tant mieux. Sinon tant pis.

[Galet]

Je ne reproche rien à personne, mais j'aimerais que les réponses viennent de personnes s'étant vraiment frotté à ce problème.
...

Bref, je vais en rester là pour mes explications, je pense avoir été clair.
Si quelqu'un a des idées concrètes et qui fonctionnent vraiment à proposer, tant mieux. Sinon tant pis.

Bonjour,
Loin de moi l'envie (et le temps) de polémiquer, ni de "poluer" ta requète.
Si tu cherches LA solution à un problème aussi ardu, tu trouveras des industriels qui se feront un plaisir de te vendre leur solution.
On trouve, sur ce forum en particulier, des pistes qui doivent être explorées et éliminées les une après les autres pour espérer trouver une solution.
A toi de juger ce qui est concret de ce qui l'est moins.
Je te souhaite d'obtenir les réponses claires à tes questions claires, et vais classer mes recherches (amicales) d'aide dans la catégorie des "tant pis".
Très cordialement,

[chrtophe]

Ce n'est pas en faisant ce type de réflexion que les choses vont avancer.

Si un algo existe ce n'est pas forcément la peine de refaire la roue. On a tous un jour besoin d'aide pour comprendre quelque chose.

Si tu tu ne veux pas aider, ou que n'as pas la capacité de le faire (cognitive pour reprendre tes termes, problématique de temps,d'empathie, ou autre), ce n'est pas la peine de répondre, surtout avec un commentaire désagréable et condescendant.

[anapurna]

Bonjour,

c'est typequement de la recherche operationnel
La programmation par contrainte est la reponse a ton probleme

Comment ferait tu pour ressoudre ce probleme sans informatique
Pour faire simple :
1°) definir une matrice des couples Parent/Prof Voulu (definir les prioritée)
2°) croisé cette matrice avec les horaire voulue et disponible Si plusieurs horraire possible essayé de les regroupé dans une session la plus courte possible


l'ordinateur va faire exactement la meme chose.
a chaque etapes il reduit ses elements de recherche avec lesresultat precedent
il va tester toutes les combinaison possibles et selon tes choix preetablie va sortir une solution ou pas le cas echeant

imaginons que tu est
3 parent et 10 Professeurs
cela fait donc 30 possibilitéq
les parent ne veulent voir au maximun que 3
il en reste donc que 9
ta recherche d'horaire ne se faras pas sur les 30 possibilitées mais
sur les 9 restant
... et ainsi de suite tu diminue le nombres de possibilité

[larnicebafteur]

Merci à anapurna pour ses éléments de réponse.

Il est vraiment regrettable que sur les forums français, toute catégories confondues, pour une simple question posée, on en arrive à plus de 10 messages échangés dont un seul qui apporte quelque chose de constructif.

Pour tous les autres messages, on trouve :
- des personnes, comme valentin03, qui viennent juste nous injurier ... mais après tout pourquoi ne le ferait-il pas, vu que son message n'est même pas modéré, et qu'il ne reçoit aucun bannissement du forum, donc il continuera
- d'autres qui viennent remettre en cause la question posée (non mais de quel droit, qui suis-je, et pour qui je me prends pour oser chercher de l'aide !!)
- certains qui conseillent de chercher dans les autres messages ou ailleurs (bah oui, j'y avais pas pensé tout seul !!)
- et enfin certains qui promettent des réponses ultérieurement, puis qui finalement capitulent, proposent d'aller acheter un logiciel, ou d'aller chercher ailleurs

Vive la France !