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)
相關術語
相關專案
- 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