Recherche opérationnelle : cellule robotisée job-shop

Ce que c’est

Cinq bras robotisés au plus fort du projet, des convoyeurs, six types de pièces, et l’ordre de passage à décider à chaque lot.

Ce qui était dur

Le plan doit piloter des bras qui bougent vraiment, sur un lot que la machine découvre au moment de le regarder.

Ce que ça prouve

Le gain se joue sur le chemin que prend chaque pièce, pas sur la durée des opérations. C’est l’inverse de ce que l’énoncé laissait attendre.

Projet mené seul, sur du matériel réel, dans le cadre du bloc recherche opérationnelle du cycle ingénieur. 5semainesproductionCinq semaines de travail, seul du début à la fin, de la caméra au pilotage des bras., encadrement par points d’avancement périodiques. Évaluation par démonstration sur un lot disposé au hasard : le cycle est allé à son terme.

Pendant quatre semaines, j’ai piloté 5brasproductionCinq vrais robots, chacun sa tâche, et un seul logiciel pour faire circuler les pièces sans collision, de la détection à la dépose. en parallèle, chacun avec son programme, ses positions, son ordre de passage et son usinage propres : toute une chaîne de fabrication miniature, de la détection des pièces à la dépose finale. Les mesures rejouées plus bas portent sur la configuration livrée en fin de projet, où trois de ces bras restaient en service.

Une cellule qui découvre son lot

Une cellule de production miniature. Des bras robotisés reliés par des convoyeurs, un bac de pièces au départ, deux postes de traitement. Le lot mélange 6types de piècesproductionDeux formes fois trois couleurs : six pièces différentes que la caméra distingue toute seule avant de décider quoi en faire. : deux formes croisées avec trois couleurs, chacune avec son temps d’usinage, et chacune ne passe pas par les mêmes postes.

La question est un problème d’ordonnancement classique dans son énoncé : dans quel ordre lâcher les pièces pour que le lot entier soit terminé au plus tôt ?

Rien n’est déclaré, tout est vu

La charge change à chaque cycle. Les postes que traverse un type de pièce sont tirés au sort au lancement du lot. Une pièce peut passer par les deux postes, un seul, ou aucun. L’ordonnanceur ne résout donc jamais deux fois le même problème, et doit s’adapter à une instance qu’il découvre.

Le lot n’est pas déclaré, il est vu. Aucune saisie : un bras observe le bac, et la vision compte les pièces par forme et par couleur. Ce que le système croit avoir sur le tapis est le résultat d’une détection, avec ce que cela suppose de sensibilité à l’éclairage.

Tout est distribué et asynchrone. Chaque bras est un processus indépendant qui ne partage aucune mémoire avec les autres. Ils se coordonnent par messages, et chacun doit rester correct si un voisin tarde, redémarre ou rate une prise.

Des bras qui se parlent

Cellule robotisée et ordonnanceur

Une ligne : la pièce défile devant tous les bras

1. Le bac de pièces

   posées au hasard, rien n’est saisi à la main

2. le bras source se place et photographie

   Vision

   compte les pièces par forme et par couleur

   six types possibles

3. la liste des pièces du lot

   Ordonnanceur

   calcule dans quel ordre lâcher les pièces

   Les postes à traverser sont tirés au sort

   par type de pièce, à chaque lot : le problème change à chaque cycle

4. l’ordre de passage

   Bras source

   lâche les pièces sur le convoyeur, une à une, dans cet ordre

5. le convoyeur emmène la pièce devant le bras 2

   Bras 2

   l’usine, ou la laisse passer

   Chaque bras choisit, ou ne fait rien

   la pièce défile devant les quatre bras dans l’ordre

   elle peut être usinée par un seul, par plusieurs, ou par aucun

6. le convoyeur continue

   Bras 3

   l’usine, ou la laisse passer

7. le convoyeur continue

   Bras 4

   l’usine, ou la laisse passer

8. le convoyeur continue

   Bras 5

   l’usine, ou la laisse passer

9. fin de ligne

   Sortie du lot

   Les temps observés remontent à l’ordonnanceur

   transits et usinages chronométrés, lissés, réutilisés au lot suivant

Un nœud unique, paramétré par identité. Le même programme tourne sur tous les bras ; son rôle, ses voisins, ses positions et son espace de travail sont dérivés de son identifiant au démarrage. Ajouter un poste ne demande pas d’écrire un nouveau programme.

Une couche de messagerie publication-abonnement porte les commandes, les états, les demandes de prise et l’arrêt d’urgence global. Chaque nœud publie un testament : si son processus meurt, les autres le voient passer hors ligne sans attendre un délai de garde.

Un module d’ordonnancement séparé du pilotage. Il ne connaît ni bras, ni convoyeur, ni caméra. Il reçoit une liste de tâches et des temps de transit, et rend un ordre. C’est cette séparation qui a permis, bien plus tard, de le rejouer entièrement hors de la cellule. Sans elle, rien de ce qui suit n’aurait été mesurable.

Une boucle de métriques chronomètre les temps de service et de transit observés et les lisse en continu, pour que le plan suivant s’appuie sur le comportement réel de la ligne plutôt que sur des valeurs figées.

artefact reproductible

Cellule distribuée réelle : des bras coordonnés par messagerie, détection par vision, capteurs de passage, convoyeurs, et reprise sur échec de préhension.

Renoncer à la finesse théorique

Admettre par disponibilité plutôt que par créneau. Le plan calcule, pour chaque pièce, l’instant idéal de lâcher, celui qui la fait arriver juste quand le poste suivant se libère. Le protocole retenu ne s’en sert pas : un bras demande, le poste accepte s’il est libre, sinon il refuse et la demande est retentée.

C’est un renoncement assumé à la finesse théorique, et il tient à une propriété du terrain : sur une prise ratée, une pièce mal détectée ou un convoyeur qui patine, un créneau réservé devient faux immédiatement, et tout le plan aval avec lui. La disponibilité constatée, elle, reste vraie par construction. J’ai préféré un protocole qui ne ment jamais à un protocole qui optimise tant que rien ne dérape.

Lisser les temps observés au lieu de les figer. Les temps de service et de transit sont réestimés en continu à partir de ce que la ligne fait réellement. Le prix est décrit plus bas : le lissage démarre sur des valeurs posées à la main, et le dispositif ne conserve aucune trace des observations.

Fabriquer la difficulté au lieu de l’attendre. Le tirage des postes traversés à chaque cycle est délibéré : sans lui, un lot ressemble au précédent et l’ordonnanceur n’a rien à faire. C’est ce choix qui a fait exister le problème, et, on le verra, c’est aussi lui qui porte tout le gain.

arbitrage documenté

Admission par disponibilité plutôt que par fenêtre temporelle : un poste accepte une pièce quand il est libre, sans négocier de créneau.

contrainte tenue

Charge variable imposée à chaque cycle : les postes traversés sont tirés au sort par type de pièce, ce qui change l’instance du problème d’un cycle à l’autre.

Ce que l’ordonnancement rapporte

La cellule fonctionne de bout en bout. Ce n’est pas le résultat qui vaut d’être publié : une ligne qui tourne est une condition d’entrée, pas une conclusion. Le résultat, c’est ce que donne le module d’ordonnancement quand on le rejoue.

Tout ce qui suit est simulé. Le module tourne sans matériel, et ne dépend que de sa configuration et du fichier de temps. Je l’ai donc exécuté tel quel, hors de la cellule, sur des charges tirées comme le fait le cycle réel, en comparant chaque stratégie à l’optimum exact obtenu en énumérant les 720ordres possiblessimulationPermutations d’un lot complet : 720 ordres possibles (simulation). d’un lot complet. Ces chiffres comparent des stratégies entre elles sous un modèle commun. Aucun n’est un temps mesuré sur la ligne.

Une méthode rapide suffit, l’énumération exhaustive ne sert à rien. Essayer tous les ordres possibles garantit le meilleur, mais leur nombre explose avec la taille du lot. Une méthode rapide trouve pourtant le même ordre 798sur 798 lots testéssimulationPour organiser une production, on peut essayer tous les ordres possibles et garder le meilleur, mais le nombre d’ordres explose avec la taille du lot. Une méthode rapide donne ici exactement le même résultat que la recherche exhaustive, sur la totalité des cas testés., sans jamais rien perdre. Or l’ordonnanceur bascule sur l’énumération complète dès que le lot est petit, précisément pour garantir cet optimum : il paie un temps de calcul qui explose pour un résultat qu’il avait déjà.

Une des stratégies offertes à l’opérateur est nuisible. L’interface propose trois méthodes. L’une d’elles, présentée comme une heuristique adaptée au job-shop, termine 54,43% de temps en tropsimulationTemps perdu par la stratégie que l’interface recommandait : 54,43 % de temps en trop (simulation, n = 798). en médiane et n’atteint l’optimum sur 0tirage sur 798simulationTirages où la stratégie hybride atteint l’optimum : 0 tirage sur 798 (simulation, n = 798).. C’est moins bon que de ne rien ordonnancer du tout : lâcher les pièces dans l’ordre où elles se présentent coûte 17,13% au-dessus de l’optimum exactsimulationÉcart médian de l’ordre d’arrivée à l’optimum : 17,13 % au-dessus de l’optimum exact (simulation, n = 798). en médiane. Personne ne pouvait le savoir, parce que rien ne comparait jamais deux méthodes.

Le levier n’est pas là où le sujet le supposait. L’énoncé oriente vers les durées d’usinage : des pièces différentes, des temps différents, un ordre à trouver. Or les faire varier ne change que 0,68%simulationMoins d’un pour cent : c’est la piste que l’énoncé du sujet désignait, et elle ne rapporte presque rien. Soixante fois moins que le trajet des pièces.. Faire varier le trajet des pièces, lui, en change 40,23%simulationSur un même lot, le pire ordre de passage prend quarante pour cent de temps de plus que le meilleur. C’est ce que l’ordonnancement va chercher., et jusqu’à 245,09%simulationMarge d’optimisation maximale observée : 245,09 % (simulation, n = 1500). dans le pire cas. Soixante fois plus.

La raison est mesurable : un poste passe 93,2% du tempssimulationSur cent secondes d’occupation d’un poste, plus de quatre-vingt-dix sont de la prise, du déplacement et de la dépose. Accélérer l’usinage ne peut donc rien changer au temps total : c’est le trajet des pièces qu’il faut optimiser. à manipuler la pièce, pas à l’usiner. Accélérer l’usinage ne peut donc pas déplacer un temps total. Ce qui le déplace, c’est de déséquilibrer les deux postes, et c’est le trajet des pièces qui le fait.

mesure

Comparaison simulée des stratégies d’ordonnancement contre l’optimum exact, reproductible sans matériel.

Le chiffre affiché qui ne veut rien dire

Le temps total annoncé à l’opérateur ne dépend pas de l’ordre calculé. En fin de planification, le cycle affiche un temps estimé accompagné du nom de la méthode choisie. Ce nombre est obtenu en sommant des contributions par pièce dans deux accumulateurs, et l’addition est commutative. Recalculé sur les 720ordres possiblessimulationPermutations d’un lot complet : 720 ordres possibles (simulation). d’un lot complet, il prend 1valeursimulationValeurs distinctes du makespan affiché sur toutes les permutations : 1 valeur (simulation).. Quelle que soit la méthode, l’écran affiche le même nombre. L’impossibilité est structurelle.

Le temps réel a été mesuré, mais pas conservé. La ligne chronomètre la durée effective du lot et l’affiche en fin de cycle, mais rien ne l’écrit : ni journal, ni fichier. C’est la différence entre ne pas avoir mesuré et avoir mesuré sans conserver, et c’est la seconde qui s’applique.

Les temps de service ne sont pas des mesures au sens strict. Le fichier qui les porte résulte d’un lissage démarré sur des valeurs posées à la main, sans effectif, sans date, sans dispersion. Toutes les simulations de cette page en héritent : elles sont cohérentes entre elles, pas étalonnées sur le réel.

Le tirage de charge n’est pas reproductible. Il prend l’horloge comme graine là où la fonction prévue pour cet usage accepte une graine explicite. Deux cycles ne peuvent donc pas être rejoués à l’identique, ce qui est exactement ce qu’il aurait fallu pour comparer deux stratégies sur la ligne.

L’usinage n’existe pas : les postes attendent une durée programmée, et les temps par type sont des constantes choisies. Et rien n’est testable sans le matériel, puisque tous les scripts du dossier de tests ouvrent une connexion à un bras. Ce sont des outils de mise en service, pas des tests, alors que le module d’ordonnancement était parfaitement testable hors ligne, comme cette page le démontre.

Si je recommençais

Je ferais échouer un chiffre qui ne peut pas être juste. Le temps affiché à l’opérateur ne dépend pas de l’ordre, et personne ne l’a vu, moi le premier, pendant tout le projet. Pas par négligence : parce que le nombre était plausible. Il avait le bon ordre de grandeur, il variait quand le lot changeait, il portait le nom de la méthode. Rien dans son apparence ne signalait qu’il était indifférent à la seule chose qu’il prétendait évaluer.

C’est le pire genre de défaut, parce qu’il ne casse rien : un plantage se remarque, un chiffre faux mais crédible s’installe. La parade n’est pas de mieux relire, c’est de rendre l’erreur impossible à ignorer. Une assertion qui compare le temps annoncé sur deux ordres du même lot et refuse de démarrer s’ils sont égaux : trois lignes, sans robot, et le défaut tombait le premier jour.

Je poserais le plancher avant l’optimum. Le projet a construit l’exhaustif avant de vérifier qu’une heuristique ne suffisait pas, et n’a jamais comparé son ordonnancement à son absence. Les deux témoins, ne rien faire et faire le plus simple, coûtaient une demi-journée et répondaient à la question centrale : est-ce que tout cela sert à quelque chose ? Ils auraient aussi sorti bien plus tôt la stratégie nuisible.

Je conserverais ce que je mesure. Une ligne écrite en fin de cycle (lot, méthode, temps estimé, temps réel) et le projet disposerait aujourd’hui d’une comparaison estimation/réalité sur toutes ses exécutions, au lieu d’un souvenir. C’est la mesure qui manquait, et elle était déjà calculée.