A BETTER LOWER-BOUND FOR ONLINE SCHEDULING

被引：56

作者：

BARTAL, Y

KARLOFF, H

RABANI, Y

机构：

[1] TEL AVIV UNIV,SCH MATH,DEPT COMP SCI,IL-69978 TEL AVIV,ISRAEL

[2] GEORGIA INST TECHNOL,COLL COMP,ATLANTA,GA 30332

[3] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 50卷 / 03期

关键词：

Competitive ratio - Lower bound - Online scheduling;

D O I：

10.1016/0020-0190(94)00026-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the completion time of the last job. In the on-line version, as soon as a job arrives, it must be assigned immediately to one of the m machines. We study the competitive ratio of the best algorithm for m-machine scheduling. The largest prior lower bound was that if m greater-than-or-equal-to 4, then every algorithm has a competitive ratio at least 1 + 1 / square-root 2 almost-equal-to 1.707. We show that if m greater-than-or-equal-to 3454, then the competitive ratio of every algorithm exceeds 1.837. The best upper bound on the competitive ratio is now 1.945.

引用

页码：113 / 116

页数：4