La data science au service de la planification sous contraintes

La data science au service de la planification sous contraintes

Rédigé le 22/06/2020
Laurence Suprano et Adrien Moreau, Axys

Dans le contexte incertain de crise sanitaire, il devient de plus en plus important pour les équipes de planification d’être réactives et de pouvoir ajuster le planning et les ressources en fonction des besoins et de la conjoncture.


Le pauvre planificateur de ressources croule sous les contraintes qui l’assaillent…

La planification des ressources est une activité stratégique dans les entreprises, concernant toutes les strates opérationnelles et managériales. Une attente forte pèse sur le planificateur, devant répondre aux objectifs de la direction et satisfaire les employés tout en préservant l’équité.

Les enjeux sont nombreux : une bonne planification permet d’éviter des coûts additionnels (heures supplémentaires, intérim, dépassement d’annualisation), d’éviter les situations de sous-effectif ou de sureffectif, de faire baisser l’absentéisme, etc.

Le métier du planificateur devient un véritable casse-tête avec les nombreuses contraintes qu’il faut intégrer, comme par exemple :
- Contraintes légales : durée du travail, repos obligatoires, congés payés, périodes de formation, éventuels contrats handicaps et temps partiels, etc.
- Contraintes liées à la satisfaction du personnel : désidératas des employés, etc.
- Contraintes de compétences : Compétences des employés vs tâches à réaliser

En complément de ces contraintes, le contexte actuel de crise sanitaire en a fait naître de nouvelles : distanciation sociale, modes de travail plus souple (télétravail), éventuelles contraintes médicales, etc.

Le nombre de paramètres croissant à intégrer fait que la planification « manuelle » devient de plus en plus chronophage et complexe. Le planificateur perd donc beaucoup de temps sur ces activités au détriment du suivi des KPIs financiers, sociaux et organisationnels et de l’optimisation des processus de production.

Dès lors, il devient nécessaire d’avoir recours à un outil de planification automatique des ressources. Un certain nombre d’outils prêts à l’emploi existent sur le marché, mais ils ne permettent pas toujours une forte réactivité et adaptabilité totale aux spécificités des entreprises.

Quand vient l’heure où les algorithmes se mettent à la rescousse du planificateur !

Face aux outils standards du marché, notre recommandation est d’adopter une approche data.

La planification sous contraintes est un problème d’optimisation bien connu des mathématiciens, faisant partie de la classe des problèmes dits « NP-difficiles », NP signifiant « Non déterministe polynomial ». Sans rentrer dans le jargon mathématique, il s’agit d’une classe de problèmes complexes, dont la résolution peut se faire en un temps polynomial (explosant avec le nombre de lignes de données à traiter).

Différentes méthodes peuvent être utilisées afin de résoudre un problème d’optimisation sous contraintes.

Le recours à la programmation linéaire, qui consiste à minimiser ou à maximiser une fonction objectif et des contraintes linéaires, permet à coup sûr d’obtenir la solution optimale, mais la complexité de calcul est forte et il faudra attendre la résolution complète avant d’obtenir les résultats. En fonction du nombre et de la complexité des contraintes, il faudra donc faire un compromis entre le nombre de contraintes prises en compte et le temps de résolution.

Notre retour d’expérience pour un acteur majeur du monde des services, en partenariat avec un chercheur reconnu de l’Université de Lyon, spécialisé en machine learning et optimisation, montre que cette méthode n’est pas adaptée au regard du volume de données traitées et du nombre de contraintes.

Les métaheuristiques : Gros mots ou substances métaphysiques ?

C’est là qu’interviennent les heuristiques et métaheuristiques ! Contrairement à ce qu’on pourrait penser, ces choses ne sont pas des monstres obscures et carnivores. Plus récemment introduites, ces méthodes permettent de résoudre des problèmes nécessitant l’examen d’un très grand nombre de combinaisons (phénomène d’explosion combinatoire) et reposent sur la stratégie visant à se déplacer dans l’espace des solutions d’une fonction objectif en espérant atteindre un maximum global.

Pour faire simple, faisons une analogie : vous êtes devant une rivière et devez la traverser en sautant de pierre en pierre. La méthode linéaire consisterait à modéliser l’ensemble du problème (distance entre chaque pierre, largeur de la rivière, taille maximale de pas possibles, courant de la rivière, etc.) et calculer le parcours optimal avant de se lancer. L’heuristique consisterait au contraire à vous lancer rapidement et sauter de pierre en pierre en essayant de s’approcher de l’autre rive, quitte à éventuellement revenir en arrière si besoin. Vous l’aurez compris : dans un cas, vous aurez trouvé le meilleur chemin mais dans l’autre, vous seriez probablement arrivé avant sur l’autre rive !

Ces méthodes permettent d’obtenir une solution satisfaisante en un temps acceptable, en n’explorant délibérément qu’une partie de l’espace des combinaisons. Elles sont plus adaptées dans une optique de réactivité.

Les métaheuristiques sont plus évoluées que les heuristiques car elles parcourent l’espace de solutions en essayant d’explorer les zones prometteuses, tout en évitant d’être « emprisonné » par un optimum local (maximum ou minimum). Nous ne pouvons donc que recommander leur usage.

Rentrons encore un peu plus dans le dur du sujet (désolé pour ceux qui aimaient bien les rivières et les pierres). Les métaheuristiques les plus classiques pouvant être utilisées pour un problème de planification sous contraintes sont les suivantes :
• Le recuit simulé : explore l’espace de recherche tout en acceptant de dégrader sa solution afin de sortir des optima locaux. Tout au long du processus, le recuit va de moins en moins accepter ces dégradations, ce qui va le faire converger vers un optimum (que l’on espère) global.
• La méthode Tabou : à l’inverse du recuit simulé, cette méthode est déterministe et a une notion de mémoire. Le choix du meilleur voisin d’une solution pousse l’algorithme à trouver les optima locaux ; et comme l’exploration de l’espace de recherche est effectué en limitant le voisinage de la solution en rendant « tabous » certains mouvements, l’algorithme doit théoriquement visiter l’optimum global.
• Les algorithmes évolutionnaires : issus de la théorie de l’évolution de Darwin, qui manipulent plusieurs solutions en même temps, et qui en les combinant forment de nouvelles solutions. Le fait d’avoir une population de solutions facilite l’exploration de l’espace de recherche, et les meilleures solutions seront favorisées pour participer à la création de nouvelles solutions ce qui aura pour effet de favoriser les combinaisons des « bonnes caractéristiques », et donc de trouver un optimum global.

Selon le cas, une ou plusieurs de ces méthodes peuvent être testées et comparées afin d’obtenir les meilleurs résultats, dans une démarche test & learn.

Vers des activités à plus haute valeur ajoutée !

Vous l’aurez compris, la mise en place de planification sous contraintes répond aux enjeux de réactivité face au contexte actuel incertain et mouvant. Elle vous permettra non seulement d’automatiser les tâches rébarbatives de planification mais aussi d’obtenir des solutions plus optimales et en temps réel. Ce gain de temps pourra vous servir à mieux piloter l’activité par le suivi de vos KPIs : taux d’affectation, heures supplémentaires, intérim, KPIs financiers, absentéisme, etc.
Rappelons tout de même que le déploiement de ce type de modèles ne peut se faire sans une conduite du changement efficace. Ces modèles étant complexes, il faudra en effet vérifier leur bonne appropriation et utilisation par les planificateurs afin de s’assurer de la performance sur le terrain.