配送スケジューリング問題に対する多項式的近似スキームの実用性向上に関する研究

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

本研究課題では,配送スケジューリング問題に対する多項式的近似スキーム(すなわち,多項式オーダ時間で動作する1+e倍近似アルゴリズムの族.e>0は任意の正数)の実用性の向上を目指した.特に本年度は,時間量と領域量のより少ない近似スキームの構築に主眼を置いた.まず,準備時間制約のあるパス上の配送スケジューリング問題に対して,ほぼ線形オーダ時間で動作する2+e倍近似アルゴリズムの族を発表した.これは,近似スキームではないが,これまでにこの問題に対して得ていた近似スキームの時間量と領域量を大幅に減少させるものであり,最悪ケースの近似精度保証よりも実際の計算時間やメモリ容量を重視しなければならない場合は,これが有用である.次に,同じ問題に対して,すでに得ていた近似スキームについて,理論的にどれだけ時間量と領域量を減少させられるかを検討した.これは昨年度に大体の部分はできていたが,投稿先の査読者の有益なコメントによって,より洗練された形式で記述することができた.その時間量と領域量は,それでもなお実用的には十分とは言えないものの,搬送車台数をmとするとき,およそ仕事数nのm乗のオーダは小さくなっている.これらの結果は国際的な学術雑誌に掲載された.本年度は,さらに関連する話題として,工作機械の間で複数の仕掛り品が同時並行的に搬送されるような柔軟生産セルの最適スケジューリング問題を考察し,これまでの最良近似比2を少なくとも1/6は改善する近似アルゴリズムを構築した.