Open Source Robotics

Eine kuratierte Sammlung hochwertiger Open-Source-Robotikprojekte, Werkzeuge und Software für die Robotik-Community.

Job-Shop Scheduling

  • Auch genannt: JSSP, JSP, job-shop problem
  • Kategorie: Planning & manipulation › Task-level
  • Schlagwörter: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning

Ein kombinatorisches Optimierungsproblem, bei dem Arbeitsgänge auf gemeinsam genutzten Maschinen in eine Reihenfolge gebracht werden, wobei jeder Auftrag seiner eigenen festen Maschinenroute folgt, meist mit dem Ziel, die Zeit bis zur Fertigstellung aller Aufträge (Makespan) zu minimieren.

Definition

Job-Shop-Scheduling (Job-shop scheduling) ist das Problem, zu entscheiden, wann jeder Arbeitsgang auf einer Menge gemeinsam genutzter Maschinen ausgeführt wird. Es gibt n Aufträge und m Maschinen. Jeder Auftrag ist eine Folge von Arbeitsgängen, die in einer vorgegebenen Reihenfolge erledigt werden müssen, und jeder Arbeitsgang benötigt eine bestimmte Maschine für eine bekannte Bearbeitungszeit. Eine Maschine kann jeweils nur einen Arbeitsgang bearbeiten, und in der klassischen Version kann ein Arbeitsgang nach dem Start nicht unterbrochen werden. Die Aufgabe besteht darin, die Reihenfolge der Arbeitsgänge auf jeder Maschine so zu wählen, dass eine Zielfunktion minimiert wird, meist der Makespan, der Zeitpunkt, zu dem der letzte Auftrag fertig ist. Weitere Zielfunktionen sind die Gesamtverspätung gegenüber Fälligkeitsterminen und die Gesamtdurchlaufzeit.

Das Problem ist im Allgemeinen NP-schwer, und selbst kleine Instanzen können schwer bis zur bewiesenen Optimalität zu lösen sein. Es hat nahe Verwandte, die sich darin unterscheiden, wie viel Freiheit besteht: In einem Flow Shop durchläuft jeder Auftrag die Maschinen in derselben Reihenfolge, in einem Open Shop ist die Reihenfolge der Arbeitsgänge innerhalb eines Auftrags frei, und in einem flexiblen Job Shop (flexible job shop) kann jeder Arbeitsgang auf jeder Maschine aus einer zulässigen Menge laufen, sodass der Solver auch die Maschinen zuweisen muss. Eine Standardmethode zur Modellierung des Problems ist der disjunktive Graph, in dem feste Kanten die Reihenfolge innerhalb jedes Auftrags kodieren und Paare ungerichteter Kanten die noch offene Wahl, welcher Arbeitsgang auf einer gemeinsam genutzten Maschine zuerst kommt.

Die Lösungsverfahren reichen von einfachen Prioritätsregeln (dispatching rules), etwa kürzeste Bearbeitungszeit zuerst, über exakte Verfahren auf Basis gemischt-ganzzahliger Programmierung, Constraint-Programmierung und Branch-and-Bound bis zu Metaheuristiken wie Tabusuche, Simulated Annealing und genetischen Algorithmen. Neuere Arbeiten trainieren Prioritätsstrategien mit bestärkendem Lernen, oft mit graphischen neuronalen Netzen über dem disjunktiven Graphen. In der Robotik tauchen Job-Shop-Formulierungen auf, wenn sich mehrere Roboter, Maschinen und Arbeitsstationen in einer Zelle die Zeit teilen müssen: Roboter fungieren als Maschinen oder Ressourcen, Aufgaben werden zu Arbeitsgängen, und der resultierende Ablaufplan wird anschließend in Bewegungspläne und Roboterprogramme umgesetzt.

Warum es wichtig ist

Immer wenn sich mehrere Roboter oder Maschinen Arbeit mit Reihenfolgebedingungen teilen, entscheidet die Reihenfolge der Aufgaben ebenso über Durchsatz und Leerlaufzeit wie die Geschwindigkeit eines einzelnen Roboters. Wer ein Planungsproblem als Instanz eines Job Shops oder flexiblen Job Shops erkennt, erhält Zugang zu ausgereiften Solvern, Benchmark-Instanzen und bekannten Schranken statt handgebauter Heuristiken, die schwer zu bewerten sind.

Wichtige Anwendungen

  • Reihenfolgeplanung von Aufgaben über mehrere Roboter und Maschinen in Fertigungszellen
  • Zuteilung gemeinsam genutzter Arbeitsstationen und Vorrichtungen an Roboterarme
  • Produktionsplanung für Bearbeitungs-, Montage- und Prüflinien
  • Benchmarking von Aufgabenplanern, einschließlich gelernter und sprachmodellbasierter Planer, gegen optimale Ablaufpläne
  • Ablaufplanung für mobile Roboter, die in einer Fabrik mehrere Maschinen bedienen

In der Praxis

Eine Montagezelle hat zwei Roboterarme, eine CNC-Maschine und eine Vorrichtungsstation. Jedes Produkt braucht eine feste Schrittfolge: den Rohling in die CNC-Maschine laden, ihn bearbeiten, ihn zur Vorrichtung bringen und dann zwei Teile einsetzen. Ein Ingenieur modelliert jedes Produkt als Auftrag und jeden Schritt als Arbeitsgang, der an den ausführenden Roboter oder die ausführende Maschine gebunden ist, und ergänzt die an der Linie gemessenen Bearbeitungszeiten. Ein Constraint-Programmierungs-Solver mit Intervallvariablen und No-Overlap-Nebenbedingungen pro Ressource liefert einen Ablaufplan, der den Makespan minimiert. Anschließend prüft der Ingenieur, ob der Ablaufplan physisch durchführbar ist, ergänzt Fahrzeiten zwischen den Stationen und Sperrzonenregeln, damit die beiden Arme nie gleichzeitig in den gemeinsamen Vorrichtungsbereich eingeplant werden, und der Ablaufplan wird in ein Programm für jeden Roboter umgesetzt.

Häufige Missverständnisse

  • Job-Shop-Scheduling ist dasselbe wie Aufgabenzuteilung — die Zuteilung entscheidet, wer eine Aufgabe erledigt, während Job-Shop-Scheduling zusätzlich Reihenfolge und Zeitpunkt der Arbeitsgänge auf jeder gemeinsam genutzten Ressource festlegt
  • Jeder Auftrag durchläuft die Maschinen in derselben Reihenfolge — das ist ein Flow Shop; in einem Job Shop hat jeder Auftrag seine eigene Route
  • Ein gültiger Ablaufplan ist für die Roboter einsatzbereit — das klassische Modell ignoriert Fahrwege, Rüstzeiten und Kollisionen zwischen Robotern, sofern sie nicht als zusätzliche Nebenbedingungen ergänzt werden
  • Optimale Ablaufpläne sind immer unerreichbar — Constraint-Programmierungs- und gemischt-ganzzahlige Solver finden für praktische Instanzen oft optimale oder nahezu optimale Ablaufpläne; die Optimalität zu beweisen ist vor allem bei großen oder stark eingeschränkten Instanzen schwer

Wer das wissen sollte

  • Fertigungs- und Automatisierungsingenieure, die Mehrroboterzellen entwerfen
  • Robotikforschende, die an Aufgabenplanung und Mehrroboterkoordination arbeiten
  • Operations-Research-Ingenieure, die Produktionsplaner entwickeln
  • Entwickler sprachmodellbasierter oder gelernter Planer für Industrieroboter

Verwandte Technologien

  • Constraint-Programmierung (Constraint Programming)
  • Google OR-Tools CP-SAT
  • Gemischt-ganzzahlige lineare Programmierung (Mixed-Integer Linear Programming)
  • Prioritätsregeln (Dispatching Rules)
  • Tabusuche (Tabu Search)
  • Flexibles Job-Shop-Scheduling (Flexible Job-Shop Scheduling)

Verwandte Begriffe

  • Task Planning
  • Mixed-Integer Programming
  • Task and Motion Planning
  • Multi-Agent Path Finding
  • Digital Twin

Verwandte Projekte

  • 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

Videos

  • Operations Research 09D: Job Shop Scheduling Problem: Yong Wang
  • Mod-07 Lec-28 Job shop scheduling -- Gantt chart, Different dispatching rules: nptelhrd

Diese Website benötigt JavaScript. Bitte aktivieren Sie JavaScript, um unsere Open-Source-Robotikprojekte zu erkunden.