WEKO3
アイテム
A Generalized Multi-organization Scheduling on Unrelated Parallel Machines
https://nitech.repo.nii.ac.jp/records/3451
https://nitech.repo.nii.ac.jp/records/3451d002de49-313c-420e-b1c2-26f9faac3d51
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文_fulltext (240.5 kB)
|
c 2009 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redision to servers or lists, or reuse of any copyrighted components of this work in other works.
|
| Item type | 会議発表論文 / Conference Paper(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-25 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | A Generalized Multi-organization Scheduling on Unrelated Parallel Machines | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Multi-organization | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | Scheduling | |||||||||||||||||
| キーワード | ||||||||||||||||||
| 言語 | en | |||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||
| 主題 | parallel | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||||||||||
| 資源タイプ | conference paper | |||||||||||||||||
| 著者 |
Oshita, Fukuhito
× Oshita, Fukuhito
× Izumi, Tomoko
× 泉, 泰介
|
|||||||||||||||||
| 著者別名 | ||||||||||||||||||
| 識別子Scheme | WEKO | |||||||||||||||||
| 識別子 | 8720 | |||||||||||||||||
| 識別子Scheme | NRID | |||||||||||||||||
| 識別子URI | http://rns.nii.ac.jp/nr/1000020432461 | |||||||||||||||||
| 識別子 | 1000020432461 | |||||||||||||||||
| 姓名 | Izumi, Taisuke | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 姓名 | 泉, 泰介 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 姓名 | イズミ, タイスケ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| 姓 | Izumi | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 姓 | 泉 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 姓 | イズミ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| 名 | Taisuke | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 名 | 泰介 | |||||||||||||||||
| 言語 | ja | |||||||||||||||||
| 名 | タイスケ | |||||||||||||||||
| 言語 | ja-Kana | |||||||||||||||||
| 書誌情報 |
en : 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies p. 26-33, 発行日 2009-02-11 |
|||||||||||||||||
| 出版者 | ||||||||||||||||||
| 出版者 | Institute of Electrical and Electronics Engineers | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 著者版フラグ | ||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||
| DOI | ||||||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||
| 関連識別子 | http://dx.doi.org/10.1109/PDCAT.2009.26 | |||||||||||||||||
| 関連名称 | 10.1109/PDCAT.2009.26 | |||||||||||||||||
| 内容記述 | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | We consider the parallel computing environment where m organizations provide machines 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 situations, we formulate the A?-cooperative multi-organization scheduling problem (A?-MOSP), where A? A? 1 is a parameter representing the degree of cooperativeness. A?-MOSP minimizes the makespan under the cooperation constraint that each organization does not allow the completion time of its own jobs to be delayed A? times of that in the case where those jobs are executed by itself. In this paper, we aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between A? and the quality of the global makespan. For A? = 1 (i.e., each organization never sacrifices its completion time), we show an instance where the cooperation constraint degrades the optimal makespan by m times. In contrast, for A? > 1, we can construct an algorithm transforming any unconstrained schedule to one satisfying the cooperation constraint. This algorithm bounds the degradation ratio by A?/(A? - 1), which implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of A?-MOSP. We show its strongly NPhardness and inapproximability for the approximation factor less than max{(A? + l)/A?, 3/2}. We also show the hardness of transformation: Even if an optimal schedule under no cooperation constraint is given, no polynomial-time algorithm finds an optimal schedule for A?-MOSP. This result is a witness for inexistence of general polynomial-time transformation algorithms that preserve the approximation ratio. | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 内容記述 | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | Higashi Hiroshima, Japan December 8-11, 2009 | |||||||||||||||||
| 言語 | en | |||||||||||||||||
