论文标题
一种改进的贪婪算法，用于在无关机器上进行随机在线调度
An Improved Greedy Algorithm for Stochastic Online Scheduling on Unrelated Machines
论文作者
论文摘要
大多数实用的调度应用程序涉及有关工作时间和工作时间的一些不确定性。随机在线调度是捕获这一点的完善模型。在这里，到达发生在线，而处理时间是随机的。对于此模型，Gupta，Moseley，Uetz和Xie最近制定了一种有效的政策，用于对无关的机器进行非抢先调度，目的是最大程度地减少预期的总加权完成时间。我们通过将贪婪的作业分配与每台机器上的$α_J$ - 点调度相结合来改进这项政策。通过这种方式，我们获得了$（3+ \ sqrt 5）（2+δ）$ - 竞争性的确定性和$（8+4δ）$ - 竞争性随机随机随机在线调度策略，其中$δ$是处理时间平方系数的上限。我们还为所有固定分配政策的类别中的这些政策提供了持续的绩效保证。当已知上限$δ$的上限$δ$或已知某些$δ\ ge 1 $的上限$δ$ -nbue时，可以增强$α_j$ - 点调度。这意味着不相关的机器的竞争比率提高了，但也可能具有独立的兴趣。
Most practical scheduling applications involve some uncertainty about the arriving times and lengths of the jobs. Stochastic online scheduling is a well-established model capturing this. Here the arrivals occur online, while the processing times are random. For this model, Gupta, Moseley, Uetz, and Xie recently devised an efficient policy for non-preemptive scheduling on unrelated machines with the objective to minimize the expected total weighted completion time. We improve upon this policy by adroitly combining greedy job assignment with $α_j$-point scheduling on each machine. In this way we obtain a $(3+\sqrt 5)(2+Δ)$-competitive deterministic and an $(8+4Δ)$-competitive randomized stochastic online scheduling policy, where $Δ$ is an upper bound on the squared coefficients of variation of the processing times. We also give constant performance guarantees for these policies within the class of all fixed-assignment policies. The $α_j$-point scheduling on a single machine can be enhanced when the upper bound $Δ$ is known a priori or the processing times are known to be $δ$-NBUE for some $δ\ge 1$. This implies improved competitive ratios for unrelated machines but may also be of independent interest.
