A linear compound algorithm for uniform machine scheduling

被引：9
作者：
Burkard, RE
He, Y
Kellerer, H
机构：
[1] Graz Tech Univ, Inst Math, A-8010 Graz, Austria
[2] Graz Univ, Inst Stat Okonometrie & Operat Res, A-8010 Graz, Austria
[3] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China
来源：
COMPUTING | 1998年 / 61卷 / 01期
关键词：
uniform machine scheduling; worst-case analysis; analysis of algorithm;
D O I：
10.1007/BF02684446
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we consider the classical two uniform machine scheduling problem. We present a compound algorithm which consists of three Greedy-like subprocedures running independently. We prove that the algorithm has a worst-case bound of 7/6 and runs in linear time.
引用
收藏
页码：1 / 9
页数：9
相关论文
共 10 条
[1]  
BURKARD RE, 1997, 116 SFB TU GRAZ I MA
[2]   ANALYSIS OF A COMPOUND BIN PACKING ALGORITHM [J].
FRIESEN, DK ;
LANGSTON, MA .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (01) :61-79
[3]  
Gonzalez T., 1977, SIAM Journal on Computing, V6, P155, DOI 10.1137/0206013
[4]  
HE Y, UNPUB LINEAR COMPOUN
[5]   A POLYNOMIAL-APPROXIMATION SCHEME FOR SCHEDULING ON UNIFORM PROCESSORS - USING THE DUAL APPROXIMATION APPROACH [J].
HOCHBAUM, DS ;
SHMOYS, DB .
SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :539-551
[6]   EXACT AND APPROXIMATE ALGORITHMS FOR SCHEDULING NONIDENTICAL PROCESSORS [J].
HOROWITZ, E ;
SAHNI, S .
JOURNAL OF THE ACM, 1976, 23 (02) :317-327
[7]   CALCULATION AND PRECISION-MEASUREMENTS OF DISTORTED RF EMF IN A RECTANGULAR CAVITY RESONATOR [J].
KOHLSMANN, S ;
HETSCHER, M ;
KRAMER, KD .
BIOELECTROCHEMISTRY AND BIOENERGETICS, 1995, 37 (01) :1-4
[8]  
KOVALEV MM, 1991, 9104 CORR U WAT
[9]   WORST-CASE ANALYSIS OF GREEDY ALGORITHMS FOR THE UNBOUNDED KNAPSACK, SUBSET-SUM AND PARTITION PROBLEMS [J].
LAI, TC .
OPERATIONS RESEARCH LETTERS, 1993, 14 (04) :215-220
[10]   A parametric worst case analysis of the LPT heuristic for two uniform machines [J].
Mireault, P ;
Orlin, JB ;
Vohra, RV .
OPERATIONS RESEARCH, 1997, 45 (01) :116-125
1