メタヒューリステイクスによる汎用組合せ最適化アルゴリズムに関する研究

点击翻译按钮获取中文摘要

資源制約スケジューリング問題(RCPSP)の一般化として、凸型コスト関数の最小化問題を考え、メタヒューリスティクスにもとづくアルゴリズムの開発を行った。RCPSPの枠組みでは、多くの場合、種々の制約の下で作業をできるだけ早く完了することを目的とする。これに対し本研究では、2つの作業の開始時刻(もしくは完了時刻)の差に応じて定まる「時間ずれコスト」を導入し、その総和を最小化する問題を考えた。(ただし、時間ずれコストは凸関数に限定している。)これにより、納期ずれの最小化に対応することができ、さらにプロジェクトスケジューリングにおいて期間短縮の方法として用いられるクラッシングやファストトラッキングを扱うことも可能になった。アルゴリズムは局所探索法を基本としているが、最小費用フローアルゴリズムによる解の評価や、最小カットアルゴリズムを用いて解を改善する仕組みを組み込むなどの工夫を加えている。一方、昨年度より行っている重工業における鋳造ラインのスケジューリングについても本研究で開発したアルゴリズムの検証を継続して行った。その結果、より大規模なデータに対する計算実験において、問題の定式化の違いが計算時間に大きく影響することが確認され、適切な定式化を行うための指針について考察を行った。しかしながら、実用性を考えると、性能が定式化に大きく依存しないアルゴリズムを開発することが望ましく、今後の課題である。