Online uniform machine covering with the known largest size  

作　　者：Cao Shunjuan Tan Zhiyi 

机构地区：[1]Department of Mathematics, Zhejiang University, Hangzhou 310027, China [2]Department of Mathematics, Zhejiang Forestry University, Hangzhou 311300, China [3]State Key Laboratory of CAD ＆ CG, Zhejiang University, Hangzhou 310027, China

出　　处：《Progress in Natural Science:Materials International》2007年第11期1271-1278,共8页自然科学进展·国际材料（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant Nos 10671177 and 60021201);the Natural Science Foundation of Zhe-jiang Forestry University (Grant No 2006FK36)

摘　　要：This paper investigates the semi-online scheduling problem with the known largest size on two uniform machines. The objective is to maximize the minimum machine completion time. Both lower bounds and algorithms are given. Algorithms are optimal for the majority values of s≥1, where s is the speed ratio of the two machines. The largest gap between the competitive ratio and the lower bound is about 0.064. Moreover, the overall competitive ratio 2 matches the overall lower bound.This paper investigates the semi online scheduling problem with the known largest size on two uniform machines. The objective is to maximize the minimum machine completion time. Both lower bounds and algorithms are given. Algorithms are optimal for the majority values of s≥1, where s is the speed ratio of the two machines. The largest gap between the competitive ratio and the lower bound is about 0. 064. Moreover, the overall competitive ratio 2 matches the overall lower bound.

关 键 词：scheduling and covering uniform machine design and analysis of algorithm ONLINE competitive ratio. 

分 类 号：TB2[一般工业技术—工程设计测绘]