News

La Recherche Opérationnelle pour l’optimisation de la planification de formations

Les gestionnaires, les décideurs, les ingénieurs doivent faire face à des problématiques d’optimisation :

  • Réduction de coûts de production
  • Gestion de ressources et de personnes
  • Amélioration de la performance des machines
  • Organisation des temps et du travail
  • etc.

Les bons gestionnaires et ingénieurs font appel à la Recherche Opérationnelle (RO). En effet, elle joue un rôle clé dans le maintien de la compétitivité, en facilitant les tâches de gestion, d’optimisation et de prise de décision.

La RO est un ensemble d’outils scientifiques dédié à l’élaboration de meilleures décisions. La RO est une discipline qui associe les mathématiques, l’économie et l’informatique. Elle commence par la modélisation mathématique des situations complexes, puis la création d’algorithmes de résolution dédiés.

Dans la section suivante nous présentons un cas concret d’application de la RO.

Planification de formations

Problématique

Le groupement Eqip organise chaque année pour ses adhérents une convention annuelle sur 2 jours. Durant cette convention, plus de 180 formations sont proposées à plus de 500 participants. Eqip souhaite réduire et simplifier ce processus d’élaboration des plannings de formation et d’affectation des participants tout en répondant aux souhaits d’inscription des participants de manière maximale. Eqip souhaite que l’affectation des formations aux salles et des participants aux formations soient automatisées.

La problématique d’organisation d’Eqip est commune à la tenue d’autres conférences et manifestations. L’assignation des formations à des salles et des créneaux horaires, où la demande de formations n’est pas connue à l’avance.

Les objectifs ambitionnés sont :

  • Pour chaque personne, de déterminer le planning des formations à suivre en satisfaisant au mieux (ou toutes) ses priorités.
  • Pour chaque formateur, de déterminer les formations à dispenser, les salles et les plages horaires, en prenant en compte ses disponibilités.
  • Pour chaque formation dispensée, d’assigner une salle et une plage horaire dans laquelle elle aura lieu, en minimisant les coûts d’utilisation des salles.

A partir de ces objectifs, nous pouvons déterminer :

  • Pour chaque personne inscrite, l’ensemble des formations auxquelles elle participera, l’heure et la salle.
  • Pour chaque formation dispensée, la liste des participants, la salle et la plage horaire dans laquelle elle aura lieu.
  • Pour chaque formateur, la liste des formations à dispenser, les participants aux formations, les salles et plages horaires.
  • L’emploi par plage horaire de chaque salle (formations et participants)

Résolution

Pour répondre aux besoins d’Eqip, nous avons :

  1. Proposé un modèle mathématique pour l’optimisation de la planification des sessions de formations.
  2. Conçu un algorithme d’optimisation GRASP (Greedy randomized adaptive search procedure) dédié à résoudre leur problématique.

Modèle mathématique

Nous avons proposé un modèle mathématique linéaire en nombres entiers. Nous avons défini deux types de variables de décision binaires pour l’affectation de participants aux formations et pour l’affectation des formations aux salles et créneaux horaires. Nous avons pris compte les contraintes de :

  1. Disponibilité des participants, des salles et des formateurs, suivantes :
  2. Les ressources limitées : nombre et capacité de salles
  3. Un temps de planification restreint

La satisfaction d’une personne est calculée comme la somme des priorités des formations affectées au participant. La satisfaction globale est la somme de toutes les satisfactions des participants. Nous souhaitons maximiser la satisfaction de toutes les personnes inscrites.

Méthode GRASP

Nous avons choisi d’implémenter en première instance la métaheuristique GRASP (Greedy randomized adaptive search procedure) du à sa simplicité et son efficacité dans la construction des solutions. En comparaison à d’autres méthodes telles que les algorithmes génétiques ou les algorithmes à voisinages multiples, cette méthode n’a pas besoin de codage et gestion de la population des solutions ou l’implémentation des voisinages complexes.

Cette méthode itérative, exécute un certain nombre de fois la construction et amélioration des solutions. La meilleure solution trouvée est gardée. Une solution est construite en deux phases : la phase de construction gloutonne aléatoire de la solution puis la phase d’amélioration de la solution.

La phase de construction combine les méthodes gloutonnes et aléatoires. La construction d’une solution se déroule par étapes. A chaque itération, une formation est affectée aux créneaux horaires et un ensemble de participants est affecté à la formation.
A chaque itération les formations les plus intéressantes à affecter sont placées dans une liste appelée RCL (Restricted Candidate List), c’est la partie gloutonne de l’algorithme. La formation à affecter est choisie aléatoirement, c’est la partie aléatoire de l’algorithme. Cette partie permet de diversifier la génération des solutions.

Pour notre problématique, la boucle principale de construction de l’algorithme :

  1. Calcule des combinaisons pour la création de la Restricted Candidate List (RCL)
  2. Sélection aléatoire d’un élément de la RCL
  3. Recherche d’une salle. Vérification de type de salle et de la disponibilité
  4. Recherche d’un formateur. Vérification de la disponibilité et la capacité à dispenser la formation
  5. Affectation de la salle, créneaux horaire, formateur et session
  6. Assignation des personnes à la formation

A chaque itération le critère d’arrêt est calculé : Vérification de nombre de personnes et de formation à assigner et modification du nombre de session de formations à suivre.

La faisabilité de la solution est vérifiée à la fin de la construction. Si la solution n’est pas faisable les fonctions de réparation de solution sont appelées.

Résultats

Les résultats obtenus par notre méthode GRASP sont satisfaisants en termes de fonction objectif et de temps de calcul.

Les tests menés sur les données d’Eqip 2016 : 127 formations, 16 salles, 485 personnes et 16 créneaux horaires. L’algorithme a donné des solutions en environ 2 minutes avec une satisfaction globale d’environ 90%.

RO

Ce que peut vous apporter la RO

  • La prise de meilleures décisions
  • Des gains de temps
  • Une meilleure productivité 
  • Des améliorations dans l’organisation et la planification
  • Des gains financiers

 

Lire la suite

La probabilité d’une surprise est de 58%!

Paul CAHU (Ingénieur généraliste – Docteur en Economie)

-Explications de la méthode de calcul-

L’analyse des sondages publiés depuis le début de la campagne officielle (10 Avril) et notamment la prise en compte des suretés de choix par candidat confirment que les 4 principaux candidats sont tous susceptibles d’atteindre le deuxième tour. Deux sondages (BVA et Ipsos) permettent même de calibrer des marges d’incertitude par candidat. L’incertitude révélée par ces deux enquêtes est tout à fait cohérente avec ce que l’on peut déduire de la performance historique des sondages politiques en France. La marge d’erreur réelle des sondages est bien supérieure à ce que les lois de la statistique pourraient laisser supposer, elle atteint 4%.

D’après les sondages de la dernière ligne droite, la probabilité que Fillon soit au deuxième tour est de plus d’une chance sur 4. La probabilité que Mélenchon soit qualifié est d’une chance sur 3. La probabilité que Macron ou Le Pen soient qualifiés est de 69%.

unnamed (1)

En définitive, bien que le duo Macron-Le Pen soit bien le plus probable, la probabilité de cette affiche pour le second tour est inférieure à 1 chance sur 2.
Si vous aimez faire des paris, misez donc sur une surprise !

camembert

Lire la suite

Une surprise au premier tour est fort possible…

…une surprise au second, très improbable

Paul CAHU (Ingénieur généraliste – Docteur en Economie)

-Explications de la méthode de calcul-

L’incertitude diminue mais reste élevée à l’approche du second tour

A l’approche de l’élection, les erreurs des sondages en tendance à s’améliorer. Ils sont donc plus prédictifs des résultats de l’élection. A 15 jours de l’élection, nous supposons que l’erreur de mesure des sondages est de 4 points pour le premier tour et de 5 points pour le second. Historiquement à cette date, les erreurs observées – c’est à dire l’écart entre les sondages moyens et le résultat réel de l’élection – sont inférieurs. Mais comme l’indécision des électeurs est encore importante et que la participation pourrait être plus faible. Nous considérons que l’incertitude est plus importante. A titre de comparaison, l’erreur pour 2012 était de moins de 2 points au second tour et l’erreur lors du Brexit était de 2 points.

Plus de 4 chances sur 10 pour que Fillon ou Mélenchon soient au second tour

L’arrivée de J-L. Mélenchon dans le quatuor de tête et la chute dans les sondages de B. Hamon modifie cependant fortement les probabilités pour le second tour. En se basant sur les sondages réalisés lors des 10 derniers jours, la probabilité que M. Le Pen et E. Macron soient les deux finalistes n’est que de 58%. Autrement dit, il y a plus de 4 chances sur 10 pour que soit J-L. Mélenchon, soit F. Fillon (soit les deux) soient qualifies pour le second tour.

A1

 

 

En calculant les probabilités de qualification par candidat, on constate que J-L. Mélenchon a 1 chance sur 5 de se qualifier, F. Fillon 1 chance sur 4, E. Macron 4 chances sur 5 et M. Le Pen 3 chances sur 4.

A2

J-L. Mélenchon a 4 fois plus de chances d’être élu que M. Le Pen

D’après les quelques sondages de second tour disponibles, J-L. Mélenchon serait dans une position plutôt favorable s’il arrivait au deuxième tour. Il aurait 1 chance sur 4 d’être élu face à E. Macron, ce qui en fait son opposant le plus sérieux. Face à un candidat de droite, ces chances sont très bonnes: 93% face à F. Fillon et 92% face à M. Le Pen. Au total, sa probabilité de victoire au 12 Avril est de 12%.

 

Les chances de F. Fillon sont en dessous de 9%

D’après les sondages actuels, F. Fillon ne peut espérer être élu que face à M. Le Pen, avec 84%. La probabilité qu’il batte E. Macron est inférieur à 0,5%.

 

M. Le Pen n’a guère de chances

En raison d’un grand nombre de sondages concordants réalisés depuis le mois d’Avril et d’une diminution notable de la proportion d’électeurs indécis, les chances de M. Le Pen s’amenuisent. Alors que sa probabilité de victoire a atteint les 20% début Mars, elle a plongé dans les sondages à la suite des deux débats. La possibilité d’une qualification de J-L. Mélenchon limite également ses chances de recontrer F. Fillon au 2e tour, le seul candidat contre lequel elle pourrait raisonnablement espérer. Ces chances de battre E. Macron sont de 1.6% à l’heure actuelle tandis qu’elle a encore 16% de chances de l’emporter si elle devait rejoindre F. Fillon au second tour.

A3

 

Lire la suite