Improved lower bounds for online scheduling to minimize total stretch
Improved lower bounds for online scheduling to minimize total stretch
复制标题
DOI：
10.1016/j.tcs.2017.09.032
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Koji M. Kobayashi
中科院分区：
文献类型：
--
作者：
Koji M. Kobayashi
在线调度是最基本的在线问题之一。我们以在线方式给出一系列作业，并且必须将它们分配给m（≥1）个等效处理器中的一个。在释放时间r (j)处给出处理时间p (j)的每个作业j。算法决定使用哪个处理器来处理j，并且必须在所选处理器的r (j)时间之后将其调度到p (j)时间。已经提出了许多标准来评估调度算法的性能，Muthukrishnan等人（FOCS 1999和SIAM Journal on Computing 34(2), 2005）在目标函数中使用了作业j的延伸，其定义为j在系统中花费的时间与其处理时间p (j)的比率。算法的成本是调度所有给定作业的总拉伸，我们的目标是将其最小化。Muthukrishnan等人考虑了允许抢占的情况，即任何作业都可以在进程中停止，一段时间后进程可以恢复。在本文中，我们展示了如何构造实例来获得每个m的竞争比的各种下界。在实例中，m个作业在恶意选择的时间之后在足够大的时间跨度内有规律地给定。给定作业的处理时间取决于作业“突发”开始时未完成作业的剩余处理时间。我们证明了在这种情况下，在爆发之前完成的工作的长度几乎不影响竞争比的评估。此外，我们为每个m提供了一个在突发前给定的作业序列。然后，我们可以使用实例改进每个m的任何确定性在线算法的先前下界。例如，我们分别得到m= 1、2和∞时的下界为1.228、1.257和21/17≈1.235。此外，我们得到了所有m的任意随机在线算法的第一个非平凡下界。
Online scheduling is one of the most basic online problems. We are given a sequence of jobs in an online fashion, and they must be assigned to one of m (≥ 1) equivalent processors. Each job j with the processing time p (j) is given at the release time r (j). An algorithm decides which processor is used to process j and must schedule it for time p (j) after time r (j) on the chosen processor. Many criteria have been proposed to evaluate the performance of scheduling algorithms, and Muthukrishnan et al.(FOCS 1999 and SIAM Journal on Computing 34 (2), 2005) used the stretch of a job j in an objective function, which is defined as the ratio of the amount of time which j spends in the system to its processing time p (j). The cost of an algorithm is the total stretch to schedule all the given jobs, and our goal is to minimize it. Muthukrishnan et al. considered the case in which preemption is allowed, that is, any job can be stopped during the process and after a while the process can resume. In this paper, we show how to construct instances to obtain various lower bounds on the competitive ratio for each m. In the instances, m jobs are given regularly for a sufficiently large time span after a maliciously chosen time. The processing times of the given jobs are taken depending on the remaining processing times of uncompleted jobs at the start time of the “burst” of jobs. We prove that for the instances, the stretch of a job completed before the burst hardly affects the evaluation of a competitive ratio. Further, we provide a job sequence given before the burst for each m. Then, we can improve the previous lower bounds for any deterministic online algorithm for each m using the instances. For example, we obtain lower bounds of 1.228, 1.257 and 21/17≈ 1.235 for m= 1, 2 and∞, respectively. Moreover, we obtain the first non-trivial lower bounds for any randomized online algorithm for all m.