A Best Possible Online Algorithm for Scheduling to minimize Maximum Flow-Time on Bounded batch Machines
A Best Possible Online Algorithm for Scheduling to minimize Maximum Flow-Time on Bounded batch Machines
复制标题
DOI：
10.1142/s0217595914500304
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Chengwen Jiao;Wenhua Li;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Chengwen Jiao;Wenhua Li;Jinjiang Yuan
我们考虑在m台完全相同的并行分批机器上的单位长度作业的在线排序问题。随着时间的推移，工作机会会到来。目标是最小化最大流时间，作业的流时间是其完成时间和投放时间之差。一台并行批处理机一批最多可以同时处理b个作业。这里，批处理能力是有限制的，即b<；∞。本文给出了竞争比为$\FRAC{\Sqrt{5}+1}{2}\约1.618$的最优在线算法。
We consider online scheduling of unit length jobs on m identical parallel-batch machines. Jobs arrive over time. The objective is to minimize maximum flow-time, with the flow-time of a job being the difference of its completion time and its release time. A parallel-batch machine can handle up to b jobs simultaneously as a batch. Here, the batch capacity is bounded, that is b < ∞. In this paper, we provide a best possible online algorithm for the problem with a competitive ratio of $\frac{\sqrt{5}+1}{2}\approx 1.618$.