L'ingénierie de la décision

Ce que le parcours a mis sur la table

Chaque chapitre a apporté une méthode, et chaque méthode a son prix. Le tableau les rassemble, avec ce que chacune demande avant de rendre quoi que ce soit.

Le chapitre 12 a comparé ces méthodes, et montré surtout comment on se trompe en le faisant.

Métaheuristique maison ou solveur

Ces comparaisons ont mesuré des méthodes que le parcours a écrites à la main, avec quelques dizaines de lignes chacune. Avant de mettre l'une d'elles en production, il faut se demander si elle est nécessaire : il existe des logiciels dont c'est le métier de résoudre ce genre de problème, écrits par des équipes qui y passent leur vie.

Ce que font les solveurs

Ce qui les distingue des méthodes du parcours tient en trois traits. Ils exigent un modèle : le problème doit s'écrire dans le langage de l'outil (des inéquations linéaires, des contraintes prédéfinies, un graphe de distances), là où une métaheuristique n'exige qu'un coût à évaluer. Ils donnent une garantie : une borne, un écart, parfois une preuve, quand une métaheuristique ne rend qu'une solution. Et ils sont écrits par d'autres, testés pendant des années sur des milliers de cas, ce qui se paie en dépendance à une bibliothèque et en une part d'opacité.

Le même problème, deux solveurs

L'ordonnancement des dix ordres du chapitre 6 (somme des retards, optimum de 17 heures) s'écrit pour les deux premiers solveurs. Pour un solveur en nombres entiers, que PuLP alimente, il faut le rendre linéaire. Le modèle indexé par le temps le fait : une variable binaire $x_{j,t}$ vaut 1 si l'ordre $j$ commence à l'heure $t$. Le retard d'un ordre est alors connu d'avance pour chaque $t$, donc l'objectif est une somme de coûts fixes. Chaque ordre commence une fois ; à chaque heure, la machine fait au plus un ordre.

Le nombre de variables croît comme $n \times H$, produit du nombre d'ordres par l'horizon : c'est le prix d'un modèle linéaire qui discrétise le temps. Pour dix ordres, ce prix est modeste.

Le solveur rend le statut Optimal, avec sol_status à 1 : l'optimum est prouvé, la borne du solveur a rejoint sa meilleure solution. Il rend une somme des retards de 17 heures et un ordre, l'un des douze qui atteignent 17 heures ; sur un poste, CBC peut en rendre un autre, pour les mêmes 17 heures. Le modèle a 424 variables et 56 contraintes.

Le même problème pour CP-SAT s'écrit autrement : une variable entière par ordre, son heure de début, un intervalle par ordre, et une seule contrainte, add_no_overlap, qui dit qu'il n'y a qu'une machine. Le code n'est pas exécutable dans la page : OR-Tools n'est pas disponible dans le moteur Python du navigateur. Il se lance sur un poste, après pip install ortools, et il est montré ici dans un encadré de texte que le site n'exécute jamais.

from ortools.sat.python import cp_model

DUREES = [2, 3, 2, 2, 5, 5, 2, 9, 7, 9]
ECHEANCES = [29, 37, 17, 27, 18, 31, 20, 26, 11, 32]
n, horizon = len(DUREES), sum(DUREES)

modele = cp_model.CpModel()
debuts = [modele.new_int_var(0, horizon, f"debut_{i}") for i in range(n)]      # une variable entiere par ordre
intervalles = [modele.new_fixed_size_interval_var(debuts[i], DUREES[i], f"ordre_{i}") for i in range(n)]
modele.add_no_overlap(intervalles)                       # une seule machine : jamais deux ordres a la fois

retards = []
for i in range(n):
    retard = modele.new_int_var(0, horizon, f"retard_{i}")
    modele.add(retard >= debuts[i] + DUREES[i] - ECHEANCES[i])       # le retard vaut au moins le depassement
    retards.append(retard)
modele.minimize(sum(retards))                            # et la minimisation le pousse a n'en valoir pas plus

solveur = cp_model.CpSolver()
solveur.parameters.max_time_in_seconds = 10
statut = solveur.solve(modele)
print(solveur.status_name(statut), "retards :", int(solveur.objective_value))
print("ordre :", [f"O{i + 1}" for i in sorted(range(n), key=lambda i: solveur.value(debuts[i]))])
print("borne :", solveur.best_objective_bound)

Les deux modèles rendent les mêmes 17 heures, et leurs formes diffèrent : le premier discrétise le temps et compte 424 variables, le second en a dix, avec des intervalles, et se lit presque comme l'énoncé. L'ordre affiché peut changer d'un lancement à l'autre : plusieurs ordres valent 17 heures, et un solveur qui travaille en parallèle n'a aucune raison de toujours tomber sur le même. Pour dix ordres, CP-SAT rend l'optimum en environ un dixième de seconde.

Quand le solveur gagne

Il gagne, et souvent de loin, dans quatre situations.

• Un modèle propre. L'ordonnancement ci-dessus, l'affectation, la découpe de barres (chapitre 4) : les contraintes s'écrivent, l'objectif est linéaire.
• Une instance de taille moyenne. Le solveur passe là où l'énumération et les métaheuristiques n'ont qu'une réponse approchée.
• Une preuve utile. Savoir que la solution est à 0 % de l'optimum, ou à au plus 2 %, change ce qu'on peut promettre.
• Des contraintes qui changent souvent. Ajouter une contrainte est ajouter une ligne au modèle, sans relire la recherche.

Le programme suivant en donne une démonstration qui touche le parcours de près. Il recalcule, dans la page, l'optimum de la plaque P-600, celui que les chapitres 7 à 11 emploient depuis le début comme référence : un modèle en nombres entiers avec une variable binaire par arête, deux arêtes par point, et des coupes de sous-tours ajoutées tant que la solution comporte plusieurs boucles. C'est ainsi que les solveurs traitent le voyageur de commerce : on relâche la contrainte de connexité, on résout, on regarde, on ajoute ce qui manque.

Quatre tours de résolution suffisent : la première solution, sans contrainte de connexité, fait 2 607,22 mm en onze boucles, la deuxième 2 698,48 en sept, la troisième 2 756,18 en deux, la quatrième 2 788,70 en une seule. La borne monte à chaque tour et rejoint la solution : l'optimum est prouvé. Le calcul prend moins d'une seconde, sur un poste comme dans la page ; dans la page, le premier bloc qui importe pulp attend en plus quelques secondes, le temps de charger le solveur.

Et c'est mieux que tout ce que le chapitre 12 a mesuré : à une demi-seconde, les meilleures médianes des méthodes du parcours sont à près d'un pour cent de l'optimum, quand le solveur donne l'optimum, et sa preuve. La bibliothèque de routage d'OR-Tools, avec la construction et la recherche locale guidée d'un seul appel (code plus bas), rend 2 790,44 mm, soit 0,06 % au-dessus de l'optimum, avec un dixième de seconde de recherche.

from math import dist
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# POINTS : le depart (0, 0) puis les 60 trous de P-600, comme au chapitre 7.
N = len(POINTS)
ECHELLE = 100                                    # OR-Tools calcule en entiers : des centiemes de millimetre
DISTANCE = [[round(dist(a, b) * ECHELLE) for b in POINTS] for a in POINTS]

gestionnaire = pywrapcp.RoutingIndexManager(N, 1, 0)          # N points, un vehicule, depart au point 0
routage = pywrapcp.RoutingModel(gestionnaire)
cout_de_l_arc = routage.RegisterTransitCallback(
    lambda i, j: DISTANCE[gestionnaire.IndexToNode(i)][gestionnaire.IndexToNode(j)])
routage.SetArcCostEvaluatorOfAllVehicles(cout_de_l_arc)

reglages = pywrapcp.DefaultRoutingSearchParameters()
reglages.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC   # construire (chapitre 6)
reglages.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH  # puis chercher
reglages.time_limit.FromMilliseconds(500)

solution = routage.SolveWithParameters(reglages)
i, ordre = routage.Start(0), []
while not routage.IsEnd(i):
    ordre.append(gestionnaire.IndexToNode(i))
    i = solution.Value(routage.NextVar(i))
longueur = sum(dist(POINTS[a], POINTS[b]) for a, b in zip(ordre, ordre[1:] + ordre[:1]))
print(f"{longueur:.2f} mm")

Quand cesse-t-on d'y arriver ? Sur les n premiers trous de la même suite de plaques, le même modèle, avec les coupes ajoutées de la même façon, donne les temps suivants, mesurés hors de la page en écrivant le modèle directement pour scipy.optimize.milp, la forme brute que PuLP alimente ; écrit avec PuLP, le même calcul fait les mêmes tours en des temps du même ordre, puisque HiGHS fait le travail. Les colonnes de droite donnent l'écart à l'optimum de la bibliothèque de routage, pour trois durées de recherche.

L'exactitude coûte de plus en plus cher : de l'ordre de 0,3 seconde pour soixante trous, 9,8 secondes pour cent, 40 secondes pour deux cents et 2,5 minutes pour trois cents, avec ce modèle et cette façon simple d'ajouter les coupes (un solveur spécialisé, Concorde, irait bien plus loin). Le routage d'OR-Tools a l'allure inverse. Il est excellent sur soixante trous (0,06 % au-dessus de l'optimum dès un dixième de seconde), et perd du terrain à court terme quand la plaque grandit : à deux cents trous, 6,89 % au bout d'une demi-seconde et 5,89 % au bout de cinq secondes ; à trois cents, 7,29 % puis 1,81 %. Le temps de l'exact dépend de l'instance autant que de sa taille : cent cinquante trous se sont résolus plus vite que cent. Ce compromis, une bonne solution vite ou la meilleure plus tard, est celui d'une métaheuristique, et la bibliothèque le propose déjà écrit. Chaque comparaison de métaheuristiques de ce parcours a d'ailleurs un optimum de référence parce qu'un solveur l'a calculé.

Quand la métaheuristique maison gagne

Elle gagne, mais sur d'autres critères que la qualité brute d'un problème standard, où on vient de voir que le solveur la bat.

• Un coût qui ne s'écrit pas comme un modèle : non linéaire, calculé par une simulation, qui dépend de la séquence entière. Une métaheuristique n'exige qu'une fonction cout(solution).
• Une très grande instance, hors de portée de l'exact et du routage standard, où il faut une solution acceptable en un temps fixé.
• Le temps réel : une recherche qui peut être interrompue à tout instant en rendant la meilleure solution vue, et qui repart de la solution courante quand un ordre arrive.
• Des contraintes bizarres, propres à l'atelier, qu'aucune contrainte prédéfinie ne dit.
• Le contrôle : pas de dépendance, un code qu'on lit en entier, qui s'exécute sur n'importe quelle machine, et dont chaque décision de la recherche s'explique.

Un exemple montre le premier point. La perceuse de Valdrome perce la plaque P-217 en 12 trous. Deux trous à moins de 40 mm l'un de l'autre, percés à trois rangs d'écart au plus, chauffent la tôle localement, qui doit refroidir : deux secondes d'attente par paire. Le coût réel n'est plus la longueur, c'est un temps qui dépend de la séquence par fenêtre glissante, ce qu'un modèle qui compte des arêtes ne voit pas. Pour le squelette du chapitre 7 et la règle du chapitre 8, une seule fonction change.

La tournée la plus courte, celle qui fait 633,23 mm, coûte 37,1 secondes : 21,1 s de déplacement, et huit paires percées trop vite, qui ajoutent 16 s d'attente. La meilleure tournée trouvée par la même recherche avec le nouveau coût est plus longue en distance (806,44 mm, 27 % de plus) et plus courte en temps réel (28,9 s, 22 % de moins) : elle ne garde qu'une paire trop rapprochée. Les six recherches rendent la même valeur, ou presque (la pire fait 30,1 s). Le coût était faux, la solution du chapitre 7 était optimale pour lui, et changer la fonction a suffi. C'est ce qu'on gagne à écrire la recherche soi-même.

Choisir

La bonne pratique est souvent de faire les deux : un solveur pour la référence sur les instances qu'il traite, qui sert d'étalon, et pour les décisions où il passe ; une méthode écrite pour le reste, jugée contre cet étalon avec le protocole du chapitre 12. C'est ce parcours.

Faire vivre la décision dans l'entreprise

Un solveur ou une métaheuristique rend une solution. Une entreprise a besoin d'une décision, c'est-à-dire d'une solution que quelqu'un exécute, à qui on peut l'expliquer, et qui tient jusqu'au lendemain. Les paragraphes qui suivent racontent une semaine de Valdrome, la semaine 41, et ce qui s'y passe entre le plan calculé et l'atelier.

D'où viennent les données

Le plan des dix ordres du chapitre 6 s'appuie sur des durées et des échéances. Elles viennent de l'ERP de l'entreprise : les temps standards du bureau des méthodes, qui donnent la durée d'un ordre, et les échéances promises aux clients. Ces données ne sont pas fausses, elles sont approximatives d'une manière biaisée : un temps standard est mesuré dans de bonnes conditions, un ordre réel a des reprises, des attentes de matière, des changements d'équipe. Sur ce genre de données, un plan optimal sur le papier peut être un mauvais plan pour l'atelier.

Le programme mesure la différence. Il tire des durées « réelles » plus longues que les temps standards (de 10 % de moins à 40 % de plus, 15 % de plus en moyenne), et juge trois plans sur 2 000 semaines simulées : l'optimum du papier (17 heures), l'échéance croissante (23 heures), et un plan robuste, cherché en minimisant la moyenne des retards sur un lot de 100 semaines simulées, différent du lot qui juge.

L'optimum du papier, qui n'a que 17 heures de retard avec les temps standards, en a 48,1 heures en moyenne dès que les durées bougent, et 65,1 heures une semaine sur dix. Le plan robuste a 25 heures de retard sur le papier, huit de plus, et 37,6 heures en moyenne : dix heures de mieux, avec un pire cas de 56,7 heures contre 88,1. Il ne fait pas mieux sur le papier, il fait mieux sur l'atelier. Deux enseignements. Le premier : la qualité d'un plan se juge sur les données qu'on aura, pas sur celles qu'on a, ce qui demande de mesurer l'écart entre le standard et le réel, dans l'historique de l'ERP. Le second : le prix d'une donnée fausse est plus grand que celui d'une méthode médiocre. Régler à un pour cent près un recuit sur des durées qui se trompent de quinze pour cent est un travail sans objet.

Ce que la cheffe d'atelier voit en premier

Le solveur rend son plan, 17 heures de retard. La cheffe d'atelier le regarde : « il me fait changer de montage six fois en dix ordres ». Personne n'avait posé la question, au moment de recueillir les données, et pourtant changer de montage coûte deux heures. La contrainte n'était écrite nulle part, et il n'y avait aucun moyen de la connaître sans lui montrer une solution : la première solution est un outil pour révéler le modèle.

Le programme suivant l'ajoute. Chaque ordre exige un montage (A, B ou C) et deux heures s'ajoutent à chaque changement. La recherche est celle du chapitre 7, et une seule fonction change, le calcul du planning. Il affiche ensuite, pour le nouveau plan, ce qui répond à la question suivante : pourquoi cet ordre ?

Le plan du papier, l'un des douze ordres à 17 heures (celui du chapitre 6), coûte 68 heures une fois les réglages comptés, avec six changements de montage ; le meilleur de ces douze ordres en coûte 54, le pire 94 (énumération des 3 628 800 ordres, hors de la page). Le plan de l'atelier, cherché avec le nouveau coût, fait 37 heures, avec trois changements seulement : O9 et O5 sur le montage C, puis O3, O7, O8 et O1 sur le A, puis O4, O2 et O6 sur le B, et O10, du montage C, en dernier. C'est l'unique optimum : la même énumération le confirme.

Le tableau qui suit le plan est l'explication. La dernière colonne donne, pour chaque paire d'ordres voisins, ce que coûterait de les intervertir. La cheffe d'atelier y lit que passer O3 avant O5 ferait perdre 25 heures, et O4 avant O1 15, parce que deux changements de montage s'ajouteraient, alors que deux ordres du même montage se remplacent presque sans effet (O9 et O5 : une heure, O3 et O7 : une heure, O2 et O6 : une heure). Il peut contester un rang en connaissant son prix. Un plan sans cette colonne est une décision à prendre sur parole, et il n'est pas suivi longtemps.

Un solveur absorbe la même contrainte, à un prix différent : en CP-SAT, il faut écrire une variable booléenne par paire d'ordres et une condition de séparation qui inclut le réglage, soit 45 booléens et 90 contraintes conditionnelles. Le modèle rend les mêmes 37 heures, en une seconde environ. La métaheuristique a changé une fonction de six lignes, le solveur a demandé de réécrire le modèle. Aucune des deux voies n'est meilleure par principe : la première est plus souple, la seconde donne une preuve.

Le plan du lendemain

Le plan de 37 heures est retenu. Le lendemain matin, un onzième ordre arrive : O11, 4 heures, échéance 24, montage B. Les deux premiers ordres du plan sont déjà lancés et ne bougent plus. Il faut replanifier. Le plus simple est de tout recalculer. Le résultat peut être très différent du plan de la veille : les opérateurs avaient préparé les gabarits, les matières étaient sorties.

Le programme mesure la stabilité. Il compte, pour un plan, le nombre d'anciens ordres dont le rang a changé (O11 mis à part), et compare cinq plans : l'insertion de O11 à sa meilleure place sans rien déplacer, le recalcul complet, et trois recherches qui ajoutent au coût un poids par ordre déplacé.

Trois lectures. Insérer sans rien bouger donne 61 heures de retard et aucun ordre déplacé. Tout recalculer donne 52 heures, 9 de moins, mais en déplace 5 : c'est le prix de la stabilité, 9 heures de retard pour éviter de toucher 5 ordres. À retards égaux, la recherche ne voit aucune raison d'en déplacer moins : un poids de 1 heure par ordre déplacé retrouve 52 heures de retard avec 4 ordres déplacés seulement, sans rien perdre. Le poids n'est pas un réglage de technicien : c'est ce qu'une heure de désordre coûte à l'atelier, et il se demande à la cheffe d'atelier. À 3 heures par ordre, la recherche préfère ne plus rien bouger, et retombe sur l'insertion minimale à 61 heures.

Reste à dire à la cheffe d'atelier à partir de quel poids le plan ne bouge plus. Le calcul semble se faire sur les deux plans extrêmes.

L'horizon gelé (les deux premiers ordres) est le second outil : ce qui est lancé ne se replanifie pas. Une méthode qui l'ignore propose des plans que l'atelier ne peut pas suivre.

Temps de calcul, maintenance, humain dans la boucle

Trois questions d'ingénierie restent, et aucune n'a de programme.

Le temps de calcul acceptable dépend de qui attend.

Une métaheuristique a cette propriété que le chapitre 8 a fait voir sans la nommer : elle est interruptible. On l'arrête à la seconde voulue, elle rend la meilleure solution vue. Un solveur en nombres entiers a une propriété voisine (une limite de temps, et l'écart à la borne rendu avec la meilleure solution), mais sa première solution peut arriver tard.

La maintenance. Le code qui décide devra être relu, corrigé, porté sur une nouvelle version de la bibliothèque, par quelqu'un qui ne l'a pas écrit. Trois pratiques comptent. Tester avec le protocole de comparaison, réduit : sur les petites instances où l'optimum est connu, la médiane de l'écart doit rester sous un seuil ; si une modification le dégrade, le test le dit. Fixer les graines dans les tests, pour qu'ils soient reproductibles, et les tirer au hasard en production. Écrire le modèle : la décision, les contraintes, la fonction de coût, ce qui a été volontairement laissé de côté. Un modèle est une hypothèse, et une hypothèse non écrite ne se discute pas. Tests et automatisation ont leur chapitre dans le parcours de génie logiciel. Enfin, le plus simple qui tienne : un plus proche voisin suivi d'un 2-opt, sans réglage, est plus facile à reprendre qu'un recuit, et le recuit plus facile qu'un génétique.

L'humain dans la boucle. L'outil propose, la cheffe d'atelier décide. Trois fonctions le rendent possible : verrouiller un ordre à un rang (l'horizon gelé en est un cas), interdire une séquence, et chiffrer une dérogation : « faire passer O10 en tête coûte 24 heures de retard de plus, 61 au lieu de 37, et O9 finit 32 heures après son échéance » (le meilleur plan qui commence par O10, trouvé par énumération des 9! ordres restants). Une cheffe d'atelier qui déroge en connaissant le prix est une cheffe d'atelier qui fait confiance à l'outil. Celle qui ne peut pas déroger le contourne, et l'outil finit par ne plus servir.

La semaine 41, en résumé

Le lundi, le plan des dix ordres sort à 17 heures de retard : l'optimum prouvé, par PuLP et HiGHS comme par CP-SAT. La cheffe d'atelier le lit, et ajoute deux heures pour chaque changement de montage : le plan coûte 68 heures, et le vrai optimum 37. Quand les durées réelles remplacent les temps standards, l'optimum du papier perd 31 heures en moyenne, et un plan un peu moins bon sur le papier en gagne 10. Le mardi, un onzième ordre arrive, et le plan de la veille, recalculé de zéro, déplace cinq ordres ; avec un poids de stabilité, il en déplace quatre pour le même retard, et à 3 heures il n'en déplace aucun, pour 9 heures de plus. Aucun de ces événements n'est un défaut de la méthode : tous relèvent de l'ingénierie.

Les erreurs d'un débutant

Ce qu'on sait faire à la fin du parcours

Un ingénieur qui a suivi le parcours sait, devant une décision de production :

• la modéliser : distinguer la décision, les contraintes et le coût, choisir une représentation qui ne laisse rien passer d'impossible, décider entre contrainte dure et pénalité (chapitre 1) ;
• mesurer la difficulté : compter les solutions, voir l'explosion, et savoir qu'une machine plus rapide ne la contourne pas (chapitre 2) ;
• l'écrire en programme linéaire, et en trouver l'optimum à un sommet ou par un solveur (chapitre 3) ;
• la borner et la résoudre quand elle est petite : relaxation, borne, écart garanti, solveur en nombres entiers, séparation et évaluation (chapitre 4) ;
• choisir le modèle qui convient : des contraintes logiques et leur propagation, un objectif non linéaire et ses optimums locaux, des sous-problèmes que la programmation dynamique range (chapitre 5) ;
• la construire par une règle gloutonne, en sachant ce que la règle sacrifie (chapitre 6) ;
• l'améliorer par recherche locale, écrire un voisinage, compter ses voisins, reconnaître un optimum local (chapitre 7) ;
• en sortir par le hasard (recuit), par la mémoire (tabou), par une population (génétique) ou par des traces (fourmis et GRASP), en réglant en mesurant ;
• comparer honnêtement : graines, trois nombres, budget égal, référence, réglage égal, et dire le cadre (chapitre 12) ;
• choisir entre une méthode écrite et un solveur, et écrire un même problème pour deux d'entre eux ;
• livrer : des données contestées, un plan expliqué, stable, dans le temps que l'atelier accepte, que l'atelier peut corriger.

Ce qu'il ne sait pas encore faire, et qu'il vaut mieux savoir : traiter des objectifs multiples (retards, énergie, stabilité) sans les fondre arbitrairement en un seul nombre ; décider sous incertitude autrement qu'en moyennant des scénarios ; apprendre les paramètres d'un problème à partir de l'historique ; maintenir une solution pendant des années sans que ses hypothèses vieillissent en silence. Ce sont des sujets d'un autre parcours, et ils commencent tous par la même première question : que se passe-t-il vraiment, dans l'atelier ?

Mettre en pratique