• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >A 3.42-Approximation Algorithm for Scheduling Malleable Tasks under Precedence Constraints
【24h】

A 3.42-Approximation Algorithm for Scheduling Malleable Tasks under Precedence Constraints

机译：优先约束下可延展任务的3.42-逼近算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Scheduling malleable tasks under general precedence constraints involves finding a minimum makespan (maximum completion time) by a feasible allotment. Based on the monotonous penalty assumptions of Blayo et al. [2], this work defines two assumptions concerning malleable tasks: the processing time of a malleable task is nonincreasing in the number of processors, while the work of a malleable task is nondecreasing in the number of processors. Additionally, the work function is assumed herein to be convex in the processing time. The proposed algorithm reformulates the linear program of [11], and this algorithm and associated proofs are inspired by the ones of [11]. This work describes a novel polynomial-time approximation algorithm that is capable of achieving an approximation ratio of $(2+sqrt{2}approx 3.4142)$. This work further demonstrates that the proposed algorithm can yield an approximation ratio of 2.9549 when the processing time is strictly decreasing in the number of the processors allocated to the task. This finding represents an improvement upon the previous best approximation ratio of $(100/63+100(sqrt{6469}+137)/5481approx 3.2920)$ [12] achieved under the same assumptions.
机译：在一般优先级约束下安排延展性任务涉及通过可行的分配找到最小的制造时间（最大的完成时间）。基于Blayo等人的单调惩罚假设。 [2]，这项工作定义了有关延展性任务的两个假设：延展性任务的处理时间在处理器数量上没有增加，而延展性任务的工作在处理器数量上没有减少。另外，在此，功函数在处理时间上是凸的。所提出的算法重新制定了[11]的线性程序，并且该算法和相关证明受到[11]的启发。这项工作描述了一种新颖的多项式时间逼近算法，该算法能够实现逼近率$（2 + sqrt {2}约3.4142）$。这项工作进一步证明，当处理时间严格减少分配给任务的处理器数量时，所提出的算法可产生约2.9549的近似比率。该发现表示在相同假设下获得的先前最佳近似比率$（100/63 + 100（sqrt {6469} +137）/ 5481约3.2920）$ [12]。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号