| 講演名 | 2008-09-11 相互無関係並列マシンにおける一般化多組織スケジューリング 大下 福仁, 泉 朋子, 泉 泰介, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,複数の組織が計算資源とジョブを与えるグリッドを考える.一般的なスケジューリング問題では,各組織がグリッドに対して協力的であることを前提として,メイクスパン(全ジョブの終了時刻)の最小化を目標とする.しかし,各組織は自身のジョブの終了時刻を最小化したいと考えており,グリッドに対して常に協力的であるとは限らない.このような状況を扱うために,本稿では,各組織の協力度を表すパラメータαを導入し,α-協力的多組織スケジューリング問題(α-MOSP)を定義する.α-MOSPでは,各組織のジョブの終了時刻が自身の資源のみで計算した場合の終了時刻に対してα倍より遅くならないという制約(以下,協力制約)を考え,協力制約のもとでメイクスパンの最小化を目標とする.本稿では,協力度αと最小メイクスパンの関係について考察する.その結果,α=1の場合,すなわち,各組織が非協力的である場合,協力制約により最小メイクスパンがm倍に増加するインスタンスが存在することを示す(mは組織の数).一方,α>1の場合,協力制約を満たしていないスケジュールを協力制約を満たすスケジュールへ,メイクスパンの増加をα/(α-1)倍以内に抑えて変換可能であることを示す.この事実は,小さな協力により最小メイクスパンを劇的に改善できることを示している.また,α-MOSPの計算複雑度についても結果を示す. |
| 抄録(英) | We consider the grid where each organization provides a machine and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the above situations, we newly introduce the α-cooperative multi-organization scheduling problem (α-MOSP), where α≧1 is a parameter representing the degree of cooperation. The α-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed α times of that in the case where those jobs are executed by itself. In this paper, we first investigate the relation between α and the quality of the global makespan. For α=1 (i.e., the completely uncooperative case), we show an instance where the cooperation constraint degrades the optimal makespan by m times, where m is the number of organizations. In contrast, for α>1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by α/(α-1), which implies that weak cooperation improves the makespan dramatically. Second, we give some complexity results of α-MOSP. |
| キーワード(和) | グリッド計算 / 異種並列計算環境 / スケジューリングアルゴリズム / 近似アルゴリズム |
| キーワード(英) | grid computing / heterogeneous parallel computing environment / scheduling algorithm / approximation algorithm |
| 資料番号 | COMP2008-32 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2008/9/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 相互無関係並列マシンにおける一般化多組織スケジューリング |
| サブタイトル（和） | |
| タイトル（英） | An analysis of a generalized multi-organization scheduling on unrelated parallel machines |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グリッド計算 / grid computing |
| キーワード(2)（和/英） | 異種並列計算環境 / heterogeneous parallel computing environment |
| キーワード(3)（和/英） | スケジューリングアルゴリズム / scheduling algorithm |
| キーワード(4)（和/英） | 近似アルゴリズム / approximation algorithm |
| 第 1 著者 氏名（和/英） | 大下 福仁 / Fukuhito OOSHITA |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 泉 朋子 / Tomoko IZUMI |
| 第 2 著者 所属（和/英） | 名古屋工業大学産学官連携センター Center of Social Contribution and Collaboration, Nagoya Institute of Technology |
| 第 3 著者 氏名（和/英） | 泉 泰介 / Taisuke IZUMI |
| 第 3 著者 所属（和/英） | 名古屋工業大学大学院工学研究科 Graduate School of Engineering, Nagoya Institute of Technology |
| 発表年月日 | 2008-09-11 |
| 資料番号 | COMP2008-32 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 206 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |