Open Source Robotics

Una raccolta curata di progetti, strumenti e software di robotica open source di alta qualità per la comunità della robotica.

Job-Shop Scheduling

  • Detto anche: JSSP, JSP, job-shop problem
  • Categoria: Planning & manipulation › Task-level
  • Tag: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning

Un problema di ottimizzazione combinatoria che consiste nell'ordinare operazioni su macchine condivise, in cui ogni job segue il proprio percorso fisso tra le macchine, di solito per minimizzare il tempo fino al completamento di tutti i job (makespan).

Definizione

La schedulazione job-shop (job-shop scheduling) è il problema di decidere quando ogni operazione viene eseguita su un insieme di macchine condivise. Ci sono n job e m macchine. Ogni job è una sequenza di operazioni da eseguire in un ordine dato, e ogni operazione richiede una specifica macchina per un tempo di lavorazione noto. Una macchina può lavorare su una sola operazione alla volta e, nella versione classica, un'operazione non può essere interrotta una volta iniziata. Il compito è scegliere l'ordine delle operazioni su ogni macchina in modo da minimizzare un obiettivo, il più delle volte il makespan, l'istante in cui finisce l'ultimo job. Altri obiettivi sono il ritardo totale rispetto alle date di consegna e il tempo di flusso totale.

Il problema è NP-difficile in generale, e anche istanze piccole possono essere difficili da risolvere con ottimalità dimostrata. Ha parenti stretti che differiscono per il grado di libertà: in un flow shop tutti i job visitano le macchine nello stesso ordine, in un open shop l'ordine delle operazioni all'interno di un job è libero, e in un job shop flessibile ogni operazione può essere eseguita su qualsiasi macchina di un insieme ammesso, quindi il solver deve anche assegnare le macchine. Un modo standard di modellare il problema è il grafo disgiuntivo, in cui archi fissi codificano l'ordine all'interno di ciascun job e coppie di archi non orientati codificano la scelta ancora aperta di quale operazione viene prima su una macchina condivisa.

I metodi di soluzione vanno dalle semplici regole di dispatching, come prima il tempo di lavorazione più breve, ai metodi esatti basati su programmazione lineare intera mista, programmazione a vincoli e branch and bound, fino alle metaeuristiche come la ricerca tabu, il simulated annealing e gli algoritmi genetici. Lavori più recenti addestrano policy di dispatching con l'apprendimento per rinforzo, spesso usando reti neurali su grafi applicate al grafo disgiuntivo. In robotica le formulazioni job-shop compaiono quando più robot, macchine e postazioni di lavoro di una cella devono condividere il tempo: i robot fungono da macchine o da risorse, i compiti diventano operazioni, e la schedulazione risultante viene poi trasformata in piani di moto e programmi per i robot.

Perché è importante

Ogni volta che più robot o macchine si dividono il lavoro con vincoli di precedenza, l'ordine dei compiti determina la produttività e i tempi morti quanto la velocità di ogni singolo robot. Riconoscere un problema di pianificazione come un'istanza di job shop o di job shop flessibile dà accesso a solver maturi, istanze di benchmark e limiti noti, invece di euristiche costruite a mano difficili da valutare.

Applicazioni principali

  • Sequenziamento dei compiti tra più robot e macchine nelle celle di produzione
  • Assegnazione di postazioni di lavoro e attrezzature di fissaggio condivise tra bracci robotici
  • Pianificazione della produzione per linee di lavorazione meccanica, assemblaggio e collaudo
  • Valutazione di pianificatori di compiti, compresi quelli appresi e quelli basati su modelli linguistici, rispetto a schedulazioni ottime
  • Schedulazione di robot mobili che servono più macchine in una fabbrica

In pratica

Una cella di assemblaggio ha due bracci robotici, una macchina CNC e una stazione di fissaggio. Ogni prodotto richiede una sequenza fissa di passi: caricare il grezzo nella CNC, lavorarlo, spostarlo all'attrezzatura di fissaggio e poi inserire due componenti. Un ingegnere modella ogni prodotto come un job e ogni passo come un'operazione legata al robot o alla macchina che la esegue, e aggiunge i tempi di lavorazione misurati sulla linea. Un solver di programmazione a vincoli con variabili di intervallo e vincoli di non sovrapposizione per ogni risorsa restituisce una schedulazione che minimizza il makespan. L'ingegnere verifica poi che la schedulazione sia fisicamente realizzabile, aggiungendo i tempi di spostamento tra le stazioni e regole di esclusione perché i due bracci non siano mai schedulati contemporaneamente nell'area di fissaggio condivisa, e la schedulazione viene trasformata in un programma per ciascun robot.

Idee sbagliate comuni

  • La schedulazione job-shop è la stessa cosa dell'assegnazione dei compiti — l'assegnazione decide chi svolge un compito, mentre la schedulazione job-shop fissa anche l'ordine e i tempi delle operazioni su ogni risorsa condivisa
  • Ogni job visita le macchine nello stesso ordine — questo è un flow shop; in un job shop ogni job ha il proprio percorso
  • Una schedulazione valida è pronta per i robot — il modello classico ignora gli spostamenti, i tempi di attrezzaggio e le collisioni tra robot, a meno che non vengano aggiunti come vincoli ulteriori
  • Le schedulazioni ottime sono sempre fuori portata — i solver di programmazione a vincoli e di programmazione intera mista trovano spesso schedulazioni ottime o quasi ottime per istanze pratiche; dimostrare l'ottimalità è difficile soprattutto per istanze grandi o fortemente vincolate

Chi dovrebbe saperlo

  • Ingegneri di produzione e automazione che progettano celle multirobot
  • Ricercatori di robotica che lavorano su pianificazione dei compiti e coordinamento multirobot
  • Ingegneri di ricerca operativa che sviluppano schedulatori di produzione
  • Sviluppatori di pianificatori basati su modelli linguistici o appresi per robot industriali

Tecnologie correlate

  • Programmazione a vincoli (Constraint Programming)
  • Google OR-Tools CP-SAT
  • Programmazione lineare intera mista (Mixed-Integer Linear Programming)
  • Regole di dispatching (Dispatching Rules)
  • Ricerca tabu (Tabu Search)
  • Schedulazione job-shop flessibile (Flexible Job-Shop Scheduling)

Termini correlati

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

Progetti correlati

  • 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

Video

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

Questo sito richiede JavaScript. Attiva JavaScript per esplorare i nostri progetti di robotica open source.