Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

doi:10.1007/s40305-023-00477-1

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (4): 1126-1138.doi: 10.1007/s40305-023-00477-1

Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

Man Xiao¹, Yu-Fei Du^1,2, Wei-Dong Li¹, Jin-Hua Yang²

1 School of Mathematics and Statistics, Yunnan University, Kunming 650504, Yunnan, China;
2 Dianchi College of Yunnan University, Kunming 650228, Yunnan, China

Received:2022-07-26 Revised:2022-10-26 Online:2024-12-30 Published:2024-12-12
Contact: Wei-Dong Li, Man Xiao, Yu-Fei Du, Jin-Hua Yang E-mail:weidongmath@126.com;man1205@163.com;285307154@qq.com;25277375@qq.com
Supported by:
This work was supported by the National Natural Science Foundation of China (No. 12071417).

Abstract

Abstract: 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α.

Key words: Semi-online, Machine covering, Hierarchy, Competitive ratio

CLC Number:

90B35
68M20

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.

TrendMD

References

[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)

Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[2]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.
[3]	Wen-Hua Li, Xing Chai. Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.
[4]	Ji Tian · Ruyan Fu · Jinjiang Yuan. Online Over Time Scheduling on Parallel-Batch Machines: A Survey [J]. Journal of the Operations Research Society of China, 2014, 2(4): 445-.