| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-09-11 16:10 An analysis of a generalized multi-organization scheduling on unrelated parallel machines ○Fukuhito Ooshita（Osaka Univ.）・Tomoko Izumi・Taisuke Izumi（Nagoya Inst. of Tech.）  COMP2008-32 |
|
| 抄録 | （和） | 本稿では，複数の組織が計算資源とジョブを与えるグリッドを考える．一般的なスケジューリング問題では，各組織がグリッドに対して協力的であることを前提として，メイクスパン（全ジョブの終了時刻）の最小化を目標とする．しかし，各組織は自身のジョブの終了時刻を最小化したいと考えており，グリッドに対して常に協力的であるとは限らない．このような状況を扱うために，本稿では，各組織の協力度を表すパラメータ$\alpha$を導入し，$\alpha$-協力的多組織スケジューリング問題（$\alpha$-MOSP）を定義する．$\alpha$-MOSPでは，各組織のジョブの終了時刻が自身の資源のみで計算した場合の終了時刻に対して$\alpha$倍より遅くならないという制約（以下，協力制約）を考え，協力制約のもとでメイクスパンの最小化を目標とする． 本稿では，協力度$\alpha$と最小メイクスパンの関係について考察する．その結果，$\alpha=1$の場合，すなわち，各組織が非協力的である場合，協力制約により最小メイクスパンが$m$倍に増加するインスタンスが存在することを示す（$m$は組織の数）．一方，$\alpha>1$の場合，協力制約を満たしていないスケジュールを協力制約を満たすスケジュールへ，メイクスパンの増加を$\alpha/(\alpha-1)$倍以内に抑えて変換可能であることを示す．この事実は，小さな協力により最小メイクスパンを劇的に改善できることを示している．また，$\alpha$-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 $\alpha$-cooperative multi-organization scheduling problem ($\alpha$-MOSP), where $\alpha\ge 1$ is a parameter representing the degree of cooperation. The $\alpha$-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed $\alpha$ times of that in the case where those jobs are executed by itself. In this paper, we first investigate the relation between $\alpha$ and the quality of the global makespan. For $\alpha=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 $\alpha>1$, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by $\alpha / (\alpha - 1)$, which implies that weak cooperation improves the makespan dramatically. Second, we give some complexity results of $\alpha$-MOSP. |
|
| キーワード | （和） | グリッド計算 / 異種並列計算環境 / スケジューリングアルゴリズム / 近似アルゴリズム / / / / |
| （英） | grid computing / heterogeneous parallel computing environment / scheduling algorithm / approximation algorithm / / / / | |
| 文献情報 | 信学技報, vol. 108, no. 206, COMP2008-32, pp. 63-70, 2008年9月. | |
| 資料番号 | COMP2008-32 | |
| 発行日 | 2008-09-04 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-32 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-09-11 - 2008-09-11 |
| 開催地（和） | 名古屋工業大学 |
| 開催地（英） | Nagoya Inst. of Tech. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 大下 福仁 / Fukuhito Ooshita / オオシタ フクヒト |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 泉 朋子 / Tomoko Izumi / イズミ トモコ |
| 第2著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） | 泉 泰介 / Taisuke Izumi / イズミ タイスケ |
| 第3著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-09-11 16:10:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-32 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.206 |
| ページ範囲 | pp.63-70 |
| ページ数 | 8 |
| 発行日 | 2008-09-04 (COMP) |
[研究会発表申込システムのトップページに戻る]