...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel Processing Letters >THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING
【24h】

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

机译：无关并行机调度中的多组织约束价格

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

摘要

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 α-cooperative multi-organization scheduling problem (α-MOSP), where α ≥ 1 is a parameter representing the degree of cooperativeness. α-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 α times of that in the case where those jobs are executed by itself.nnFirst, 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 α = 1, while the degradation ratio is bounded by α/(α - 1) for α > 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of α-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(α + 1)/α, 3/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for α-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.
机译：我们考虑了并行计算环境，其中m个组织提供了机器和要执行的多个作业。尽管需要组织合作以最大程度地减少全球制造时间，但每个组织也期望主要是更快地完成自己的工作，因此不一定是合作的。为了应对这种情况，我们制定了α-合作的多组织调度问题（α-MOSP），其中α≥1是代表合作程度的参数。 α-MOSP在多组织约束下最大程度地降低了制造跨度，即每个组织都不允许延迟其自己的工作的完成时间，这是那些组织自己执行工作的情况的α倍。合作期限和合作程度。我们表明，对于α= 1，多组织约束可能会使m的最佳制造期降级，而当α> 1时，降级率受α/（α-1）限制。这意味着弱合作会显着提高制造期。其次，我们研究α-MOSP的复杂性。对于小于max {（α+ 1）/α，3/2}的逼近因子，我们显示出其强烈的NP硬度和不可逼近性。我们还显示了从无多组织约束的最佳计划向α-MOSP的最佳计划转变的难度。该结果证明了保留近似比率的通用多项式时间变换算法的不存在。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号