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

• • 上一篇

收稿日期:2022-07-26 修回日期:2022-10-26 出版日期:2024-12-30 发布日期:2024-12-12
通讯作者: 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

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

中图分类号:

90B35
68M20

. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价