A Better Semi-online Algorithm for Q3/s_1=s_2≤s_3/C_(min) with the Known Largest Size  

作　　者：Sheng-yi CAI Qi-fan YANG 

机构地区：[1]Department of Mathematics,Zhejiang University,Hangzhou 310027,China [2]School of Mathematics&Information Science,Wenzhou University,Wenzhou 325035,China

出　　处：《Acta Mathematicae Applicatae Sinica》2012年第1期111-116,共6页应用数学学报（英文版）

基　　金：Supported by the National Natural Science Foundation of China (No. 60674071)

摘　　要：This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.

关 键 词：analysis of algorithms SCHEDULING machine covering SEMI-ONLINE competitive ratio 

分 类 号：O223[理学—运筹学与控制论] TF704.7[理学—数学]