Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

技術要約：量子アニーリングを用いた羊毛繊維産業における分散型フレキシブルジョブショップ・スケジューリング問題の解決

問題定義
本論文は、羊毛繊維産業の文脈における分散型フレキシブルジョブショップ・スケジューリング問題（DFJSP）を取り扱う。従来のジョブショップ・スケジューリング問題（JSSP）や標準的なフレキシブル・ジョブショップ・スケジューリング問題（FJSP）とは異なり、DFJSPは地理的に分散した生産拠点を含んでおり、単一の生産オーダー（ジョブ）が異なる工場間で工程を行う必要がある。この特定のユースケースは、実際の羊毛繊維メーカーから派生したものであり、独自の複雑さを導入している。すなわち、生産オーダーが複数の拠点に分散しているだけでなく、単一のジョブ内の個々の生産ステップ（工程）も分散し得るということである。その結果、モデルは標準的な加工時間や機械の制約に加え、異なる工場に位置する機械間の輸送時間も考慮しなければならない。目的は、先行制約を満たし、工程が一度のみ開始されることを保証し、機械の重複を防ぎつつ、メイクスパン（総完了時間）を最小化することである。この問題はNP困難であると特定されており、工場間の輸送時間の導入により、組合せの複雑さが大幅に増大している。

手法
著者らは、拡張されたDFJSPを、D-Wave Advantage System 4.1量子アニーラー（QPU）を用いて解くための二次無制約バイナリ最適化（QUBO）問題として定式化した。

1. QUBO定式化: 問題を、工程 $o$ のジョブ $i$ が時刻 $t$ に機械 $m$ で開始するかどうかを表すバイナリ変数 $x_{i,o,m,t}$ にマッピングする。コスト関数 $H(x)$ は、制約（先行、工程の一回性、重複禁止）に対するペナルティ関数と、メイクスパンを最小化するための目的関数の加重和として構成される。
2. 変数の削減（Variable Pruning）: QPUの物理的限界内で問題サイズを管理するため、著者らは変数の削減を採用している。これには、最小の先行時間と最大メイクスパンの制限に基づき、工程開始時刻の下限と上限を計算し、無効なスケジュールに対応するバイナリ変数を排除するプロセスが含まれる。
3. パラメータの決定: 重要な手法上のステップは、ペナルティ項のためのラグランジュ・パラメータ（$\alpha, \beta, \gamma$）の体系的な計算である。試行錯誤に頼るのではなく、著者らは特定の問題インスタンスの最大可能メイクスパン（$t_{max}$）に基づいて、これらの重みを数学的に導出している。これにより、有効な解のエネルギーが、いかなる無効な解のエネルギーよりも低くなることが保証される。
4. 埋め込みと構成: 論理的なQUBO変数は、チェイン（鎖）を用いたQPUの物理的トポロジー上に埋め込まれる。著者らは、「チェイン強度」（チェイン内の量子ビット間の結合強度）が解の質に与える影響を調査し、システムエネルギーと切断されたチェインの割合の間のトレードオフを分析することで、最適な値を決定している。
5. 比較: 量子アニーリング（QA）の結果は、D-Wave Ocean SDKを用いたシミュレーテッド・アニーリング（SA）と比較検証される。両手法は、50から250個の変数を持つ問題インスタンスでテストされ、さらにベースラインを確立するために、SAはより大きなインスタンス（最大400変数）でもテストされている。

主な貢献
本論文は、主に3つの貢献を述べている。

1. QAを用いた拡張DFJSPモデル: 著者らは、生産オーダーおよび個々の生産ステップの両方が工場間で分散しており、工場間の輸送時間を明示的にモデル化した、拡張されたDFJBJPに量子アニーリングを適用した最初の事例を提示している。
2. 体系的なパラメータ計算: 論文では、試行錯誤的なヒューリスティック手法から脱却し、問題の数学的定式化に基づいてラグランジュ・パラメータおよびQPU構成設定（特にチェイン強度）を決定する方法を詳述している。
3. 経済的および性能評価: 本研究は、産業固有の分散型スケジューリングにおけるQAの使用による速度向上の可能性を評価し、解の質および計算時間を古典的なSAと比較している。

結果

• 解の質: 150変数までの問題インスタンスにおいて、QAは一貫して有効な解（制約違反なし）を生成したが、シミュレーテッド・アニーリング（SA）は一般に、わずかに低いエネルギー（より優れた最適性）を持つ解を返した。問題サイズが200および250変数に増加すると、QAの解は制約違反（それぞれ1つおよび2つの違反）を示し始め、エネルギー値が高くなった。この劣化は、より長いチェインと高いチェイン切断率をもたらす、物理的なQPUグラフへの大規模な論理問題の埋め込みの難易度上昇に起因している。
• メイクスパン: ほとんどのサイズにおけるQAの解は、可能なメイクスパン範囲の下半分に収まっており、実行可能な生産スケジュールであることを示している。しかし、250変数のインスタンスでは、メイクスパンは範囲の上半分となった。
• 計算時間: 小規模な問題インスタンスでは、SAの方が高速な計算時間を実現した。しかし、SAのCPU時間は問題のサイズとともに指数関数的に増加した。対照的に、QAのQPUアクセス時間は、減少（対数的）する割合で増加した。現在のハードウェアはQAによる最大250変数までの問題の埋め込みを制限しているが、この傾向は、より大きなインスタンス（300変数以上に外挿されるもの）に対して、QAがSAに対して大幅な速度優位性を提供する可能性があることを示唆している。

意義と主張
本論文は、現在の量子アニーリング・ハードウェアは、小規模なインスタンスにおける古典的なヒューリスティックと比較して、大規模な問題の埋め込みやグローバルな最小値の達成において課題に直面しているものの、羊毛繊維産業の特定のDFJSPの課題に対して大きな潜在能力を持っていると主張している。著者らは、計算時間と問題サイズの相関関係における有利なスケーリングにより、QAが大規模な分散型スケジューリングのための有望な代替案を提供すると主張している。彼らは、将来のハードウェアの改善（より多くの量子ビット、より優れた接続性、および安定性）が進めば、QAは、約300変数を超える問題インスタンスに対して決定的な速度向上の優位性を提供し、複雑で現実的なマルチファクトリー生産計画のための実行可能なツールとなり得ると結論付けている。本研究は、QAの成功した適用は、慎重な問題の定式化、具体的にはペナルティ重みの数学的導出と埋め込みパラメータの最適化に強く依存することを強調している。