Open Source Robotics

精选高质量开源机器人项目、工具和软件,推动机器人社区发展。

Job-Shop Scheduling

  • 又称: JSSP, JSP, job-shop problem
  • 类别: Planning & manipulation › Task-level
  • 标签: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning

一个在共享机器上安排工序顺序的组合优化问题,其中每个作业都遵循自己固定的机器路线,通常目标是使所有作业完成所需的时间(最大完工时间,makespan)最小。

定义

作业车间调度(job-shop scheduling)是决定每道工序何时在一组共享机器上运行的问题。共有 n 个作业和 m 台机器。每个作业是一串必须按给定顺序完成的工序,每道工序需要一台特定的机器,加工时间已知。一台机器一次只能处理一道工序,并且在经典版本中,工序一旦开始就不能中断。任务是为每台机器选择工序顺序,使某个目标最小化,最常见的是最大完工时间(makespan),即最后一个作业完成的时刻。其他目标包括相对于交货期的总拖期和总流程时间。

该问题一般是 NP-hard 的,即使是很小的实例也可能难以求解到被证明的最优。它有一些近亲问题,区别在于自由度的大小:在流水车间(flow shop)中,每个作业以相同的顺序访问各台机器;在开放车间(open shop)中,作业内的工序顺序是自由的;在柔性作业车间(flexible job shop)中,每道工序可以在一组允许的机器中的任意一台上运行,因此求解器还必须分配机器。对该问题建模的一种标准方法是析取图:其中固定的弧编码每个作业内的顺序,而成对的无向弧编码尚未确定的选择,即在一台共享机器上哪道工序先进行。

求解方法范围很广,从简单的调度规则(dispatching rules),例如最短加工时间优先,到基于混合整数规划、约束规划和分支定界的精确方法,再到禁忌搜索、模拟退火和遗传算法等元启发式方法。较新的工作用强化学习训练调度策略,常常在析取图上使用图神经网络。在机器人学中,当一个工作单元中的多台机器人、机器和工作站必须共享时间时,就会出现作业车间表述:机器人充当机器或资源,任务变成工序,所得的调度随后被转换为运动规划和机器人程序。

为何重要

每当多台机器人或机器在有顺序约束的情况下分担工作时,任务顺序对吞吐量和空闲时间的影响,与任何单台机器人的速度一样大。把一个规划问题识别为作业车间或柔性作业车间实例,就能利用成熟的求解器、基准实例和已知的界,而不必依赖难以评估的手工启发式方法。

主要应用

  • 在制造工作单元中对多台机器人和机器的任务进行排序
  • 在多台机械臂之间分配共享工作站和夹具
  • 机加工、装配和测试产线的生产计划
  • 以最优调度为基准评测任务规划器,包括学习型规划器和语言模型规划器
  • 为服务工厂中多台机器的移动机器人安排调度

实际应用

一个装配工作单元有两台机械臂、一台数控(CNC)机床和一个夹具工位。每个产品都需要一串固定的步骤:把毛坯装入 CNC 机床,进行加工,把它移到夹具上,然后插入两个零件。一名工程师把每个产品建模为一个作业,把每个步骤建模为一道与执行它的机器人或机器绑定的工序,并加入在产线上测得的加工时间。一个使用区间变量和每个资源不重叠约束的约束规划求解器,返回一个使最大完工时间最小的调度。随后,工程师检查该调度在物理上是否可行,加入工位之间的移动时间和禁入规则,使两台机械臂绝不会被同时安排进入共享的夹具区域,最后把调度转换为每台机器人的程序。

常见误解

  • 作业车间调度和任务分配是一回事 — 分配决定由谁执行任务,而作业车间调度还要确定每个共享资源上工序的顺序和时间
  • 每个作业都以相同的顺序访问各台机器 — 那是流水车间;在作业车间中,每个作业都有自己的路线
  • 有效的调度可以直接交给机器人 — 经典模型忽略了机器人之间的移动、准备和碰撞,除非把它们作为额外约束加入
  • 最优调度总是无法得到 — 约束规划和混合整数求解器常常能为实际实例找到最优或接近最优的调度;证明最优性主要在大型或约束很紧的实例上才困难

谁需要了解

  • 设计多机器人工作单元的制造和自动化工程师
  • 研究任务规划和多机器人协调的机器人研究人员
  • 构建生产调度器的运筹学工程师
  • 面向工业机器人的语言模型规划器或学习型规划器的开发者

相关技术

  • 约束规划(Constraint Programming)
  • Google OR-Tools CP-SAT
  • 混合整数线性规划(Mixed-Integer Linear Programming)
  • 调度规则(Dispatching Rules)
  • 禁忌搜索(Tabu Search)
  • 柔性作业车间调度(Flexible Job-Shop Scheduling)

相关术语

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

相关项目

  • 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

视频

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

本网站需要 JavaScript 才能正常运行。请启用 JavaScript 以浏览我们的开源机器人项目。