相互無関係並列マシンにおける一般化多組織スケジューリング

概要

論文の詳細を見る
本稿では,複数の組織が計算資源とジョブを与えるグリッドを考える.一般的なスケジューリング問題では,各組織がグリッドに対して協力的であることを前提として,メイクスパン(全ジョブの終了時刻)の最小化を目標とする.しかし,各組織は自身のジョブの終了時刻を最小化したいと考えており,グリッドに対して常に協力的であるとは限らない.このような状況を扱うために,本稿では,各組織の協力度を表すパラメータαを導入し,α-協力的多組織スケジューリング問題(α-MOSP)を定義する.α-MOSPでは,各組織のジョブの終了時刻が自身の資源のみで計算した場合の終了時刻に対してα倍より遅くならないという制約(以下,協力制約)を考え,協力制約のもとでメイクスパンの最小化を目標とする.本稿では,協力度αと最小メイクスパンの関係について考察する.その結果,α=1の場合,すなわち,各組織が非協力的である場合,協力制約により最小メイクスパンがm倍に増加するインスタンスが存在することを示す(mは組織の数).一方,α>1の場合,協力制約を満たしていないスケジュールを協力制約を満たすスケジュールへ,メイクスパンの増加をα/(α-1)倍以内に抑えて変換可能であることを示す.この事実は,小さな協力により最小メイクスパンを劇的に改善できることを示している.また,α-MOSPの計算複雑度についても結果を示す.
社団法人電子情報通信学会の論文
2008-09-04

相互無関係並列マシンにおける一般化多組織スケジューリング

スポンサーリンク

概要

著者

関連論文

スポンサーリンク