...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >A note on periodic schedules for linear precedence constraints
【24h】

A note on periodic schedules for linear precedence constraints

机译：关于线性优先约束的定期计划的注释

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

摘要

Hanen and Munier-Kordon [C. Hanen, A. Munier Kordon, Periodic schedules for linear precedence constraints, Discrete Applied Mathematics 157 (2) (2009) 280-291] have considered a problem of scheduling periodic tasks each of which has to be repeated with its own period. They have developed a weakly polynomial algorithm for a particular class of linear precedence graphs called unitary graphs, which generalizes the usual not-earlier precedence relations between the tasks. The purpose of this note is two-fold. First, we suggest a further generalization of the unitary relations that extends the usual not-later precedence relations; as a result, the arc lengths and heights in the underlying graph may be negative. Second, we show that, as soon as the arc heights in the graph are computed, an optimum periodic schedule can be found in strongly polynomial time.
机译：Hanen和Munier-Kordon [C. Hanen，A. Munier Kordon，线性优先约束的周期性计划，离散应用数学157（2）（2009）280-291]已经考虑到了计划周期性任务的问题，每个周期性任务都必须以自己的周期重复进行。他们为一类称为unit图的线性优先级图开发了一种弱多项式算法，该算法概括了任务之间通常的较早优先级关系。该注释的目的是双重的。首先，我们建议对relations关系进行进一步的概括，以扩展通常的非优先关系。结果，下图中的弧长和弧高可能为负。其次，我们表明，一旦计算出图中的弧高，就可以在强多项式时间内找到最佳的周期计划。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号