SPT is optimally competitive for uniprocessor flow

被引：4

作者：

Bunde, DP ^{[1
]}

机构：

[1] Univ Illinois, Dept Comp Sci, Urbana, IL 61801 USA

来源：

INFORMATION PROCESSING LETTERS | 2004年 / 90卷 / 05期

基金：

美国国家科学基金会; 美国能源部;

关键词：

algorithms; on-line algorithms; scheduling;

D O I：

10.1016/j.ipl.2004.02.013

中图分类号：

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

学科分类号：

0812 ;

摘要：

We show that the Shortest Processing Time (SPT) algorithm is (Delta + 1)/2-competitive for nonpreemptive uniprocessor total flow time with release dates, where Delta is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the (Delta + 1)-competitive ratio shown by Epstein and van Stee using different methods. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：233 / 238

页数：6

共 7 条

[1]

Awerbuch B., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P198, DOI 10.1145/301250.301304

[2]

Epstein L, 2001, LECT NOTES COMPUT SC, V2136, P338

[3]

EPSTEIN L, 2001, LECT NOTES COMPUT SC, V2138, P472

[4] Approximability and nonapproximability results for minimizing total flow time on a single machine [J].