...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Optimal semi-online algorithm for scheduling with rejection on two uniform machines
【24h】

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

机译：两台均等机上带拒绝的最优半在线调度算法

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

摘要

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ H (s) as a piecewise function in terms of the speed ratio s.
机译：在本文中，我们考虑了分别在速度为1和s≥1的两台均匀机器上具有拒绝的半在线调度问题。给出了一系列独立的作业，每个作业的特点是其大小（处理时间）和罚款，从某种意义上说，作业是一个接一个地到达的，可以通过支付一定的罚款来拒绝，也可以分配给某些机器。不允许抢占。目的是使计划的总和最小化，该总和由所有接受的工作和所有被拒绝的工作的总罚款产生。此外，允许两种拒绝策略，因此算法可以提出两种不同的方案，从中可以选择更好的解决方案。对于上述版本，我们提出了一种最佳的半在线算法H，该算法以速度比s为分段函数，实现了竞争比ρ H （s）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号