【要約】ジョブショップ・スケジューリング選手権 ―― 貪欲・焼きなまし・遺伝的アルゴリズム・厳密解を同じ問題で競わせる [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
製造現場の担当者は、限られた設備を複数の仕事で効率的に共有する工程順序の決定に直面している。機械の排他制御と工程の依存関係がある中で、全体の終了時刻を最小化する必要がある。
- ・機械の排他制御と工程の依存関係による制約。
- ・メイクスパン（全工程終了時刻）の最小化。
- ・問題規模の拡大に伴う組み合わせ爆発（NP困難）。
// Approach
著者は、ジョブショップ問題を解くために4つの異なるアルゴリズムをPythonで実装し、比較実験を行った。評価回数の予算を揃えることで、探索の効率性を公平に測定している。
- ・貪欲法：SPTやMWKR等のディスパッチ規則による即時決定。
- ・焼きなまし法：温度パラメータを用いた局所探索による解の改善。
- ・遺伝的アルゴリズム：POX交叉を用いた集団進化による探索。
- ・厳密解：分枝限定法を用い、下界による枝刈りで最適解を探索。
// Result
実験の結果、問題の規模に応じて最適な手法が変化することが定量的に示された。手法の名称による決め打ちではなく、実測に基づく選定の重要性が浮き彫りになった。
- ・小規模：全手法が最適解に到達。
- ・中規模：焼きなまし法と遺伝的アルゴリズムが厳密解と同等の解を発見。
- ・大規模：厳密解は計算爆発により失速。焼きなまし法が遺伝的アルゴリズムを僅かに上回る精度を記録。
Senior Engineer Insight
> 手法の名称で性能を決め打つのは極めて危険だ。大規模問題では厳密解は通用せず、ヒューリスティクスの性能は問題構造に強く依存する。実務においては、貪欲法で即席の初期解を作り、それを焼きなまし法などの局所探索で磨き上げるハイブリッドなアプローチが、計算コストと解の質のバランスを取る上で最も現実的である。