RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

この論文は、複雑な特徴量設計やグラフベースのアーキテクチャに依存せず、最小限の 4 つの特徴量と Transformer 機構を活用した軽量な強化学習フレームワーク「ReSched」を提案し、柔軟ジョブショップスケジューリング問題において既存の手法を上回る性能と高い汎用性を示したことを報告しています。

要約

🏭 物語の舞台：「混乱する巨大な工場」

想像してください。
ある巨大な工場では、数百もの「部品（ジョブ）」を、数十台の「機械（マシン）」で加工する必要があります。

• 部品 A は、機械 1 でも機械 2 でも加工できますが、機械 1 の方が速いです。
• 部品 B は、部品 A が終わってからしか加工できません。
• 機械は一度に 1 つしか作業できません。

**「誰が、どの機械で、いつ作業するか」**を決めるのが「スケジューリング」です。
これが少しのミスでも、全体の完成時間が大幅に遅れてしまい、工場は赤字になります。

これまでの AI は、この問題を解こうとして**「超複雑なメモ帳」**を持っていました。

• 「過去に何があったか」「誰がいつ待っていたか」「過去の履歴」など、20 種類以上の情報を手書きでメモし、それをグラフ（図）として AI に見せていました。
• しかし、メモが多すぎると AI は混乱し、計算も重くなり、新しい工場（異なる問題）に行くと失敗してしまうことがありました。

---

💡 解決策：「RESCHED（リ・スケッド）」という新しい考え

この論文の著者たちは、**「複雑なメモは捨てて、本質だけを見よう！」**と考えました。

1. メモ帳を「4 つの項目」に減らす（状態の簡素化）

これまでの AI は、過去の履歴をすべて覚えていましたが、RESCHED は**「今、必要な情報だけ」に絞りました。
まるで、「今、どの機械が空いているか？」「次の作業はどれくらいかかるか？」**という 4 つの核心だけを見れば、未来のスケジュールは自然に決まる、と気づいたのです。

• アナロジー：
  • 昔の AI： 「昨日の天気、朝の交通量、前のドライバーの気分、過去の事故履歴…」など、100 項目のメモを見ながら「今、右折するか？」を決める運転手。
  • RESCHED： 「今、目の前に信号があるか？」「右折レーンが空いているか？」という4 つのことだけを見て、瞬時に判断するプロのドライバー。
  • これにより、AI の頭（計算リソース）が軽くなり、どんな新しい工場でもすぐに適応できるようになりました。

2. 頭脳を「トランスフォーマー」にアップグレード

AI の頭脳（モデル）を、最新の「トランスフォーマー（Transformer）」という技術にしました。これは、ChatGPT などが使っている、文章の文脈を非常に得意とする技術です。

• 工夫点：

  • 部品同士の関係（O2O）： 「部品 A の後には必ず部品 B が来る」というルールを、回転する位置情報（RoPE）を使って、AI が自然に理解できるようにしました。
  • 機械との関係（O2M）： 「部品」と「機械」の数が圧倒的に違う（部品が 100 個、機械が 10 台など）場合、AI が混乱しないよう、機械の視点からも情報を集める特別な仕組みを作りました。

• アナロジー：

  • 従来の AI は、部品の列を「1 つずつ順番に」見るような、遅い読み手でした。
  • RESCHED は、**「全体を一度にスキャンして、部品と機械の関係を瞬時に把握する」**ような、超高速な読書家です。

---

🏆 結果：なぜこれがすごいのか？

実験の結果、RESCHED は以下の点で素晴らしい成果を上げました。

1. 最強の成績：
   既存の AI や、人間が考えた「経験則（ルール）」よりも、はるかに短時間で完成させるスケジュールを作れました。
2. 汎用性（応用範囲）の広さ：
   • 「柔軟な工場（FJSP）」だけでなく、機械が決まっている「普通の工場（JSSP）」や、流れ作業の「ライン（FFSP）」など、問題の種類が変わっても、同じ AI で対応できました。
   • 特別な調整なしに、小さな工場から巨大な工場まで、サイズが変わってもうまく動きました。
3. 高速さ：
   複雑な計算をしないため、AI がスケジュールを決めるまでの時間が非常に短く、実用的です。

---

🚀 まとめ：「シンプルこそが最強」

この論文が伝えたかったメッセージは、**「AI を賢くするには、複雑なルールや大量のデータを詰め込む必要はない」**ということです。

• 本質を見極める（4 つの要素だけ）
• 強力な頭脳を使う（トランスフォーマー）

この「シンプル × 強力」な組み合わせが、工場の生産効率を劇的に上げ、将来の物流や製造業をよりスマートにする可能性を秘めています。

まるで、「迷い込みやすい複雑な地図」を捨て、「北極星（本質）」だけを見て、どんな道でも最短で駆け抜けるナビゲーターが誕生したようなものです。

技術概要

RESCHED: 変換器ベースのアーキテクチャと簡素化された状態表現によるフレキシブルジョブショップスケジューリングの再考

本論文は、ICLR 2026 にて発表された「RESCHED」と呼ばれる、深層強化学習（DRL）に基づくフレキシブルジョブショップスケジューリング問題（FJSP）の解決フレームワークについて報告しています。既存の手法が抱える複雑な特徴量設計やグラフ偏ったアーキテクチャの限界を克服し、最小限の状態表現と汎用的な変換器（Transformer）アーキテクチャを組み合わせることで、高い性能と汎用性を達成した点が特徴です。

以下に、論文の主要な内容を技術的に要約します。

1. 問題設定：フレキシブルジョブショップスケジューリング問題 (FJSP)

FJSP は、製造業、エッジコンピューティング、物流などにおいて広く応用される組み合わせ最適化問題です。

• 定義: 複数のジョブが、それぞれ一連の操作（オペレーション）の列として構成されています。各操作は、互換性のある複数の機械のいずれかで処理可能であり、処理時間は機械によって異なります。
• 課題: 各操作をどの機械に割り当てるか（割り当て決定）と、各機械上で操作をどの順序で実行するか（順序決定）という、2 つの連動した意思決定を同時に行う必要があります。
• 目的: 全ての操作の完了時間の最大値（メイクスパン）を最小化することです。
• 既存手法の限界: 従来の DRL 手法は、複雑に設計された状態表現（20 種類以上の手動設計された特徴量）や、グラフニューラルネットワーク（GNN）に依存したアーキテクチャを採用しています。これらは計算コストが高く、過剰な特徴量や履歴情報の追跡が学習の一般化性能を阻害する要因となっていました。

2. 手法：RESCHED フレームワーク

RESCHED は、FJSP のマルコフ決定過程（MDP）定式化とモデル設計の両方を再考し、以下の 2 つの主要な革新を導入しています。

2.1 最小限の状態表現 (Minimal State Representation)

既存の手法では、操作の完了時間や機械の空き時間などを履歴から追跡する必要があり、多数の特徴量が必要でした。RESCHED は、サブ問題ベースの視点から MDP を再定義し、状態空間を以下の4 つの必須特徴量に集約しました。

1. 操作の空き時間 (Operation Available Time): 前段の操作が完了する時間（ジョブ内の依存関係）。
2. 機械の空き時間 (Machine Available Time): 直前の操作が完了し、その機械が次に使用可能になる時間。
3. 処理時間 (Duration): 特定の操作を特定の機械で処理する時間。
4. 最小処理時間 (Minimum Duration): 候補となる機械群の中で最も短い処理時間（操作の難易度の下限を示すプロキシ）。

重要な工夫:

• 履歴の排除: 絶対的な時間ではなく、現在のステップにおける「相対的な空き時間」を使用することで、時間の無限増大を防ぎ、一般化性を向上させました。
• グラフ構造の活用: 操作間の依存関係（O2O）や操作 - 機械の接続（O2M）は特徴量ではなく、グラフ構造（エッジ）として明示的にエンコードされます。これにより、冗長な特徴量や履歴追跡を不要にしました。
• マルコフ性: この状態定義により、現在の状態が将来のサブ問題の解空間を一意に決定するため、過去の履歴に依存しないマルコフ性を満たすことが理論的に証明されています。

2.2 タスク特化型変換器アーキテクチャ

従来の GNN ではなく、Transformer をベースとしたデコーダ専用アーキテクチャを採用し、スケジューリングタスクに特化した 3 つの軽量化かつ効果的な改良を加えています。

1. 操作ブランチ（RoPE 付き自己注意）:
   • ジョブ内の操作順序（O2O 依存）をモデル化するために、自己注意メカニズムを使用します。
   • 位置エンコーディングとして**回転位置エンコーディング (RoPE)**を導入し、追加のパラメータなしで相対的な位置関係（ジョブ内の順序）を効率的に学習させます。
2. 機械ブランチ（エッジ特徴量を含むクロス注意）:
   • 操作と機械の相互作用をモデル化するために、クロス注意メカニズムを使用します。
   • 従来の手法では間接的に扱われていた「処理時間（エッジ特徴量）」を、アテンション重みの計算だけでなく、値ベクトル（Value Vector）に直接埋め込むことで、エッジ情報が最終的な表現に直接影響するように設計しました。
3. 自己ベースのクロス注意 (Self-based Cross-attention):
   • 操作数が機械数を大幅に上回る（10 倍以上など）不均衡な構造において、機械ノードが過剰な操作情報に埋もれてしまう問題（情報の希薄化）を解決します。
   • 機械ノードが自身の表現にも注意を向ける（自己接続）ことで、重要な機械レベルの情報を保持しつつ、操作からの情報を適切に集約します。

2.3 意思決定と報酬

• 行動: 実行可能な「操作 - 機械ペア」を選択すること。
• 報酬: 現在の状態から次の状態への移行における、推定された下限メイクスパンの減少量（負の差分）を報酬として使用します。これにより、学習が効率的に行われます。
• 最適化: 実装の簡素化と状態・アーキテクチャ設計の影響を明確にするため、Actor-Critic ではなく単純な REINFORCE アルゴリズムを使用しています（PPO 版の実装も検証済み）。

3. 実験結果

3.1 FJSP における性能

• ベンチマーク: SD1, SD2（合成データ）、Brandimarte, Hurink（標準ベンチマーク）で評価。
• 結果: 既存の古典的な優先度割り当てルール（PDRs）や、最先端の DRL 手法（HGNN, DANIEL, DOAGNN など）をすべて上回る性能を達成しました。
• 一般化性能: 訓練データよりもはるかに大きな問題サイズ（例：訓練 10x10、テスト 40x10）や、異なる分布のベンチマークデータに対しても、高い汎化性能を示しました。特に、OR-Tools（CP ソルバー）と比較しても、推論時間が極めて短く、かつ解の質が同等以上であることが確認されました。

3.2 他スケジューリング問題への汎用性

• JSSP (Job Shop Scheduling Problem): 機械の割り当てが固定された問題。訓練サイズ 10x10 のみで学習し、Taillard ベンチマーク（最大 100x20）でテストしたところ、JSSP 特化型の DRL 手法（L2D, RL-GNN）を上回る性能を示しました。
• FFSP (Flexible Flow Shop Scheduling Problem): 共通の工程フローを持つ問題。MatNet などの手法と比較し、単一のモデルで異なるサイズ（20, 50, 100）に対応可能であることを示しました。

3.3 考察とアブレーション

• 4 つの特徴量に絞った状態表現や、RoPE、エッジ特徴量の直接埋め込み、自己ベースのクロス注意など、各コンポーネントが性能向上に寄与していることがアブレーション研究で確認されました。
• 既存の手法（DANIEL など）から特徴量を大幅に削減しても性能が維持・向上することから、多くの手動設計特徴量が冗長であったことが示唆されました。

4. 主要な貢献と意義

1. 最小限かつ十分な状態表現の確立: FJSP において、4 つの特徴量とグラフ構造のみで最適な意思決定が可能であることを示し、複雑な特徴工学の必要性を排除しました。
2. スケジューリング特化型 Transformer の提案: 操作と機械の不均衡や、エッジ特徴量の重要性を考慮した、双ブランチ構造の Transformer アーキテクチャを設計しました。
3. 高い汎用性と SOTA 性能: 単一のフレームワークで FJSP、JSSP、FFSP に対応し、既存の DRL ベンチマークや古典的ヒューリスティック、CP ソルバーを凌駕する性能を達成しました。
4. 実用性: 推論時間が短く、大規模問題や動的な環境への適用可能性が高く、実世界のスケジューリングシステムへの導入が期待されます。

結論

RESCHED は、深層強化学習を用いたスケジューリング問題解決において、「複雑な特徴量とグラフ構造への依存」から「最小限の状態と汎用的な変換器アーキテクチャ」へのパラダイムシフトを提案しました。このアプローチは、計算コストを削減しつつ、より高い一般化性能と解の質を実現しており、将来のスケジューリング研究および実装における重要な基盤となると考えられます。