Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time
Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time
复制标题
DOI：
10.1016/j.tcs.2016.01.001
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
Ji Tian;Qian Wang;Ruyan Fu;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Ji Tian;Qian Wang;Ruyan Fu;Jinjiang Yuan
我们考虑在 m 个无界直放线批量机器上进行在线调度，并指定交货时间。这里，落线批处理机可以在一个批次中处理多个作业，使得一个批次的处理时间等于该批次中作业的最长处理时间，一个批次中的作业具有相同的开始时间，并且一个作业的完成时间等于其开始时间和处理时间之和。一旦机器上完成作业的处理，我们立即将其运送到目的地。目标是最大限度地缩短所有工作的交付时间。对于这个问题，我们提出了一种最佳的在线算法，其竞争比为 1+ α m，其中 α m 是方程 α 2+ m α− 1= 0 的正根。
We consider the online scheduling on m unbounded drop-line batch machines with delivery times. Here a drop-line batch machine can process several jobs in a batch so that the processing time of a batch is equal to the longest processing time of the jobs in the batch, the jobs in a batch have the same starting time, and the completion time of a job is equal to the sum of its starting time and its processing time. Once the processing of a job is completed on the machine, we immediately deliver it to the destination. The objective is to minimize the time by which all jobs have been delivered. For this problem, we present a best possible online algorithm with a competitive ratio of 1+ α m, where α m is the positive root of the equation α 2+ m α− 1= 0.