No Access

A Best Possible Online Algorithm for the Parallel-Machine Scheduling to Minimize the Maximum Weighted Completion Time

Wenjie Li

School of Mathematical Sciences, Luoyang Normal University, Luoyang, Henan 471022, P. R. China

https://doi.org/10.1142/S021759591550030XCited by:14 (Source: Crossref)

Abstract

In this paper, we consider the online scheduling on m identical machines in which jobs arrive over time. The goal is to determine a nonpreemptive schedule that minimizes the weighted makespan, i.e., the maximum weighted completion time of jobs. When m = 1, we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3. For the case in which m ≥ 1, and all jobs have a common processing time p > 0, we obtain a best possible online algorithm with a competitive ratio of .

Keywords:

References

Y. H. Cai , Q. Feng and W. J. Li , Asia-Pacific Journal of Operational Research 29 , 1 ( 2012 ) . Link, Web of Science, Google Scholar
B. Chen and A. P. A. Vestjens , Operations Research Letters 21 , 165 ( 1997 ) . Crossref, Web of Science, Google Scholar
B. Chen, C. N. Potts and G. J. Woeginger, Handbook of Combinatorial Optimization 3 (Kluwer Academic, Dordrecht, 1998) pp. 21–169. Google Scholar
Q. Feng and J. J. Yuan , OR Transactions 11 , 121 ( 2007 ) . Google Scholar
M. R. Garey and D. S. Johnson , Journal of the Association for Computing Machinery 25 , 499 ( 1978 ) . Crossref, Web of Science, Google Scholar
R. L. Graham , Bell System Technical Journal 45 , 1563 ( 1966 ) . Crossref, Web of Science, Google Scholar
R. L. Graham , SIAM Journal on Applied Mathematics 17 , 263 ( 1969 ) . Google Scholar
Y. Huo and J. Y.-T. Leung , SIAM Journal on Computing 34 , 743 ( 2005 ) . Crossref, Web of Science, Google Scholar
M. Liu et al. , Asia-Pacific Journal of Operational Research 31 , 1450038 ( 2014 ) . Link, Web of Science, Google Scholar
R. McNaughton , Management Science 6 , 1 ( 1959 ) . Crossref, Web of Science, Google Scholar
J. Noga and S. S. Seiden , Theoretical Computer Science 268 , 133 ( 2001 ) . Crossref, Web of Science, Google Scholar
Q. Q. Nong , T. C. E. Cheng and C. T. Ng , European Journal of Operational Research 215 , 39 ( 2011 ) . Crossref, Web of Science, Google Scholar
K. Pruhs , J. Sgall and E. Tong , Handbook of Scheduling: Algorithm, Model, and Performance Analysis , ed. J.Y.-T. Leung ( Chapman & Hall/CRC Press , Boca Raton , 2004 ) . Google Scholar
Vestjeans, APA (1997). On-line machine scheduling. Ph.D. Thesis, Eindhove University of Technology, Netherlands . Google Scholar
J. L. Yuan , W. H. Li and J. J. Yuan , Theoretical Computer Science 457 , 174 ( 2012 ) . Crossref, Web of Science, Google Scholar