Job-Shop Scheduling
- 別名: JSSP, JSP, job-shop problem
- カテゴリ: Planning & manipulation › Task-level
- タグ: scheduling, combinatorial-optimization, multi-robot, manufacturing, task-planning
各ジョブがそれぞれ固定された機械の経路をたどる中で、共有される機械上の作業の順序を決める組合せ最適化問題。通常はすべてのジョブが終わるまでの時間(メイクスパン)を最小化する。
定義
ジョブショップスケジューリング(job-shop scheduling)は、共有される機械の集合の上で、各作業をいつ実行するかを決める問題である。n 個のジョブと m 台の機械がある。各ジョブは決められた順序で行わなければならない作業の列であり、各作業は特定の 1 台の機械を既知の処理時間だけ必要とする。機械は一度に 1 つの作業しか処理できず、古典的な版では作業はいったん始めると中断できない。課題は、目的関数を最小化するように各機械上の作業の順序を選ぶことであり、最も多いのは最後のジョブが終わる時刻であるメイクスパン(makespan)である。ほかの目的関数には、納期に対する総納期遅れや総フロータイムがある。
この問題は一般に NP 困難(NP-hard)であり、小さなインスタンスでさえ最適性を証明できるまで解くのが難しいことがある。自由度の違いによって近い親戚の問題がある。フローショップ(flow shop)ではすべてのジョブが同じ順序で機械を訪れ、オープンショップ(open shop)ではジョブ内の作業の順序が自由であり、フレキシブルジョブショップ(flexible job shop)では各作業が許可された機械の集合のどれでも実行できるため、ソルバーは機械の割り当ても行わなければならない。この問題をモデル化する標準的な方法は選言グラフであり、固定された弧が各ジョブ内の順序を表し、無向の弧の対が、共有される機械でどの作業を先に行うかというまだ決まっていない選択を表す。
解法は、最短処理時間優先のような単純なディスパッチングルール(dispatching rules)から、混合整数計画、制約プログラミング、分枝限定法に基づく厳密解法、そしてタブーサーチ、焼きなまし法、遺伝的アルゴリズムなどのメタヒューリスティクスまで幅広い。より最近の研究では、強化学習でディスパッチングの方策を訓練し、多くの場合、選言グラフ上でグラフニューラルネットワークを用いる。ロボティクスでは、セル内の複数のロボット、機械、作業ステーションが時間を共有しなければならないときにジョブショップの定式化が現れる。ロボットは機械やリソースとして振る舞い、タスクは作業となり、得られたスケジュールはその後、動作計画とロボットプログラムに変換される。
重要な理由
複数のロボットや機械が順序制約のある仕事を分担するときには、作業の順序が、どの 1 台のロボットの速さにも劣らずスループットと待ち時間を左右する。計画問題をジョブショップやフレキシブルジョブショップのインスタンスとして認識すれば、評価しにくい手作りのヒューリスティクスではなく、成熟したソルバー、ベンチマークのインスタンス、既知の上下界を利用できる。
主な用途
- 製造セルにおける複数のロボットと機械にまたがる作業の順序付け
- 複数のロボットアームの間での共有作業ステーションと治具の割り当て
- 機械加工、組立、試験のラインの生産計画
- 学習型や言語モデルによるプランナーを含むタスクプランナーの、最適スケジュールに対するベンチマーク評価
- 工場内の複数の機械に対応する移動ロボットのスケジューリング
実際の使われ方
ある組立セルには、2 台のロボットアーム、1 台の CNC 工作機械、1 つの治具ステーションがある。各製品には決まった手順の列が必要である。素材を CNC 工作機械に載せ、加工し、治具へ移し、2 つの部品を挿入する。エンジニアは各製品をジョブとして、各手順をそれを行うロボットや機械に結び付いた作業としてモデル化し、ラインで測定した処理時間を加える。区間変数とリソースごとの重なり禁止制約を用いる制約プログラミングのソルバーが、メイクスパンを最小化するスケジュールを返す。続いてエンジニアは、ステーション間の移動時間と立ち入り禁止のルールを加えて、2 台のアームが同時に共有の治具エリアに入るようにスケジュールされることがないようにし、スケジュールが物理的に実行可能かを確認する。そしてスケジュールは各ロボットのプログラムに変換される。
よくある誤解
- ジョブショップスケジューリングはタスク割り当てと同じである — 割り当ては誰が作業を行うかを決めるが、ジョブショップスケジューリングは各共有リソース上の作業の順序とタイミングも確定させる
- すべてのジョブが同じ順序で機械を訪れる — それはフローショップであり、ジョブショップでは各ジョブが独自の経路をもつ
- 有効なスケジュールはそのままロボットに使える — 古典的なモデルは、追加の制約として加えない限り、ロボット間の移動、段取り、衝突を無視する
- 最適なスケジュールには常に手が届かない — 制約プログラミングや混合整数のソルバーは、実用的なインスタンスでは最適またはそれに近いスケジュールをしばしば見つける。最適性の証明が難しいのは主に大規模なインスタンスや制約の厳しいインスタンスである
知っておくべき人
- マルチロボットのセルを設計する製造・自動化エンジニア
- タスク計画とマルチロボット協調に取り組むロボティクスの研究者
- 生産スケジューラーを構築するオペレーションズリサーチのエンジニア
- 産業用ロボット向けの言語モデルによるプランナーや学習型プランナーの開発者
関連技術
- 制約プログラミング(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