Ziheng Zhang (ズィヘン・チャン) 氏らは10月15日(現地時間)、学術論文公開サイトarXiv cs.LGに、フレキシブルジョブショップスケジューリング問題の解決を目指す新たな学習手法「BOLT」に関する研究を発表した。BOLTは、時間遅延と資源結合型輸送が伴う複雑な生産環境において、ボトルネックを考慮した下限値の導出に基づき、スケジューリングの最適化を図る。同手法は、生産完了までの時間（メイクスパン）を大幅に短縮する可能性を示している。
フレキシブルジョブショップスケジューリングでは、限られた車両フリートがステーション間でジョブを移動させるため、スケジューリングが輸送待ち時間を決定し、資源結合型となる。BOLTは、このような輸送結合型スケジューリングに対応するバウンド指向学習手法である。これは、チェーン、機械能力、フリート能力の緩和から下限値を構築する。この下限値は終了時にメイクスパンと等しくなるため、段階的な変化が報酬となり、メイクスパンから定数を引いた値に合計される。
この手法は、到達可能なメイクスパンを超えることがないため、候補となるバウンドの増加はメイクスパンフロアの確実な上昇を意味し、ポリシーはこれを「価格」として読み取る。ルートバウンドは、ソルバーを使用せずに完了したスケジュールの最適性ギャップを証明する。業界動機付けの10モジュールプレハブ建設の事例において、積載移動がフリート時間の少なくとも66%を占める全てのテストセルで、明示的な輸送結合が輸送ペナルティポリシーを上回る結果を示した。5つのzero-shot 50モジュールおよび80モジュール生産バッチ全体で、BOLTは4つのバッチで最良のディスパッチングルールペアを上回り、長距離移動を伴う3つのバッチではペナルティポリシーを上回った。
3車両の80モジュールバッチでは、BOLTの平均メイクスパンが最良ペアより13.0%低く、平均34%の証明済みギャップを持つ1時間予算の制約プログラミングソルバーより4.2%低い結果となった。BOLTは1つのプロセッサコアでイベントごとに2.3〜5.9ミリ秒で決定を下し、数秒で障害を再計画できると論文は述べている。
参考: arXiv cs.LG — 2026年10月19日 13:00 (JST)
原文ハイライト"the penalty policy on the three with long moves"