Job-Shop Scheduling
- Aussi appelé: JSSP, JSP, job-shop problem
- Catégorie: Planning & manipulation › Task-level
- Mots-clés: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning
Un problème d'optimisation combinatoire consistant à ordonner des opérations sur des machines partagées, où chaque travail suit son propre itinéraire fixe de machines, généralement pour minimiser le temps nécessaire pour que tous les travaux soient terminés (makespan).
Définition
L'ordonnancement d'atelier (job-shop scheduling) est le problème qui consiste à décider quand chaque opération s'exécute sur un ensemble de machines partagées. Il y a n travaux et m machines. Chaque travail est une suite d'opérations qui doivent être effectuées dans un ordre donné, et chaque opération nécessite une machine précise pendant une durée de traitement connue. Une machine ne peut traiter qu'une opération à la fois et, dans la version classique, une opération ne peut pas être interrompue une fois commencée. Il s'agit de choisir l'ordre des opérations sur chaque machine de façon à minimiser un objectif, le plus souvent le makespan, l'instant où le dernier travail se termine. D'autres objectifs incluent le retard total par rapport aux dates d'échéance et la durée totale de séjour.
Le problème est NP-difficile en général, et même de petites instances peuvent être difficiles à résoudre jusqu'à une optimalité prouvée. Il a des proches parents qui diffèrent par le degré de liberté : dans un flow shop, chaque travail passe par les machines dans le même ordre ; dans un open shop, l'ordre des opérations au sein d'un travail est libre ; et dans un job shop flexible (flexible job shop), chaque opération peut s'exécuter sur n'importe quelle machine d'un ensemble autorisé, si bien que le solveur doit aussi affecter les machines. Une façon standard de modéliser le problème est le graphe disjonctif, dans lequel des arcs fixes codent l'ordre au sein de chaque travail et des paires d'arcs non orientés codent le choix encore ouvert de l'opération qui passe en premier sur une machine partagée.
Les méthodes de résolution vont de simples règles de priorité (dispatching rules), comme le temps de traitement le plus court en premier, aux métaheuristiques comme la recherche tabou, le recuit simulé et les algorithmes génétiques, en passant par des méthodes exactes fondées sur la programmation en nombres entiers mixtes, la programmation par contraintes et la séparation et évaluation. Des travaux plus récents entraînent des politiques de priorité par apprentissage par renforcement, souvent avec des réseaux de neurones sur graphes appliqués au graphe disjonctif. En robotique, les formulations de type job-shop apparaissent lorsque plusieurs robots, machines et postes de travail d'une cellule doivent se partager le temps : les robots jouent le rôle de machines ou de ressources, les tâches deviennent des opérations, et l'ordonnancement obtenu est ensuite transformé en plans de mouvement et en programmes robot.
Pourquoi c'est important
Chaque fois que plusieurs robots ou machines se partagent un travail soumis à des contraintes d'ordre, l'ordre des tâches détermine le débit et le temps d'inactivité autant que la vitesse de n'importe quel robot pris isolément. Reconnaître un problème de planification comme une instance de job shop ou de job shop flexible donne accès à des solveurs matures, à des instances de référence et à des bornes connues, au lieu d'heuristiques construites à la main et difficiles à évaluer.
Applications principales
- Séquencement des tâches entre plusieurs robots et machines dans les cellules de fabrication
- Affectation de postes de travail et de montages partagés entre bras robotiques
- Planification de la production pour les lignes d'usinage, d'assemblage et de test
- Évaluation comparative de planificateurs de tâches, y compris des planificateurs appris et fondés sur des modèles de langage, par rapport à des ordonnancements optimaux
- Ordonnancement de robots mobiles qui desservent plusieurs machines dans une usine
En pratique
Une cellule d'assemblage comprend deux bras robotiques, une machine CNC et un poste de montage. Chaque produit nécessite une séquence fixe d'étapes : charger le brut dans la machine CNC, l'usiner, le déplacer vers le montage, puis insérer deux pièces. Un ingénieur modélise chaque produit comme un travail et chaque étape comme une opération liée au robot ou à la machine qui l'exécute, et ajoute les durées de traitement mesurées sur la ligne. Un solveur de programmation par contraintes, avec des variables d'intervalle et des contraintes de non-chevauchement par ressource, renvoie un ordonnancement qui minimise le makespan. L'ingénieur vérifie ensuite que l'ordonnancement est physiquement réalisable, en ajoutant les temps de déplacement entre postes et des règles de zones interdites pour que les deux bras ne soient jamais planifiés en même temps dans la zone de montage partagée, puis l'ordonnancement est transformé en programme pour chaque robot.
Idées reçues
- L'ordonnancement d'atelier (job-shop) est la même chose que l'allocation de tâches — l'allocation décide qui effectue une tâche, tandis que l'ordonnancement job-shop fixe aussi l'ordre et les instants des opérations sur chaque ressource partagée
- Chaque travail passe par les machines dans le même ordre — c'est un flow shop ; dans un job shop, chaque travail a son propre itinéraire
- Un ordonnancement valide est prêt pour les robots — le modèle classique ignore les déplacements, les réglages et les collisions entre robots, sauf s'ils sont ajoutés comme contraintes supplémentaires
- Les ordonnancements optimaux sont toujours hors de portée — les solveurs de programmation par contraintes et en nombres entiers mixtes trouvent souvent des ordonnancements optimaux ou quasi optimaux pour des instances pratiques ; prouver l'optimalité est difficile surtout pour les instances grandes ou fortement contraintes
Qui devrait le savoir
- Ingénieurs en fabrication et en automatisation concevant des cellules multi-robots
- Chercheurs en robotique travaillant sur la planification de tâches et la coordination multi-robots
- Ingénieurs en recherche opérationnelle développant des ordonnanceurs de production
- Développeurs de planificateurs fondés sur des modèles de langage ou appris pour robots industriels
Technologies associées
- Programmation par contraintes (Constraint Programming)
- Google OR-Tools CP-SAT
- Programmation linéaire en nombres entiers mixtes (Mixed-Integer Linear Programming)
- Règles de priorité (Dispatching Rules)
- Recherche tabou (Tabu Search)
- Ordonnancement job-shop flexible (Flexible Job-Shop Scheduling)
Termes associés
Projets associés
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
- IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
- X-VLA: Cross-embodiment VLA model with soft-prompted scaling
- Swarm-SLAM: Decentralized collaborative SLAM for robot swarms with bandwidth-aware loop closing
- PlanSys2: The PDDL-based task planning system for ROS 2 — symbolic AI planning on real robots
Vidéos
- Operations Research 09D: Job Shop Scheduling Problem: Yong Wang
- Mod-07 Lec-28 Job shop scheduling -- Gantt chart, Different dispatching rules: nptelhrd