...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays
【24h】

Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays

机译：期限不统一的树状任务系统的调度受单位长度通信延迟的影响

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

摘要

We consider the problem of scheduling outforests and inforests with non-uniform deadlines subject to unit-length communication delays. We will prove that minimum-tardiness schedules for outforests on two processors and for chain-like task systems on m processors can be constructed in polynomial time. In addition, we present two polynomial-rime approximation algorithms: one with an asymptotic approximation bound of 2 - 2/m for scheduling outforests with non-positive deadlines on m processors and one with an asymptotic approximation:bound of 2 for scheduling inforests with non-positive deadlines on m processors. Moreover, it is proved that for a special class of inforests, minimum-tardiness schedules on m processors can be constructed in polynomial time. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 16]
机译：我们考虑在单位长度通信延迟的情况下，在期限不统一的情况下安排外林和森林的问题。我们将证明，可以在多项式时间内构造两个处理器上的外林和m个处理器上的链式任务系统的最小延迟时间表。此外，我们提出了两种多项式近似算法：一种用于在m个处理器上以非正数截止时间来调度具有非正负期限的外林，其渐近近似界为2-2 / m，另一种是采用渐近式：用于调度具有非截止期限的森林中的2界。 -m个处理器的最后期限。此外，事实证明，对于一类特殊的森林，可以在多项式时间内构造m个处理器上的最小拖延进度。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：16]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号