WORST CASE BOUND OF AN LRF SCHEDULE FOR THE MEAN WEIGHTED FLOW-TIME PROBLEM

被引：88

作者：

KAWAGUCHI, T

KYAN, S

机构：

[1] Univ of the Ryukyus, Jpn, Univ of the Ryukyus, Jpn

来源：

SIAM JOURNAL ON COMPUTING | 1986年 / 15卷 / 04期

关键词：

COMPUTER PROGRAMMING - Algorithms - SCHEDULING;

D O I：

10.1137/0215081

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper studies the problem of scheduling a set of n independent tasks on m identical processors so as to minimize mean weighted flow-time. The problem is known to be NP-complete for m greater than equivalent to 2 and to be NP-complete in the strong sense for m arbitrary. The worst case behavior of a heuristic algorithm which requires time O(n log n) is investigated, and it is shown that the mean weighted flow-time obtained by the algorithm does not exceed ( ROOT 2 plus 1)/2 congruent 1. 207 times that of an optimal schedule. Moreover the bound ( ROOT 2 plus 1)/2 is best possible.

引用

页码：1119 / 1129

页数：11

共 7 条

[1]

Chandra A. K., 1975, SIAM Journal on Computing, V4, P249, DOI 10.1137/0204021

[2]

Coffman E.G., 1976, COMPUTER JOB SHOP SC

[3] BOUNDS FOR THE OPTIMAL SCHEDULING OF NORMAL-JOBS ON META-PROCESSORS [J].