Acta Mathematicae Applicatae Sinica, English Series 2012, Vol. 28 Issue (1) :111-116    DOI: 10.1007/s10255-012-0137-7
 ARTICLES Adv Search << | >>
A Better Semi-online Algorithm for Q3/s1 = s2 ≤ s3/Cmin with the Known Largest Size
Sheng-yi CAI1,2, Qi-fan YANG1
1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China;
2. School of Mathematics & Information Science, Wenzhou University, Wenzhou 325035, China
 Download: PDF (1KB)   HTML (1KB)   Export: BibTeX or EndNote (RIS)      Supporting Info
Abstract 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 = rt = 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, (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.
 Service Email this article Add to my bookshelf Add to citation manager Email Alert RSS Articles by authors
Keywordsanalysis of algorithms   scheduling   machine covering   semi-online   competitive ratio
Abstract： 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 = rt = 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, (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.
  Azar, Y., Epstein, L. Online machine covering. Algorithms-ESA’97, Lecture Notes in Computer Science 1284, Springer-Verlag, 1997, 23-36 Cao, S.J., Tan, Z.Y. Online uniform machine covering with the known largest size. Progress in Natural Science, 17(11): 1271-1278 (2007)  Deuermeyer, B.L., Friesen, D.K., Langston, M.A. Scheduling to maximize the minimum processing finish time in a multiprocessor system. SIAM J. Algebraic Discrete Methods, 3: 190-196 (1982)  Epstein, L. Tight bounds for bandwidth allocation on two links. Discrete Applied Mathematics, 148(2): 181-188 (2005)  Epstein, L., Ye, D.H. Semi-online scheduling with “end of sequence” information. Journal of Combinatorial Optimation, 14(1): 45-61 (2007)  Kellerer, H., Kotov, V., Speranza, M.C., Tuza, Z. Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5): 235-242 (1997)  Luo, R.Z., Sun, S.J. Semi-on-line scheduling problem for maximizing the minimum machine completion time on three special uniform machines. Asia-Pacific Journal of Operational Research, 22(2): 229-237 (2005)  Tan, Z.Y., Cao, S.J. Semi-online machine covering on two uniform machines with known total size. Computing, 78(4): 369-378 (2006)  Tan, Z.Y., Chen, S.X. Online machine covering on uniform machines. Technique Report, Zhejiang University, 2007  Woeginger, G. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20: 149-154 (1999)