Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching
Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching
复制标题
通过立即调度最大限度地减少总流程时间和总完成时间
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Y. Azar
中科院分区：
文献类型：
--
作者：
N. Avrahami;Y. Azar
我们考虑了在多处理机环境中调度随时间到达的作业的问题，在立即分派的情况下，不允许作业迁移。目标是最小化总流程时间(系统中的总时间)和总完成时间。以前的研究表明，抢占(中断作业并在稍后继续执行)是使调度算法有效的内在原因，而迁移(在不同的机器上继续执行)则不是。尽管如此，当前的非迁移性在线算法仍然存在对未分配作业的中央队列的需求，这在大型计算系统(如Web)中是“没有选择的”。我们介绍了一种简单的在线非迁移算法IMD，它采用立即分派，即立即将释放的作业分配给其中一台机器。我们证明了该算法的性能相对于总流时是最优迁移离线算法的对数倍，相对于总完成时间是最优迁移离线算法的一个小常量倍。这解决了Awerbuch等人提出的一个公开问题。(斯托克99)。
We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with immediate dispatching, disallowing job migration. The goal is to minimize both the total flow time (total time in the system) and the total completion time. Previous studies have shown that while preemption (interrupt a job and later continue its execution) is inherent to make a scheduling algorithm efficient, migration (continue the execution on a different machine) is not. Still, the current non-migratory online algorithms suffer from a need for a central queue of unassigned jobs which is a "no option" in large computing systems, such as the Web. We introduce a simple online non-migratory algorithm IMD, which employs immediate dispatching, i.e., it immediately assigns released jobs to one of the machines. We show that the performance of this algorithm is within a logarithmic factor of the optimal migratory offline algorithm, with respect to the total flow time, and within a small constant factor of the optimal migratory offline algorithm, with respect to the total completion time. This solves an open problem suggested by Awerbuch et al. (STOC 99).