科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper studies the online machine minimization problem, where the jobs have real release times, uniform processing times and a common deadline. We investigate how the lookahead ability improves the performance of online algorithms. Two lookahead models are studied, that is, theadditive lookaheadand themultiplicative lookahead. At any timet, the online algorithm knows all the jobs to be released before time t + L (or beta center dot t) in the additive (or multiplicative) lookahead model. We propose a e/alpha(e-1)+1-competitive online algorithm with the additive lookahead, where alpha = L/T <= 1 and T is the common deadline of the jobs. For the multiplicative lookahead, we provide an online algorithm with a competitive ratio of beta e/(beta-1)e+1, where beta >= 1. Lower bounds are also provided for both of the two models, which show that our algorithms are optimal for two extreme cases, that is, alpha = 0 (or beta = 1) and alpha = 1 (or beta -> infinity), and remain a small gap for the cases in between. Particularly, for alpha = 0 (or beta = 1), the competitive ratio ise, which corresponds to the problem without lookahead. For alpha = 1 (or beta -> infinity), the competitive ratio is 1, which corresponds to the offline version (with full information).
-
单位西安交通大学
