应用数学学报(英文版)
HOME | ABOUT JOURNAL | EDITORIAL BOARD | FOR AUTHORS | SUBSCRIPTIONS | ADVERTISEMENT | CONTACT US
 
Acta Mathematicae Applicatae
Sinica, Chinese Series
 
   
   
Adv Search »  
Acta Mathematicae Applicatae Sinica, English Series 2012, Vol. 28 Issue (1) :111-116    DOI: 10.1007/s10255-012-0137-7
ARTICLES Current Issue | Next Issue | Archive | 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.  
Keywordsanalysis of algorithms,   scheduling,   machine covering,   semi-online,   competitive ratio     
Received: 2008-03-04;
Fund:

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

Cite this article:   
.A Better Semi-online Algorithm for Q3/s1 = s2 ≤ s3/Cmin with the Known Largest Size[J]  Acta Mathematicae Applicatae Sinica, English Serie, 2012,V28(1): 111-116
URL:  
http://www.applmath.com.cn/jweb_yysxxb_en/EN/10.1007/s10255-012-0137-7      或     http://www.applmath.com.cn/jweb_yysxxb_en/EN/Y2012/V28/I1/111
 
[1] Azar, Y., Epstein, L. Online machine covering. Algorithms-ESA’97, Lecture Notes in Computer Science 1284, Springer-Verlag, 1997, 23-36
[2] Cao, S.J., Tan, Z.Y. Online uniform machine covering with the known largest size. Progress in Natural Science, 17(11): 1271-1278 (2007)
[3] 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)
[4] Epstein, L. Tight bounds for bandwidth allocation on two links. Discrete Applied Mathematics, 148(2): 181-188 (2005)
[5] Epstein, L., Ye, D.H. Semi-online scheduling with “end of sequence” information. Journal of Combinatorial Optimation, 14(1): 45-61 (2007)
[6] 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)
[7] 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)
[8] Tan, Z.Y., Cao, S.J. Semi-online machine covering on two uniform machines with known total size. Computing, 78(4): 369-378 (2006)
[9] Tan, Z.Y., Chen, S.X. Online machine covering on uniform machines. Technique Report, Zhejiang University, 2007
[10] Woeginger, G. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20: 149-154 (1999)
没有找到本文相关文献
Copyright 2010 by Acta Mathematicae Applicatae Sinica, English Serie