Problème de couplage / optimisation

amsel · March 2022

Bonjour,
je suis face à un problème concernant un exercice de recherche opérationnelle.

Dans une école primaire nous avons 4 professeurs qui doivent enseigner 6 matières (Maths, Français, Sport, Histoire-Géo, Anglais, SVT) pour une classe.
Certains de ces professeurs sont multi compétences (ils peuvent enseigner de 2 à 6 matières) et d'autres sont mono compétences.
Le nombre d'heures d'études par matière doit être garanti (chaque matière doit être dispensée à la hauteur de ce qui a été fixé en terme d'heures).

Je cherche donc une répartition à faire entre les professeurs : exemple il faut faire 15h de maths, 12h de Français, 4h de sport : Professeur A va enseigner 50% de son temps les maths, 25% le sport et 25% le Français, professeur B enseignera 75% le sport et 25% le Français, professeur C va enseigner 50% de son temps les maths et 50% le Français (il n'est pas qualifié pour faire prof de sport). Il ne reste plus d'heure à faire pour professeur D.

Comment trouver une répartition optimisée ?
Je sais qu'il faudra peut être passer par un algo de couplage (mais je sais pas lequel), puis il y aura sûrement de l'optimisation à faire via Simplex
Je ne sais pas par ou commencer donc je suis un peu perdu.
Merci de votre aide.

babsgueye · March 2022

Salut.
Je connais bien la recherche opérationnelle, mais si je comprends bien ton problème, tu cherches le nombre d'heures à affecter à chaque prof pour remplir au mieux le quantum horaire pour chaque matière.
Pour ton exemple, je trouve 13 heures pour le prof A, 1 heure pour le prof B et 17 heures pour le prof C, le prof D n'a pas de temps de travail.

Est ce que j'ai compris ?

amsel · March 2022

Salut,
Effectivement c'est ça, mais comment tu as fait?
En réalité je cherche à faire ça sur une bien plus grande échelle, donc je cherche à implémenter un algorithme pour faire ça.

Merci d'avance pour l'aide

babsgueye · March 2022

Moi j'ai juste résolu un système de trois équation à trois inconnues. Ce que tu dis dans l'exemple, tu peux le traduire en système d'équations. Si c'est plus compliqué, tu ne trouveras peut-être pas des valeurs entières mais tu pourras toujours avoir une solution optimale je pense.

Barjovrille · March 2022

Bonsoir, comment tu évalues que une répartition est plus optimisé qu'une autre ?

amsel · March 2022

Enfait je pense que j'ai mal posé le problème, le but est de trouver le pourcentage idéal pour chaque prof qui permettra de remplir ses heures a faire.

Ce qu'il faut optimiser en priorité est bien les heures à dispenser.

Donc le type de réponse qu'il faut donner est : prof A : 27% maths, 53% Francais, 20% sport etc..

lourrran · March 2022

Barjovrille a posé la bonne question : que cherche-t-on à optimiser, et tu ne réponds pas.
Trouver Le pourcentage 'Idéal' pour chaque prof : comment tu traduis ça en termes mathématiques ou informatiques ?

Dans un problème d'optimisation, on a plein de dispositions qui correspondent aux contraintes, et on veut choisir celle qui donne le meilleur résultat pour une certaine fonction d'évaluation.

Extrait d'un cours pour lycéens : Résoudre un problème d'optimisation, c'est rechercher le couple $(x,y)$ qui, selon le contexte, maximise ou minimise la fonction à optimiser.

Ici, éventuellement, chaque prof a des souhaits, tous les profs préfèrent enseigner les maths et pas le sport. Et on va essayer de satisfaire le prof A, parce que c'est un râleur ... On a les débuts d'une base pour une fonction d'évaluation.

Et selon les volumes de données (nombre de profs , nombre de matières ...) les outils à utiliser sont variables. Pour beaucoup de données, une base serait la méthode de Monte-Carlo. L'autre mot-clé qui va te permettre de trouver des informations, c'est la méthode du gradient. Ou des outils comme Simplex, tu en parles dans le 1er message.
Si tu as peu de données, une recherche systématique de toutes les solutions est même envisageable.

Et a priori, on est plus dans le domaine 'Informatique' que dans le domaine 'Combinatoire'.

babsgueye · March 2022

amsel a dit :
Donc le type de réponse qu'il faut donner est : prof A : 27% maths, 53% Francais, 20% sport etc.

Dans le cas de ton exemple, tu donnes les pourcentages donc ce n'est plus ces pourcentages qu'on cherche.
Dans ce cas là, on a trouvé une solution optimale très facilement parce il n'y a pas beaucoup de contraintes, presque pas si ce n'est le pourcentage sur leur temps qu'ils veulent allouer à chaque matière, et le respect du quantum horaire pour chaque matière. En fait dans ce genre de problème il faut savoir ce qu'on veut. Y a pas besoin de spéculer sur des données qui ne sont pas dans le problème.
Dans ce cas précis, toute autre répartition des heures de travail différente de la solution que j'ai donnée, soit ne permettrait pas de pouvoir respecter le quantum horaire pour chaque matière, soit affecterait à certains profs des heures superflues (sans travail). C'est ça qui signifie que le résultat donné est optimal.

Barjovrille · March 2022

Bonjour, @babsgueye c'est à amsel de donner sa définition de solution optimale selon ses besoins, pour le faire comme lourran a dit il faut définir une fonction d'évaluation ou de coût à minimiser ou (à maximiser ça dépend de comment est posé le problème), la solution optimale sera alors la solution qui respecte ses contraintes et qui minimise (ou maximise) cette fonction. Et dans ses contraintes il a juste dit qu'il faut respecter les nombre d'heures de cours et que chaque professeur a son domaine de compétence. Il n'a jamais dit que si il y a un prof sans travail ça pose problème. Par exemple si il décide qu' il faut minimiser le nombre de professeurs différents qui enseigne à la classe (parce que par exemple si on change trop souvent ça peut déboussoler les élèves de primaires).
Une solution optimale serait alors de mettre le plus de professeur possible sans heure de cours.

babsgueye · March 2022

@Barjovrille je vois bien ce que vous dites, mais je dis tout simplement que c'est pas à moi d'imaginer des contraintes qu'il n'a pas mises. C'est pourquoi je dis qu'on est dans un cas de figure très simple, ce qui logiquement simplifie la méthode et donne un résultat très précis.

lourrran · March 2022

Ce n'est pas à toi d'imaginer des contraintes qu'il n'a pas mises. Certes. Mais tu dois essayer de comprendre la question. Et si besoin l'inciter à donner les informations qu'il a oubliées.

Amsel n'a toujours pas formulé correctement sa question.

J'essaie péniblement de comprendre le 1er message. En particulier ce passage :

exemple il faut faire 15h de maths, 12h de Français, 4h de sport : Professeur A va enseigner 50% de son temps les maths, 25% le sport et 25% le Français, professeur B enseignera 75% le sport et 25% le Français, professeur C va enseigner 50% de son temps les maths et 50% le Français (il n'est pas qualifié pour faire prof de sport). Il ne reste plus d'heure à faire pour professeur D.

A priori, mais ce n'est pas 100% clair, les contraintes sont :

il faut faire 15h de maths, 12h de Français, 4h de sport

Et la suite, c'est la réponse, ce n'est pas la suite des contraintes :

Professeur A va enseigner 50% de son temps les maths, 25% le sport et 25% le Français, professeur B enseignera 75% le sport et 25% le Français, professeur C va enseigner 50% de son temps les maths et 50% le Français (il n'est pas qualifié pour faire prof de sport). Il ne reste plus d'heure à faire pour professeur D.

Babsgueye, tu parles de solution optimale.... Tu pourrais aussi dire que tu as trouvé la pire solution, ce serait aussi correct. On parle de solution optimale quand on choisit parmi plusieurs solutions. Quand il n'y a qu'une solution, ça n'a pas de sens de parler de solution optimale.

Tant que Amsel n'aura pas donné une formulation correcte de son besoin, il est illusoire de lui apporter des solutions.

babsgueye · March 2022

@lourrran dans sa formulation j'ai compris que le prof A veut faire 50% de son temps en maths, 25% de son temps en en français et 25% de son temps en sport, etc... Ce qui est peut être ambiguë dans la formulation c'est quand il dit ''Il ne reste plus d'heure à faire pour le prof D'' au lieu de ''le prof D ne veut enseigner aucune matière'' ou en tout cas le libeller autrement.

Pourquoi la solution est optimale, je l'ai dit dans le message précédent. Par exemple 20 heures pour le prof A, 20 heures pour le prof B, 20 heures pour le prof C ça arrangerait aussi son problème, mais c'est pas une solution optimale parce que des profs resteront un temps à ne rien faire (''et ils seront payés par exemple'').

amsel · March 2022

Bonjour,
Merci beaucoup pour vos réponses et pour votre implication.
Effectivement je me suis rendu compte que j'avais très mal exprimé mon problème.

Je vais retenter de l'expliquer en prenant en compte tous vos super messages.

Pour cela je vais changer d'exemple et beaucoup plus l'expliciter.

Nous sommes dans un fast food qui fait uniquement des burgers.

La cuisine comporte plusieurs postes de travail: 2 fours à pain, 3 postes de cuisson des steaks, 1 poste de préparation des toppings (salade tomate fromage) et 4 postes d'assemblage des burgers.

Je me limite à ça pour le moment mais on peut imaginer qu'il y ait beaucoup plus de postes de travail (ex: 3 postes en plus qui font des desserts, 2 postes de boissons).

Dans notre fast food il y a également des employés polyvalents, avec chacun leurs compétences :
Compétences Employé 1 : four à pain, cuisson des steaks
Compétences Employé 2 : cuisson des steaks, assemblage, desserts
Compétences Employé 3: préparation des toppings, cuisson des steaks, desserts
Compétences Employé 4: four à pain, préparation des toppings
Compétences Employé X : etc......

On considère qu'on reçoit la liste des burgers à faire le matin même et qu'ils doivent être prêts pour le soir même et donc il faut organiser notre journée de travail.

En réalité cela revient à savoir combien de temps chaque poste de travail va être occupé.

Ce que je cherche à faire, c'est compte tenu des compétences de chaque employé, et du travail à faire sur chaque poste, comment faire pour les répartir de façon à ce qu'on arrive à fabriquer tous les burgers demandés.

Les employés n'ont pas de préférence, ils peuvent être affectés partout du moment qu'ils sont compétents pour réaliser la tâche.'

La vraie contrainte que je vois est que les postes qui seront les plus utilisés (ex: cuisson des steaks, car tous les burgers ont un steak) doivent tout le temps être occupés pour faire le maximum de steaks.

Si vraiment il faut ajouter des contraintes, on peut par exemple imaginer que certains employés sont meilleurs sur un poste que l'autre et donc il faut le prioriser sur le poste où il est le plus fort.

Je comprends bien que d'un point de vue mathématique, on cherche surtout à savoir qu'est ce qu'il faut maximiser, quelles sont les contraintes, mais en réalité j'ai du mal à définir cela et trouver le point de départ.

En sortie de mon algorithme / Solveur: (ce à quoi je m'attends c'est bien une répartition du temps de mes employés que me proposera le solveur, et qui me garantie que les burgers seront fabriqués)

Je veux avoir quelque chose comme ça:
Sur une journée de 7h de travail :

Employé 1: 50% de son temps sur four a pain; 50% de son temps sur cuisson des steaks (cela veut dire qu'il reste (2x7h) - 3,5h = 10,5h à distribuer sur les fours à pain et (3x7h) - 3,5h = 17,5h

Employé 2 : 25% de son temps sur la cuisson des steaks; 25% sur l'assemblage; 50% sur les desserts ( cela veut dire qu'il reste 10,5h - 25%x7h=8,25h de temps à distribuer sur la cuisson des steaks)

Employé 3: etc.... je pense que vous avez compris ^^ sinon dites le moi.

Le problème que je pense identifier c'est que si je raisonne de manière séquentielle (employé par employé) je ne suis pas sûr de trouver la bonne répartition puisque j'ai bloqué la répartition de l'employé 1. ( peut etre que je me trompe)

Il faudrait donc penser à une autre manière de faire ( si vous avez des propositions, je serais ravi)

Je vous remercie et j'ai hâte de vous lire !!

N'hésitez pas s'il vous manque des précisions

lourrran · March 2022

Tu as un autre problème à gérer, c'est que les taches ne peuvent pas être faites dans n'importe quel ordre. On doit cuire les steacks avant d'assembler les burgers ! Et j'imagine qu'il y a plein d'autres contraintes de ce type.
Les mots clés pour trouver de la littérature sur le sujet, ça ressemble à 'optimisation planning production' ; tu vas trouver plein de publicités, parce que c'est un problème compliqué, et il y a beaucoup de business autour de ces questions.

Tu peux faire ton planning demi-heure par demi-heure.
Pour la Première demi-heure, tu sais que tu ne peux pas faire d'assemblage, puisqu'il n'y a aucun steack de cuit. Tu regardes les taches où il y a le plus de besoin par rapport au nombre de personnes capables de faire ces taches. Et tu mets un max d'individu sur ces taches les plus 'demandeuses' de temps.
Et tu répartis les ressources ainsi...

En gardant en tête que certaines taches sont bloquantes. Si tu ne mets pas beaucoup de personnes sur la cuisson, tu ne pourra commencer l'assemblage que très tard. Et ça risque de bloquer.

Faire cette planification rigoureusement, c'est compliqué. Et c'est pour ça qu'il y a des outils commerciaux sur le créneau.
Tu dois pouvoir faire quelques plannings type. Sauf si les employés présents changent trop d'un jour sur l'autre,

Problème de couplage / optimisation

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 12