In this paper, we consider the problem of semi-online machine covering on three machines with two hierarchies, whose objective is to maximize the minimum machine load. Since there is no online algorithm with bounded competitive ratio for the online machine covering problem, we consider the semi-online case where the processing times of all jobs lie in [1, α]. When there are one machine of hierarchy 1 and two machines of hierarchy 2, we design an optimal online algorithm with a competitive ratio of 1 + α. When there are two machines of hierarchy 1 and one machine of hierarchy 2, we give an optimal online algorithm with a competitive ratio of 1 + 2α.
Man Xiao, Yu-Fei Du, Wei-Dong Li, Jin-Hua Yang
. Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times[J]. Journal of the Operations Research Society of China, 2024
, 12(4)
: 1126
-1138
.
DOI: 10.1007/s40305-023-00477-1
[1] Bar-Noy, A., Freund, A., Naor, J.: On-line load Balancing in a hierarchical server topology. SIAM J. Comput. 31(2), 527-549(2001)
[2] Zhang, A., Jiang, Y., Tan, Z.: Online parallel machines scheduling with two hierarchies. Theoret. Comput. Sci. 410, 3597-3605(2009)
[3] Park, J., Chang, S.Y., Lee, K.: Online and semi-online scheduling of two machines under a grade of service provision. Oper. Res. Lett. 34(6), 692-696(2006)
[4] Chen, Y., Chen, T., Liu, L., Jiang, Y., Tan, Z., Zhang, A.: Online scheduling with unit processing times and processing set restrictions. J. Oper. Res. Soc. China 7, 475-484(2019)
[5] Jia, Xu., Liu, Z.: An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints. J. Oper. Res. Soc. China 4, 371-377(2016)
[6] Cai, S., Liu, K.: Online scheduling on two parallel identical machines under a grade of service provision. J. Oper. Res. Soc. China (2020). https://doi.org/10.1007/s40305-020-00325-6
[7] Woeginger, G.J.: A polynomial time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20, 149-154(1997)
[8] He, Y.: The optimal on-line parallel machine scheduling. Comput. Math. Appl. 39, 117-121(2000)
[9] Azar, Y., Epstein, L.: On-line machine covering. J. Sched. 1, 67-77(1998)
[10] Tan, Z., Wu, Y.: Optimal semi-online algorithms for machine covering. Theoret. Comput. Sci. 372(1), 69-80(2007)
[11] He, Y.: Semi-on-line scheduling problems for maximizing the minimum machine completion time. Acta Math. Appl. Sin. 17, 107-113(2001)
[12] Chassid, O., Epstein, L.: The hierarchical model for load balancing on two machines. J. Comb. Optim. 15(4), 305-314(2008)
[13] Wu, Y., Cheng, T.C.E., Ji, M.: Optimal algorithms for semi-online machine covering on two hierarchical machines. Theoret. Comput. Sci. 531(6), 37-46(2014)
[14] Luo, T., Xu, Y.: Semi-online hierarchical load balancing problem with bounded processing times. Theoret. Comput. Sci. 607, 75-82(2015)
[15] Wu, G., Li, W.: Semi-online Machine Covering on Two Hierarchical Machines with Discrete Processing Times. In: Li, L., Lu, P., He, K. (eds.) Theoretical computer science. NCTCS 2018. Communications in computer and information science, vol. 882, pp. 1-7. Springer, Singapore (2018)
[16] Xiao, M., Wu, G., Li, W.: Semi-online Machine Covering on Two Hierarchical Machines with Known Total Size of Low-Hierarchy Jobs. In: Sun, X., He, K., Chen, X. (eds.) Theoretical computer science. NCTCS 2019. Communications in computer and information science, vol. 1069, pp. 95-108. Springer, Singapore (2019)
