Open Source Robotics

Una colección curada de proyectos, herramientas y software de robótica de código abierto de alta calidad.

Job-Shop Scheduling

  • También llamado: JSSP, JSP, job-shop problem
  • Categoría: Planning & manipulation › Task-level
  • Etiquetas: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning

Un problema de optimización combinatoria que consiste en ordenar operaciones en máquinas compartidas, donde cada trabajo sigue su propia ruta fija de máquinas, normalmente para minimizar el tiempo hasta que terminan todos los trabajos (makespan).

Definición

La planificación de talleres (job-shop scheduling) es el problema de decidir cuándo se ejecuta cada operación en un conjunto de máquinas compartidas. Hay n trabajos y m máquinas. Cada trabajo es una secuencia de operaciones que deben realizarse en un orden dado, y cada operación necesita una máquina concreta durante un tiempo de procesamiento conocido. Una máquina solo puede trabajar en una operación a la vez y, en la versión clásica, una operación no puede interrumpirse una vez iniciada. La tarea consiste en elegir el orden de las operaciones en cada máquina de modo que se minimice un objetivo, casi siempre el makespan, el instante en que termina el último trabajo. Otros objetivos son el retraso total respecto a las fechas de entrega y el tiempo de flujo total.

El problema es NP-difícil en general, e incluso instancias pequeñas pueden ser difíciles de resolver con optimalidad demostrada. Tiene parientes cercanos que difieren en cuánta libertad hay: en un flow shop todos los trabajos visitan las máquinas en el mismo orden, en un open shop el orden de las operaciones dentro de un trabajo es libre, y en un job shop flexible cada operación puede ejecutarse en cualquier máquina de un conjunto permitido, por lo que el solver también debe asignar las máquinas. Una forma estándar de modelar el problema es el grafo disyuntivo, en el que arcos fijos codifican el orden dentro de cada trabajo y pares de arcos no dirigidos codifican la elección aún abierta de qué operación va primero en una máquina compartida.

Los métodos de resolución van desde simples reglas de despacho, como el tiempo de procesamiento más corto primero, pasando por métodos exactos basados en programación entera mixta, programación con restricciones y ramificación y acotación, hasta metaheurísticas como la búsqueda tabú, el recocido simulado y los algoritmos genéticos. Trabajos más recientes entrenan políticas de despacho con aprendizaje por refuerzo, a menudo usando redes neuronales de grafos sobre el grafo disyuntivo. En robótica, las formulaciones de job shop aparecen cuando varios robots, máquinas y puestos de trabajo de una celda deben compartir el tiempo: los robots actúan como máquinas o como recursos, las tareas se convierten en operaciones, y el cronograma resultante se transforma después en planes de movimiento y programas de robot.

Por qué importa

Siempre que varios robots o máquinas comparten trabajo con restricciones de orden, el orden de las tareas determina el rendimiento y el tiempo ocioso tanto como la velocidad de cualquier robot individual. Reconocer un problema de planificación como una instancia de job shop o de job shop flexible da acceso a solvers maduros, instancias de referencia y cotas conocidas, en lugar de heurísticas hechas a mano que son difíciles de evaluar.

Aplicaciones clave

  • Secuenciación de tareas entre varios robots y máquinas en celdas de fabricación
  • Asignación de puestos de trabajo y utillajes compartidos entre brazos robóticos
  • Planificación de la producción para líneas de mecanizado, montaje y pruebas
  • Evaluación de planificadores de tareas, incluidos los aprendidos y los basados en modelos de lenguaje, frente a cronogramas óptimos
  • Planificación temporal de robots móviles que atienden varias máquinas en una fábrica

En la práctica

Una celda de montaje tiene dos brazos robóticos, una máquina CNC y una estación de utillaje. Cada producto necesita una secuencia fija de pasos: cargar la pieza en bruto en la CNC, mecanizarla, llevarla al utillaje y después insertar dos piezas. Un ingeniero modela cada producto como un trabajo y cada paso como una operación ligada al robot o la máquina que la realiza, y añade los tiempos de procesamiento medidos en la línea. Un solver de programación con restricciones, con variables de intervalo y restricciones de no solapamiento por recurso, devuelve un cronograma que minimiza el makespan. Después, el ingeniero comprueba que el cronograma es físicamente viable, añadiendo tiempos de desplazamiento entre estaciones y reglas de exclusión para que los dos brazos nunca estén programados a la vez en la zona de utillaje compartida, y el cronograma se convierte en un programa para cada robot.

Ideas erróneas comunes

  • La planificación de talleres es lo mismo que la asignación de tareas — la asignación decide quién hace una tarea, mientras que la planificación de talleres fija además el orden y los tiempos de las operaciones en cada recurso compartido
  • Todos los trabajos visitan las máquinas en el mismo orden — eso es un flow shop; en un job shop cada trabajo tiene su propia ruta
  • Un cronograma válido está listo para los robots — el modelo clásico ignora los desplazamientos, los tiempos de preparación y las colisiones entre robots, a menos que se añadan como restricciones adicionales
  • Los cronogramas óptimos siempre están fuera de alcance — los solvers de programación con restricciones y de programación entera mixta encuentran a menudo cronogramas óptimos o casi óptimos para instancias prácticas; demostrar la optimalidad es difícil sobre todo en las instancias grandes o muy restringidas

Quién debería saberlo

  • Ingenieros de fabricación y automatización que diseñan celdas multirrobot
  • Investigadores en robótica que trabajan en planificación de tareas y coordinación multirrobot
  • Ingenieros de investigación operativa que desarrollan planificadores de producción
  • Desarrolladores de planificadores basados en modelos de lenguaje o aprendidos para robots industriales

Tecnologías relacionadas

  • Programación con restricciones (Constraint Programming)
  • Google OR-Tools CP-SAT
  • Programación lineal entera mixta (Mixed-Integer Linear Programming)
  • Reglas de despacho (Dispatching Rules)
  • Búsqueda tabú (Tabu Search)
  • Planificación de talleres flexible (Flexible Job-Shop Scheduling)

Términos relacionados

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

Proyectos relacionados

  • 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

Vídeos

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

Este sitio web requiere JavaScript. Por favor, habilite JavaScript para explorar nuestros proyectos de robótica.