Abstract
This paper considers classical online scheduling problems on uniform machines. We show the tight competitive ratio of LS for any combinations of speeds of three machines. We prove that LS is optimal when s 3 ≥ s 2 ≥ s 1 = 1 and \({s_3^2\geq s_2^2+s_2s_3+s_2}\), where s 1, s 2, s 3 are the speeds of three machines. On the other hand, LS can not be optimal for all combinations of machine speeds, even restricted to the case of 1 = s 1 = s 2 < s 3. For m ≥ 4 machines, LS remains optimal when one machine has very large speed, and the remaining machines have the same speed.
References
Berman P., Charikar M., Karpinski M.: On-line load balancing for related machines. J. Algorithms 35, 108–121 (2000)
Chen B., van Vliet A., Woeginger G.J.: New lower and upper bounds for on-line scheduling. Oper. Res. Lett. 16, 221–230 (1994)
Chen B., van Vliet A., Woeginger G.J.: An optimal algorithm for preemptive on-line scheduling. Oper. Res. Lett. 18, 127–131 (1995)
Cheng T.C.E., Ng C.T., Kotov V.: A new algorithm for online uniform-machine scheduling to minimize the makespan. Inform. Process. Lett. 99, 102–105 (2006)
Cho Y., Sahni S.: Bounds for list schedules on uniform processors. SIAM J. Comput. 9, 91–103 (1980)
Ebenlendr T., Jawor W., Sgall J.: Preemptive online scheduling: optimal algorithms for all speeds. Algorithmica 53, 504–522 (2009)
Epstein L., Noga J., Seiden S., Sgall J., Woeginger G.J.: Randomized on-line scheduling on two uniform machines. J. Scheduling 4, 71–92 (2001)
Faigle U., Kern W., Turan G.: On the performance of on-line algorithm for particular problem. Acta Cybern. 9, 107–119 (1989)
Graham R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)
Kovács A.: Tighter approximation bounds for LPT scheduling in two special cases. J. Discrete Algorithms 7, 327–340 (2009)
Li R.H., Shi L.J.: An online algorithm for some uniform professor scheduling. SIAM J. Comput. 27, 414–422 (1998)
Pardalos, P.M., Du, D.-Z. (eds): Handbook of Combinatorial Optimization. Kluwer, Dordrecht (1998)
Pardalos, P.M., Resende, M. (eds): Handbook of Applied Optimization. Oxford University Press, Oxford (2002)
Rudin J.F. III, Chandrasekaran R.: Improved bound for the online scheduling problem. SIAM J. Comput. 32, 717–735 (2003)
Wen J., Du D.: Preemptive on-line scheduling for two uniform processors. Oper. Res. Lett. 23, 113–116 (1998)
Xu, Y., Zhang, W., Zheng, F.: Optimal algorithms for the online time series search problem. In: Du, D.-Z., Hu, X., Pardalos, P. M. (eds.) Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 5573, pp. 322–333 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Han, F., Tan, Z. & Yang, Y. On the optimality of list scheduling for online uniform machines scheduling. Optim Lett 6, 1551–1571 (2012). https://doi.org/10.1007/s11590-011-0335-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0335-x