No Access

SEMI-ONLINE MACHINE COVERING

SHENG-YI CAI

School of Mathematics and Information Science, Wenzhou University, Wenzhou 325035, P. R. China

https://doi.org/10.1142/S0217595907001255Cited by:4 (Source: Crossref)

Abstract

This paper investigates two different semi-online versions of the machine covering, which is the problem of assigning a set of jobs to a system of m(m ≥ 3) identical parallel machines so as to maximize the earliest machine completion time. In the first case, we assume that the largest processing times is known in advance. In the second case, we assume that the total processing times of all jobs is known in advance. For each version we propose a semi-online algorithm and investigate its competitive ratio. The competitive ratio of each algorithm is , which is shown to be the best possible competitive ratio for each semi-online problem.

Keywords:

References

Y. Azar and L. Epstein, Algorithms-ESA'97, Lecture Notes in Computer Science 1284 (Springer Verlag, 1997) pp. 23–36. Crossref, Google Scholar
J. Csirik, H. Kellerer and G. Woeginger, Oper. Res. Letters 11, 281 (1992), DOI: 10.1016/0167-6377(92)90004-M. Crossref, Web of Science, Google Scholar
B. L. Deuermeyer and D. K. Friesen, Math. Oper. Rea. 6, 74 (1981). Web of Science, Google Scholar
B. L. Deuermeyer, D. K. Friesen and M. A. Langston, SIAM J. Algebraic Discrete Methods 3, 190 (1982), DOI: 10.1137/0603019. Crossref, Web of Science, Google Scholar
T. Ebenlendr et al. , A note on semi-online machine covering , The 3rd Workshop on Approximation and Online Algorithms , Lecture Notes in Computer Science ( 2005 ) . Google Scholar
L. Epstein and L. M. Favrholdt, Optimal non-preemptive semi-on-line scheduling on two related machines, Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS'2002) (2002) pp. 245–256. Google Scholar
L. Epstein and L. M. Favrholdt, Oper. Res. Letters 30(4), 269 (2002), DOI: 10.1016/S0167-6377(02)00179-7. Crossref, Web of Science, Google Scholar
Y. He, Computers and Mathematics with Applications 17(1), 107 (2000). Google Scholar
Y. He, Acta Mathematicae Applicatae Sinica 17(1), 107 (2001). Google Scholar
Y. He and S. Y. Cai, Journal of Computer Science and Technology 39, 117 (2002). Web of Science, Google Scholar
Y. He and Z. Y. Tan, Journal of Combinatorial Optimization 6, 199 (2002), DOI: 10.1023/A:1013855712183. Crossref, Web of Science, Google Scholar
Y. He and Z. Y. Tan, Asia-Pacific Journal of Operational Research 20, 31 (2003). Web of Science, Google Scholar
Y. He and G. C. Zhang, Computing 62, 179 (1999), DOI: 10.1007/s006070050020. Crossref, Web of Science, Google Scholar
H. Kellereret al., Oper. Res. Letters 21, 235 (1997), DOI: 10.1016/S0167-6377(98)00005-4. Crossref, Web of Science, Google Scholar
S. Seiden, J. Sgall and G. Woeginger, Oper. Res. Letters 27, 215 (2000), DOI: 10.1016/S0167-6377(00)00053-5. Crossref, Web of Science, Google Scholar
Z. Y. Tan and Y. He, Oper. Res. Letters 28(5), 221 (2001), DOI: 10.1016/S0167-6377(01)00071-2. Crossref, Web of Science, Google Scholar
G. Woeginger, Oper. Res. Letters 20, 149 (1999), DOI: 10.1016/S0167-6377(96)00055-7. Crossref, Web of Science, Google Scholar
G. C. Zhang, Information Progressing Letters 61, 145 (1997), DOI: 10.1016/S0020-0190(97)00006-9. Crossref, Web of Science, Google Scholar