Planifier à l'œil : un luxe que vous payez sans le voir

Ce qu'est un solveur

Un solveur est un programme d’intelligence artificielle qui bâtit un plan à votre place. On lui décrit les décisions à prendre (ex. quelle tâche va sur quelle machine, quel chauffeur prend quelle route), les règles à respecter (ex. l'opération A doit être faite avant l’opération B) et le coût à réduire (ex. nombre de postes, heures de production, kilomètres parcourus). Il explore ensuite un ensemble de plans possibles et garde le meilleur qu'il a trouvé dans le temps qu'on lui accorde. 

Les solveurs du commerce sont des moteurs de résolution génériques. Le même programme doit bien se comporter sur des milliers de problèmes qu'il ne connaît pas d'avance, du transport aérien à la planification d’un atelier de production. Et ça va plus loin. Deux entreprises qui fabriquent la même chose n'ont pas nécessairement le même problème. L'une a une machine toujours surchargée alors que l'autre a une équipe de soir réduite. Chacun a sa façon de décrire ses règles, et un moteur générique doit toutes les recevoir dans le même moule.

Notre approche est différente. Nous partons d'un solveur de fondation que nous réutilisons d'un projet à l'autre. Pour chaque problème, nous réalisons des ajustements sur mesure au solveur qui exploitent les particularités du problème. 

Comment mesure-t-on un solveur ?

Le domaine a ses examens standardisés, les benchmarks. Ce sont des collections de problèmes publiées par la communauté de recherche. Chaque problème d'une collection s'appelle une instance, et pour chaque instance, on connaît la meilleure solution jamais trouvée par qui que ce soit, souvent après des jours de calcul. Un solveur est jugé sur sa capacité à s'approcher de cette meilleure solution connue, ou à la battre, dans un temps limité.

La concurrence en a fait sa vitrine et publie ses résultats sur des instances de taille et de complexité variables. N'importe qui peut refaire l'exercice. Nous l'avons fait sur trois benchmarks qui ressemblent aux problèmes que rencontrent nos clients.

Maintenance du Réseau de Transport Électrique (RTE). Le défi posé par le gestionnaire du réseau français RTE : Planifier l'entretien d'un réseau électrique en l'exposant au plus petit risque possible. La tâche consiste à donner une date de début à chaque intervention, sur un horizon qui va jusqu'à 365 périodes, en gardant la charge de chaque équipe dans les limites permises et sans lancer en même temps deux travaux qui ne peuvent pas se chevaucher à cette saison. Les organisateurs fournissent, pour chaque période, un éventail de situations possibles du réseau avec le risque associé à chacune. Le plan est jugé sur le risque moyen et sur le risque des pires scénarios. 45 instances et jusqu'à 706 interventions de maintenance.

Atelier flexible. L'objectif est de faire passer toutes les pièces dans un atelier de production en terminant le plus tôt possible. Chaque pièce doit suivre ses étapes de production dans un ordre fixé, et chaque machine ne fait qu'une chose à la fois. Une même opération peut se faire sur plusieurs machines. Il faut choisir sur quelle machine va chaque opération et dans quel ordre. 336 instances, jusqu'à 100 pièces, 25 étapes par pièce, 500 opérations et 60 machines.

Équilibrage de ligne. Une ligne d'assemblage avance au même rythme pour tout le monde. Chaque poste dispose du même temps pour faire sa part, le temps de cycle, et la pièce avance ensuite qu'il ait fini ou non. Il faut donc répartir les tâches entre les postes sans qu'aucun dépasse ce temps, en respectant l'ordre des opérations, et en utilisant le moins de postes possible. 525 instances à 100 tâches et 525 à 1000 tâches.

Dans les trois cas, nous reprenons leur problème sans y toucher : mêmes contraintes, même objectif, même budget de calcul d'une minute, et 8 cœurs de calcul. Notre solveur part d'une fondation commune et de techniques d'IA, que nous ajustons aux particularités de chaque problème.

Les chiffres

Le tableau reprend les chiffres publiés par la concurrence, sans retouche. En une minute, un solveur peut ne trouver aucun plan valide sur une instance difficile. La première ligne de chaque bloc RTE donne la part des instances où un plan est trouvé. Dans les lignes d'écart moyen, un écart négatif veut dire que la solution bat la meilleure solution connue. Chacune de nos solutions a été revalidée par un vérificateur indépendant, et la maintenance RTE par le vérificateur officiel du défi.

Sur les petits problèmes, l'écart entre les solveurs est mince. Sur les grands problèmes, les moteurs génériques ont plus de difficulté alors que le nôtre continue de trouver des solutions, souvent meilleures que tout ce qui a été publié. Sur une ligne d'assemblage, un poste de moins veut dire une station à doter en moins, à chaque quart, toute l'année. Dans un atelier, quelques pourcentages de durée totale en moins, ce sont des heures-machine récupérées sur chaque commande.

Ce que ça veut dire pour vous

Les trois benchmarks sont des problèmes épurés. Vos opérations portent bien plus de règles que ça : des quarts, des certifications, des préférences d'équipe, des clients prioritaires, des équipements qui tombent en panne. Un solveur générique traite chaque règle avec une recette standard, la même pour tout le monde. Un solveur ajusté est construit autour de la manière dont ces règles se combinent chez vous et à votre réalité d’entreprise. Sa recherche est faite pour votre problème et pour aucun autre. Plus le problème a ses particularités, plus l’écart se creuse. C'est ce travail d'ajustement que les chiffres ci-dessus mesurent.

Ce travail sur mesure reste abordable, parce que nous repartons chaque fois du même solveur de fondation. Une PME y a ainsi accès au même titre qu'une grande entreprise. Voici trois cas où nous l'avons appliqué.

Résultats clients réels

Planification d'horaire collégial : Au niveau collégial, monter la grille horaire prenait environ 520 heures par année. Baseline a construit avec le client un moteur qui place 550 cours, 500 professeurs et 140 locaux, puis répartit 29 000 inscriptions par session, sous une trentaine de types de contraintes venues de 19 départements. Le calcul prend moins de deux minutes, ne laisse aucun conflit d'horaire et maximise significativement mieux les demandes pédagogiques qu'avant.

Routage du câblage électrique commercial : Le câblage d'un immeuble commercial ou d'une tour à bureaux ne s'optimise à peu près jamais. L'ingénieur électrique n'a le temps que de placer les grands équipements, l'électricien tire les câbles comme il peut sur le chantier, et chaque détour se paie en mètres de cuivre. Baseline a construit le moteur du module d'optimisation électrique d'un client spécialisé en conception de bâtiments. Il raccourcit les parcours de câbles en respectant les contraintes de construction et le code de l'électricité canadien, parce qu'un circuit plus court ne vaut rien s'il n'est pas conforme.

Gestion de flotte : Sur les sites miniers, les centaines de kilomètres de routes de service ne figurent sur aucune carte numérique. Les véhicules s'attribuent au jour le jour, dans des fichiers Excel, département par département. Baseline a reconstitué la carte d'un site à partir de millions de points de télémétrie, puis livré le moteur d'optimisation qui bâtit les itinéraires à partir de cette carte pour un spécialiste québécois de la télémétrie véhiculaire. Plus de 400 véhicules légers, plusieurs centaines d'opérateurs, sous contraintes d'horaire, de capacité et de disponibilité de la main-d'œuvre et plus. Les améliorations apportées à la solution de télémétrie et le moteur d'optimisation retirent ensemble une soixantaine de véhicules de la flotte du site.

Pour aller plus loin

Cette approche d'optimisation a été conçue et écrite au Québec, par une coopérative d'ici. Le savoir-faire qui tient tête aux grands noms de l'optimisation existe au Canada, et il travaille pour les organisations d'ici, sur leur plancher, avec leurs données. Avant d'envoyer votre budget d'optimisation à l'étranger pour un moteur qui ne connaît pas votre usine, regardez ce qui se fait localement.

Si une de vos opérations coûte plus cher qu'elle ne devrait, un horaire, une tournée de livraison, une ligne de production, écrivez-nous. Nous passons du temps avec votre équipe pour comprendre vos objectifs d'affaires, nous montons un modèle de référence sur vos données, et nous chiffrons l'écart entre votre façon de faire actuelle et ce qui est atteignable. Quand vous êtes prêts, nous mettons l'approche en production. Le développement logiciel est notre métier autant que l'IA.