Experimental Analysis 10

あたらしい数理最適化 -GurobiとPython言語で解く- (近代科学社) 2012年 久保幹雄,ジョア(ジョアン)・ペドロ・ペドロソ,村松正和,アブドル・レイス 著では,実験の結果は示していない.今回は,実験的解析の10回目であり,スケジューリング問題に対する実験的解析である.

実験に用いたのはランダムに生成した1機械リース時刻付きの納期遅れ最小化問題である.すべてのデータは[1,99]の一様乱数にしたがって生成した.以下に示すのは Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz RAM: 64 GB でのCPU時間である.

スケジューリング問題に対する計算時間の変化

図中で,lopは線形順序付け定式化,tiは時刻添え字定式化,disjは施設定式化を表す.結果から,最も良いのは線形順序付け定式化,次いで時刻添え字定式化,最も悪いのは大きな数(M)を用いた離接定式化である.

ただし,時刻添え字定式化は,時刻を表す数字が大きくない場合には,より高速になることが予想される.

いずれにせよ,1機械の簡単な問題に対してもGurobiでは比較的長い計算時間がかかることから,スケジューリング問題に対しては,制約プログラミングや専用のメタ解法に基づくソルバー(たとえばSCOPやOptSeq)が実務的に推奨されることが分かる.