独立タスクを非一様プロセッサに割付ける近似算法と厳密算法

スポンサーリンク

概要

• 論文の詳細を見る

• 順序制約のないn個のタスク(独立タスク)を、タスク毎に相性の異なるm(m≧2)台のプロセッサ(非一様プロセッサ)で並列処理する場合を考える。タスクの分割処理は許されないものとして、総処理時間を最小にする割付け計画を求めたい。本論文では、NP--完全であるこの問題に対し、まずm=2の場合について効率のよいε-近似算法を提案する。これは、n個のタスクを、スケジュール長に対する影響の大きいものとそうでないものに分割し、前者に対しては、(実質的に)全ての場合を列挙し、その各部分スケジュール毎に後者を割付ける連続緩和問題を解き、それを丸めて近似解を求めるというものである。相対誤差限界εをを保証しようとするとき、前者の集合の大きさが高々「2/ε」で済むこと、後者に対する連続緩和問題nlogn以下の手間で解けることが示される。また既存のε/δ-近似算法との比較のため、ε=0。1とした場合の数値実験結果も示される。次にm>2の場合については、元の問題を捉え直し、タスクの種類をk(各種類毎に複数の同一タスクが存在する)とし、k《nに限定して考えた。この枠組みのもとで、動的計画法と二分探索法に基づく多項式時間(ただしkについては指数オーダ)の厳密算法を提案する。

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• 沼田 一道

  電気通信大学

関連論文

• 単体内の点集合の分割について(LP新解法)
• モデルとしての計算機と道具としての計算機 : VOS3上のCP/M-80シミュレータ
• LISP語による知能端末ソフトウェアの試み
• 独立タスクを非一様プロセッサに割付ける近似算法と厳密算法

スポンサーリンク