检索结果-内蒙古大学图书馆

10th International Conference on parallel and Distributed computing, Applications and Technologies

作者： Ooshita, Fukuhito Izumi, Tomoko Izumi, Taisuke Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadaoka Suita Osaka 5650871 Japan Ritsumeikan Univ Coll Informat Sci & Engn Shiga 5258577 Japan Nagoya Inst Technol Grad Sch Engn Nagoya Aichi 4668555 Japan

ISBN: (纸本)9781424452910

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 alpha-cooperative multi-organization scheduling problem (alpha-MOSP), where alpha >= 1 is a parameter representing the degree of cooperativeness. 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 aim to reveal the relation between the makespan and the degree of cooperativeness. First, we investigate the relation between alpha and the quality of the global makespan. For alpha = 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 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 study the complexity of alpha-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(alpha 1)/alpha,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.

关键词： heterogeneous parallel computing environments scheduling algorithm approximation algorithm computation complexity

来源：评论

学校读者我要写书评

暂无评论

THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED parallel MACHINE SCHEDULING

引用

parallel PROCESSING LETTERS 2012年第2期22卷 1250006-1250006页

作者： Ooshita, Fukuhito Izumi, Tomoko Izumi, Taisuke Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadoka Suita Osaka 5650871 Japan Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Shiga 5258577 Japan Nagoya Inst Technol Grad Sch Engn Syowa Ku Nagoya Aichi 4668555 Japan

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 (alpha-MOSP), where alpha >= 1 is a parameter representing the degree of cooperativeness. alpha-MOSP minimizes the makespan under the multi-organization 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. First, we reveal the relation between the makespan and the degree of cooperativeness. We show that the multi-organization constraint may degrade the optimal makespan by m times for a = 1, while the degradation ratio is bounded by alpha/(alpha- 1) for a > 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of a-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(alpha + 1)/alpha, 3/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for a-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.

关键词： heterogeneous parallel computing environments scheduling algorithm multi-organization scheduling approximation algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：