In this paper, we consider
online scheduling for jobs with arbitrary release times on the parallel uniform
machine system. An algorithm with competitive ratio of 7.4641 is addressed,
which is better than the best existing result of 12.
References
[1]
Cho, Y. and Sahni, S. (1980) Bounds for List Schedules on Uniform Processors. SIAM Journal on Computing, 9, 91-103. https://doi.org/10.1137/0209007
[2]
Epstein, L., Noga, J., Seiden, S.S., Sgall, J. and Woeginger, G.J. (2001) Randomized on-Line Scheduling on Two Uniform Machines. Journal of Scheduling, 4, 71-92.
https://doi.org/10.1002/jos.60
[3]
Cai, S.Y. and Yang, Q.F. (2012) Online Scheduling on Three Uniform Machines. Discrete Applied Mathematics, 160, 291-302.
https://doi.org/10.1016/j.dam.2011.10.001
[4]
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S. and Waarts, O. (1997) On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of the ACM, 44, 486-504. https://doi.org/10.1145/258128.258201
[5]
Berman, P., Charikar, M. and Karpinski, M. (2000) On-Line Load Balancing for Related Machines. Journal of Algorithms, 35, 108-121.
https://doi.org/10.1006/jagm.1999.1070
[6]
Li, R.H. and Shi, L.J. (1998) An on-Line Algorithm for Some Uniform Processor Scheduling. SIAM Journal on Computing, 27, 414-422.
https://doi.org/10.1137/S0097539799527969
[7]
Cheng, T.C.E., Ng, C. and Kotov, V. (2006) A New Algorithm for Online Uniform-Machine Scheduling to Minimize the Makespan. Information Processing Letters, 99, 102-105.
[8]
Li, R.H. and Huang, H.C. (2004) On-Line Scheduling for Jobs with Arbitrary Release Times. Computing, 73, 79-97. https://doi.org/10.1007/s00607-004-0067-1
[9]
Li, R.H. and Huang, H.C. (2007) Improved Algorithm for a Generalized On-line Scheduling Problem on Identical Machines. European Journal of Operations Research, 176, 643-652. https://doi.org/10.1016/j.ejor.2005.06.061
[10]
Li, K., Zhang, H., Cheng, B. and Pardalos, P. (2018) Uniform Parallel Machine Scheduling Problem with Fixed Machine Cost. Optimization Letter, 12, 73-86.
https://doi.org/10.1007/s11590-016-1096-3
[11]
Yin, Y., Chen, Y., Qin, K. and Wang, D. (2019) Two-Agent Scheduling on Unrelated Parallel Machines with Total Completion Time and Weighted Number of Tardy Jobs Criteria. Journal of Scheduling, 22, 315-333.
https://doi.org/10.1007/s10951-018-0583-z
[12]
Cheng, X., Li, R. and Zhou, Y. (2016) On-Line Scheduling for Jobs with Arbitrary Release Times on Parallel Related Uniform Machines. Intelligent Information Management, 8, 98-102. https://doi.org/10.4236/iim.2016.84008
