• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Online Flow Time Scheduling in the Presence of Preemption Overhead
【24h】

Online Flow Time Scheduling in the Presence of Preemption Overhead

机译：具有抢占开销的在线流时间调度

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

摘要

This paper revisits the online problem of preemptive scheduling to minimize the total flow time. Previous theoretical results often assume that preemption is free, which is not true for most systems. This paper investigates the complexity of the problem when a processor has to perform a certain amount of overhead (extra work) before it resumes the execution of a job preempted before. Such overhead causes delay to all unfinished jobs. In this paper we first consider single-processor scheduling. We show that no online algorithm can be competitive for total flow time in the presence of preemption overhead (note that the well-known online algorithm SRPT is 1-competitive when preemption overhead is zero). We then consider resource augmentation and show a simple algorithm that is (1 + ∈)-speed (1 + 1/∈)-competitive for minimizing total flow time on a single processor. We also extend the result to the multiprocessor setting.
机译：本文探讨了抢先式调度的在线问题，以最大程度地减少总流程时间。先前的理论结果通常假定抢占是免费的，这对于大多数系统而言并非如此。本文研究了当处理器必须先执行一定量的开销（额外工作）才能恢复之前执行的作业时，该问题的复杂性。这样的开销会延迟所有未完成的工作。在本文中，我们首先考虑单处理器调度。我们显示，在存在抢占开销的情况下，没有任何在线算法可以竞争总流量时间（请注意，当抢占开销为零时，众所周知的在线算法SRPT为1竞争）。然后，我们考虑资源扩充，并展示了一个简单的算法（1 +∈）-速度（1 + 1 /∈）-有竞争力，可最大程度地减少单个处理器上的总流时间。我们还将结果扩展到多处理器设置。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号