通信遅延を考慮したタスクスケジューリングアルゴリズムについて

河田 俊郎  大山口 通夫  太田 義勝  

誌名
電子情報通信学会論文誌 D   Vol.J85-D1   No.11   pp.1088-1092
発行日: 2002/11/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: レター
専門分野: 
キーワード: 
スケジューリング,  タスク複製,  通信遅延,  NP完全,  近似アルゴリズム,  

本文: PDF(142.6KB)>>
論文を購入




あらまし: 
Papadimitriouら(1990)は,タスク複製を許す通信遅延のあるスケジューリング問題がNP完全であることを示すとともに,近似精度2のアルゴリズムを与えた.本論文ではタスク間の依存グラフの高さを2に限ってもNP完全であること,高さ2の場合には近似精度が1.5に改善されたアルゴリズムが存在することを示す.