Les heuristiques constructives

Construire sans revenir

Une décision d'atelier se compose de petits choix : quelle commande lancer, quel trou percer ensuite, dans quelle barre ranger une pièce. La force brute du chapitre 2 essayait tous les enchaînements possibles de ces choix. Une heuristique constructive fait l'inverse : elle en fait un seul, à chaque pas, selon une règle.

Trois ingrédients la décrivent, et chaque règle de ce chapitre n'en change qu'un.

Le lecteur a déjà rencontré cette famille. Le chapitre gloutons et programmation dynamique présente la règle gloutonne : choisir toujours ce qui paraît le mieux sur le moment. On ne la redémontre pas ici. Ce chapitre l'emploie sur les problèmes de Valdrome, et regarde ce qu'elle vaut quand on connaît la réponse.

Le premier cas est celui des commandes du lundi, au chapitre 1 : les deux règles de bon sens de la figure du conteneur sont deux heuristiques constructives. Chacune considère les commandes dans un ordre, garde celle qui tient encore, et ne revient jamais en arrière.

Le programme est court, et les deux règles ne diffèrent que par la clé de tri : l'ordre de considération est toute la règle. La marge décroissante lance C4, C1 et C9 : 97 heures, 13 200 €, à 100 € de l'optimum, soit 0,8 %. La marge par heure lance C8, C1, C9 et C2 : 95 heures, 12 700 €, à 600 € de l'optimum, soit 4,5 %. La règle qui semble la plus raisonnable, celle du rendement, est ici la moins bonne, et rien dans la règle ne permettait de le prévoir. L'optimum, lui, prend C4, C6 et C8 : il a pris C6, que les deux règles avaient écartée, et laissé C1, que les deux avaient prise.

Le plus proche voisin

Sur la plaque P-217, la règle de la cheffe d'atelier s'écrit en une phrase : depuis le dernier trou percé, aller au trou non percé le plus proche. Il reste à dire par quel trou commencer, et ce que l'outil fait de deux trous à égale distance. Par défaut, la règle part du trou le plus proche du départ de l'outil, et départage les égalités par le nom du trou.

Avant de lire ce que la règle donne, mieux vaut mesurer ce qu'on obtient sans elle. La figure ci-dessous reprend la plaque P-217 et son outil, comme au chapitre 1, avec en plus un panneau sous le dessin, « Une règle construit la tournée ». Le lecteur peut d'abord percer les trous dans l'ordre de son choix, en cherchant la tournée la plus courte possible, puis regarder la règle en construire une, pas à pas, et comparer.

Voici la même règle en Python, avec la plaque du chapitre 2 et l'optimum du chapitre 3. Le programme a deux moitiés : la première construit la tournée du premier trou naturel, la seconde lance la règle depuis les douze trous et sert la section « Le point de départ compte ». À l'exécution, les deux résultats s'affichent à la suite.

Le plus proche voisin perce T1, T7, T10, T11, T5, T6, T12, T8, T3, T2, T9 et T4 : 692,06 mm, soit 9,3 % au-dessus de l'optimum de 633,23 mm (la figure arrondit ses longueurs au dixième de millimètre : elle affiche 692,1 et 633,2). Douze petits choix, une milliseconde de calcul, contre les 479 millions d'ordres de la force brute. Sur les cent mille tirages au hasard du chapitre 2, le meilleur était à 6,6 % : la règle fait moins bien que ce tirage, mais avec plus de dix mille fois moins de distances à calculer (1,3 million pour les cent mille tirages, treize distances chacun, contre moins d'une centaine pour la règle).

Le programme montre aussi où se perd le gain. L'outil suit d'abord des petits traits de quelques dizaines de millimètres, tant qu'il reste des trous proches, puis les quatre derniers traits, de T3 à T2, de T2 à T9, de T9 à T4, puis le retour au départ, font 383 mm : plus de la moitié de la tournée, pour quatre trajets sur treize. À T7, la règle hésitait entre T9 et T10, à égale distance : elle a pris T10, T9 est resté, et il a fallu le rattraper à la fin en traversant la plaque.

Dix minutes de machine par semaine pour 300 plaques : ce n'est pas rien, mais c'est peu au regard de ce qu'aurait coûté une recherche de l'optimum. C'est l'arbitrage de toutes les heuristiques : un écart modeste, pour un temps de calcul qui ne pose aucun problème.

Les égalités changent le résultat

Sur la plaque, plusieurs trous sont exactement à la même distance d'un troisième : T9 et T10 sont tous deux à 30 mm de T7, par exemple, parce que les coordonnées tombent sur une grille. La règle ne dit pas lequel choisir, et ce que la règle ne dit pas se décide malgré elle.

Le programme ci-dessus départage par le nom, en comparant les noms comme des chaînes de caractères : « T10 » vient avant « T2 », qui vient avant « T9 ». Départager par le numéro (T2 avant T10) donne une autre tournée, T1, T7, T9, T11, T5, T6, T12, T8, T10, T3, T2, T4, qui mesure 722,57 mm, soit 14,1 % au-dessus de l'optimum. Le seul changement est celui du départage, et l'écart passe de 9,3 % à 14,1 %.

Le point de départ compte

La règle a besoin d'un premier trou. Rien n'oblige à prendre le plus proche du départ, et rien ne dit que ce soit le meilleur choix. La seconde moitié du programme de la section précédente, sous le commentaire « Suite : les douze départs », lance la même règle depuis chacun des douze trous, en gardant le retour au départ de l'outil. Rien à recopier : la plaque, les distances et la règle sont les mêmes.

Les douze tournées vont de 692,06 mm, depuis T1, à 989,84 mm, depuis T2 : de 9 % à 56 % au-dessus de l'optimum, avec une moyenne à 35 %. La règle est la même, la plaque est la même. Le point de départ naturel, le trou le plus proche de l'outil, se trouve être le meilleur des douze, ce qui n'a rien d'une loi : c'est ici un cas favorable. Un trou de départ mal choisi se paie de deux façons. T2, au bout de la plaque, est à 208 mm de l'outil. Puis la règle traverse le centre par des traits de 25 à 54 mm, et arrive à T4 avec pour seul trou restant T3, à l'autre bout de la plaque : de T4 à T3 (183,6 mm), puis le retour au départ (180,6 mm), font 364 mm sur 990, soit 37 % de la tournée. C'est encore le piège du dernier élément.

L'insertion

Le plus proche voisin ne regarde qu'un trou à la fois, et jamais ce qui se passe plus loin dans la tournée. Une autre famille de règles procède autrement : elle garde toujours une boucle complète, et fait grossir cette boucle en y insérant les trous un par un.

Deux règles décident quel trou on insère à chaque pas. La deuxième est moins intuitive.

• L'insertion la moins chère : le trou dont le meilleur surcoût est le plus petit. Elle cherche à ne rien coûter à la boucle.
• L'insertion la plus lointaine : le trou le plus éloigné de la boucle, c'est-à-dire dont la plus courte distance à un point de la boucle est la plus grande. Elle place d'abord les trous qui structurent la tournée, les extrémités de la plaque, et remplit les creux ensuite. L'idée est la même que celle du rangement des grosses pièces avant les petites : ce qui est difficile à placer doit l'être tôt.

Le panneau de la figure de la section précédente propose les deux insertions sous le plus proche voisin. Elles se regardent de la même façon : la boucle se dessine dès le premier pas, avec le départ, puis grossit d'un trou par pas, et la ligne d'explication dit entre quels trous le nouveau est posé, et pour quel surcoût. Voici le même calcul en Python.

L'insertion la moins chère rend 640,29 mm, soit 1,1 % au-dessus de l'optimum. L'insertion la plus lointaine rend 633,23 mm : l'optimum, sur cette plaque. Les deux font nettement mieux que le plus proche voisin, à 9,3 %.

Deux précautions avant de conclure que « l'insertion est meilleure ». D'abord, ce résultat est celui d'une plaque de douze trous, et rien ne le garantit ailleurs : avec un autre premier trou, l'insertion la plus lointaine donne 633,23 mm six fois sur douze, et de 645,65 à 667,03 mm les six autres fois ; l'insertion la moins chère ne le donne que deux fois sur douze. Ensuite, la meilleure des règles n'est pas gratuite : le plus proche voisin compare, au total, 66 candidats sur cette plaque ; une insertion en compare 352, parce qu'elle essaie chaque trou restant à chaque position de la boucle. Le panneau de la figure affiche ces nombres à la fin de la construction. La qualité se paie en calcul, à un tarif qui reste très raisonnable : les 352 comparaisons se font en une fraction de milliseconde.

La découpe : First Fit Decreasing

Le deuxième problème de Valdrome est celui des barres de 6 000 mm et des vingt pièces à en tirer. Le chapitre 3 a fourni la borne (5 barres) et l'optimum (5 barres), et une règle simple à 6 barres. Voici cette règle, avec son nom.

Pourquoi le sens décroissant. Une longue pièce tient dans peu de barres, celles qui sont presque vides ; une courte tient presque partout. Ranger d'abord les longues, c'est régler les cas difficiles quand il reste de la place, et garder les pièces courtes pour boucher les trous. À l'inverse, des pièces courtes rangées d'abord remplissent les barres en s'y serrant sans nécessité, et la pièce longue qui arrive à la fin ouvre une barre à elle seule.

Le tableau du haut est instructif : six barres, partout. Le plan de découpe dans l'ordre du plan, l'ordre décroissant, l'ordre croissant, avec First Fit comme avec Best Fit (la barre la plus pleine où la pièce tient) : les six combinaisons rendent la même réponse. Sur ces vingt pièces, le sens du tri ne change rien, et le choix de la barre non plus. Ce n'est pas vrai en général : l'exercice « la découpe qui range les pièces dans le mauvais sens » construit des cas où le sens décide d'une barre.

Le détail de FFD montre ce qui ne va pas. Cinq barres sont remplies à 5 530 mm au moins, et la sixième ne porte que deux petites pièces, 620 et 590 mm : 1 210 mm de pièces dans une barre de 6 000. La borne du chapitre 3 dit qu'il faut au moins 5 barres, et un solveur en a trouvé une solution : l'écart d'une barre est le dernier élément, encore une fois. Les pièces arrivent de la plus longue à la plus courte, et les dernières, les plus courtes, ne peuvent plus boucher aucun trou des barres déjà pleines. Au total, 6 500 mm sont libres, répartis en cinq petits jeux et une barre presque vide, alors qu'une solution à cinq barres n'en laisse que 500. La règle a rangé chaque pièce au mieux du moment, et l'ensemble n'est pas au mieux.

L'ordonnancement : la règle dépend de l'objectif

Troisième problème : un centre d'usinage traite un ordre de fabrication à la fois, et dix ordres attendent, chacun avec une durée et une échéance. Choisir l'ordre de passage est un problème de construction naturel : à chaque instant où la machine se libère, une règle de priorité désigne l'ordre suivant parmi ceux qui restent. Trois règles se rencontrent partout.

• Durée croissante : le plus court d'abord.
• Échéance croissante : le plus pressé d'abord.
• Marge croissante : échéance moins durée, le plus juste d'abord.

Deux mots servent à juger un ordre de passage. L'instant de fin d'un ordre est l'heure à laquelle la machine le termine, comptée depuis le début, sans pause entre les ordres ; son retard est le temps dont cet instant dépasse l'échéance, ou zéro si l'ordre est à l'heure. Quand les ordres passent dans l'ordre de leur numéro, O9, qui dure 7 heures pour une échéance de 11, finit 37 heures après le début : 26 heures de retard.

Le coût que Valdrome cherche à réduire est la somme des retards. Mais un atelier ne juge pas toujours ainsi : on peut préférer que le plus grand retard soit le plus petit possible, que peu d'ordres soient en retard, ou que les ordres sortent vite en moyenne, ce que mesure la somme des instants de fin (divisée par dix, c'est la fin moyenne que la figure affiche). Chaque règle est bonne pour un de ces objectifs, et pas pour les autres.

La figure suivante est un diagramme de Gantt : une ligne par ordre, sa durée en barre, son échéance en losange. Le lecteur place les ordres un à un, et voit où chacun tomberait avant de le choisir.

Voici les mêmes règles en Python, avec les quatre critères, et le meilleur total de retards obtenu par programmation dynamique.

La lecture se fait colonne par colonne, et c'est ce qui compte.

• Somme des retards. L'échéance croissante fait 23 heures, la durée croissante 42, l'ordre du planning 45, la marge croissante 49, la durée décroissante 110. L'optimum est de 17 heures, atteint par un ordre qu'aucune de ces règles ne construit.
• Plus grand retard. L'échéance croissante est la meilleure de toutes les règles, avec 11 heures, et aucun ordre ne fait moins : c'est une propriété démontrée de cette règle. La durée croissante monte à 17.
• Somme des instants de fin. La durée croissante est la meilleure, avec 179 heures : aucun ordre ne fait moins. L'échéance croissante, avec 250, est très loin derrière.
• Nombre d'ordres en retard. Le meilleur est de 2. La durée croissante et l'échéance croissante en comptent 3, la marge croissante 6.

Ainsi, la durée croissante, qui coûte 42 heures de retard, est la meilleure règle possible pour un autre objectif, la somme des instants de fin : elle sort les petits ordres vite, et laisse peu de temps à attendre. L'échéance croissante, à 23 heures, est la meilleure pour le plus grand retard. Aucune règle ne gagne partout, et aucune ne gagne sur la somme des retards.

L'affectation : la règle gloutonne

Dernier problème : huit opérateurs, huit postes, un poste par opérateur, les temps de la matrice du chapitre 1. Deux règles gloutonnes viennent à l'esprit.

• Par opérateur : les opérateurs passent l'un après l'autre dans un ordre donné, et chacun prend, parmi les postes encore libres, celui où son temps est le plus petit.
• Par case : on considère toutes les cases de la matrice, de la moins chère à la plus chère, et on garde une case si l'opérateur et le poste sont libres.

Les opérateurs servis dans l'ordre 0 à 7 coûtent 125 minutes, soit 32 % au-dessus de l'optimum de 95 ; la règle par case fait 112 minutes, soit 18 % au-dessus. Elle fait mieux ici, et la raison se comprend : elle considère les choix dans un ordre qui a un sens (les plus avantageux d'abord), au lieu de l'ordre arbitraire de la liste des opérateurs.

Le dernier opérateur servi, Hugo, est le meilleur exemple du piège du dernier élément : il se retrouve au poste de soudure en 25 minutes, alors que son meilleur temps est de 10. Et le résultat dépend de façon spectaculaire de l'ordre de passage : sur les 40 320 ordres possibles des opérateurs, la même règle donne de 95 à 141 minutes, et n'atteint l'optimum que pour 2 800 ordres, soit un sur quatorze. Un ordre d'opérateurs choisi au hasard n'a pas de raison d'être bon. L'ordre de considération est le seul levier de la règle, et il compte plus que la règle elle-même.

Ce qu'on gagne, ce qu'on perd

Les cinq problèmes de Valdrome, côte à côte, donnent le bilan.

Ce que ces règles apportent :

• La vitesse. Chaque règle fait au plus quelques dizaines de comparaisons par élément posé. Au total, 66 pour le plus proche voisin sur douze trous, 352 pour une insertion, moins d'une centaine pour les barres. Aucune n'énumère.
• La simplicité. Chaque règle tient en quelques dizaines de lignes au plus, se comprend, se raconte à l'atelier, et se reproduit à chaque exécution. Le calcul n'a besoin d'aucun réglage.
• Souvent pas si loin. Sur ces cinq problèmes, les écarts vont de 0 à 35 % pour neuf lignes du tableau sur dix, et montent à 147 % pour la durée croissante jugée sur la somme des retards, un critère pour lequel aucune des trois règles n'est faite. Pour un problème qui se pose des centaines de fois par jour, c'est une solution acceptable, obtenue sans attendre.
• Une solution de départ. Une tournée à 9,3 % n'est pas la fin de l'histoire : c'est un excellent point de départ pour une méthode qui l'améliore. C'est le sujet du chapitre suivant.

Ce qu'elles font perdre :

• Toute garantie, en général. Sur ces données, on connaît l'écart parce que le chapitre 3 a fourni l'optimum. Sur une instance nouvelle, l'écart d'une règle constructive n'est connu que par une borne, et celle du plus proche voisin sur la plaque, 416,77 mm, laisse un écart garanti de 66 % au plus. La règle peut être bonne ; rien ne le dit à sa place.
• L'indépendance vis-à-vis de détails qui n'ont rien à voir. Le trou de départ, l'ordre des opérateurs, le départage d'une égalité, le sens du tri : chacun peut faire varier le résultat de dizaines de points.
• Le dernier élément. Les derniers choix se font avec ce qui reste, et l'erreur se concentre en fin de construction.
• Toute possibilité de se corriger. Un choix fait au premier pas conditionne tous les autres, et personne ne le remet en cause. Une règle constructive ne trouve jamais mieux que ce que son premier pas permettait.

Les erreurs de débutant

Exercices type

La méthode

1. Écrire ce qu'on optimise, et chercher une règle dont l'ordre de considération est adapté à ce critère.
2. Écrire la règle en entier : le premier élément, l'ordre de considération, la règle de choix, le départage d'une égalité.
3. Fixer les détails dans le code, pour que deux exécutions donnent le même résultat.
4. Mesurer l'écart à l'optimum quand il est connu, à la borne sinon, avec le sens de l'écart dit (« au plus », « au-dessus de »).
5. Faire varier ce qui n'a rien à voir : le point de départ, l'ordre des éléments, le départage, pour voir ce que vaut la règle et non un cas particulier.
6. Regarder la fin de la construction : c'est là que se paient les mauvais choix, et là qu'on repère où la solution est perdue.
7. Garder la solution comme point de départ pour une méthode qui l'améliore.

Synthèse

• Une heuristique constructive bâtit une solution élément par élément, par une règle, sans jamais revenir sur un choix. Elle coûte peu, et ne donne aucune garantie en général.
• L'ordre de considération est toute la règle des gloutons : sur les commandes, la marge décroissante fait 13 200 € et le rendement décroissant 12 700 €, pour un optimum de 13 300 €.
• Le plus proche voisin donne 692,06 mm sur la plaque, 9,3 % au-dessus de l'optimum ; l'insertion la moins chère 640,29 mm (1,1 %), la plus lointaine 633,23 mm.
• Le point de départ, l'ordre des éléments et le départage des égalités font varier le résultat : le plus proche voisin va de 9 % à 56 % selon le premier trou, de 9,3 % à 14,1 % selon le départage.
• First Fit Decreasing range les pièces de la plus longue à la plus courte : 6 barres pour une borne de 5, avec une garantie théorique de 11/9 de l'optimum plus 6/9 de barre.
• Une règle de priorité est adaptée à un objectif : la durée croissante à la somme des instants de fin, l'échéance croissante au plus grand retard, aucune à la somme des retards (23 et 42 heures contre un optimum de 17).
• Une règle gloutonne d'affectation donne de 95 à 141 minutes selon l'ordre de passage des opérateurs.
• Le dernier élément ramasse ce qui reste : l'erreur d'une règle constructive se concentre en fin de construction.
• Ce qu'on gagne : vitesse, simplicité, écart souvent modeste. Ce qu'on perd : la garantie, l'indépendance vis-à-vis des détails, la possibilité de se corriger.

Et ensuite

Ces solutions ont un défaut commun, qu'aucune règle ne peut réparer : elles sont figées. Une tournée à 9,3 % de l'optimum est bien loin d'être perdue, mais la règle qui l'a construite n'a aucun moyen de l'améliorer. Le chapitre suivant, la recherche locale, part de ces solutions construites et les retouche : échanger deux trous, inverser un tronçon, déplacer une pièce, et garder chaque retouche qui raccourcit la tournée. Le plus proche voisin fournit la solution de départ, et un petit changement à la fois fait le reste. Pour situer les écarts de ce chapitre, on garde en tête les bornes du chapitre bornes et programmation linéaire, et pour l'ordre de grandeur de ce qu'une méthode exacte coûterait, celui sur l'explosion combinatoire.