arXiv (AI)AI
深層強化学習とTransformerを用いたオープンショップスケジューリング問題の解法
A Deep Reinforcement Learning (DRL)-Based Transformer Method for Solving the Open Shop Scheduling Problem
この記事についてAIに質問する →
日本語要約青い用語にマウスを合わせると解説が表示されます
オープンショップスケジューリング問題(OSSP)は、製造業やサービス業など多くの産業現場で発生する最適化問題であり、ジョブと機械の数が増加するにつれて計算量が急速に増大することが課題となっています。厳密解法は問題規模の拡大とともに急速に計算不可能となり、古典的なディスパッチルールやメタヒューリスティクスは大規模問題で解の品質を維持するために大幅なチューニングが必要です。
本研究は、エンコーダ・デコーダ構造とマルチヘッドアテンションを備えたTransformerベースのスケジューリングポリシーを開発しました。このモデルはTaillardベンチマークインスタンス(4x4、5x5、7x7、10x10)で訓練され、処理時間行列のみを入力として受け取り、最良既知値から典型的に15~30%以内のメイクスパン(全工程完了時間)を持つ実行可能なスケジュールを生成します。
スケーラビリティを評価するため、訓練されたポリシーは40x40から100x100のランダムに生成されたインスタンスに対して再訓練なしで適用され、SPT、LPT、MWKR、ESTなどの古典的ディスパッチヒューリスティクスと比較されました。これらの大規模インスタンス全体で、Transformerは標準的な下界相対値で平均12.89~15.12%のギャップを達成しています。ESTとの比較では、Transformerは競争力を維持しながらSPTやLPTを大幅に上回るパフォーマンスを示しました。これらの結果は、小規模OSSPインスタンスで訓練されたTransformerポリシーがより大規模な問題へ汎化でき、古典的なディスパッチルールに対する学習ベースの軽量な代替手段を提供することを示唆しています。