带等级约束的多重任务半在线调度问题
Multiple Tasks Semi-Online Scheduling Problem under a Grade of Service Provision
DOI: 10.12677/PM.2022.128145, PDF,    科研立项经费支持
作者: 代兵飞, 吴建丽：楚雄师范学院数学与计算机科学学院，云南 楚雄
关键词: 多重任务；半在线算法；竞争比；等级约束；Multiple Tasks； Semi-Online Algorithm； The Competitive Ratio； Grade of Service Provision
摘要: 在本文，我们研究两台平行机上带等级约束的多重任务调度问题，每个客户提交多个加工时间和等级相同的任务给机器加工。当低等级和高等级任务的加工时间之和分别已知时，本文提出了一个半在线算法，算法的竞争比为3/2。当低等级任务的加工时间之和已知时，本文也提出了一个半在线算法，算法的竞争比为3/2。
Abstract: In this paper, we study the multiple tasks semi-online scheduling problem with hierarchical con-straints on two parallel machines. Each customer submits multiple tasks with the same processing time and level to the machine. When the sum of processing time of low-level and high-level tasks is known respectively, this paper designs a semi-online algorithm with a competition ratio of 3/2. When the sum of processing time of low-level tasks is known, this paper also designs a semi-online algorithm with a competition ratio of 3/2.
文章引用：代兵飞, 吴建丽. 带等级约束的多重任务半在线调度问题[J]. 理论数学, 2022, 12(8): 1327-1332. https://doi.org/10.12677/PM.2022.128145

参考文献

[1] Hwang, H.-C., Chang, S.Y. and Lee, K. (2004) Parallel Machine Scheduling under a Grade of Service Provision. Computers and Operations Research, 31, 2055-2061. [Google Scholar] [CrossRef] 
[2] Ou, J., Leung, J.Y.-T. and Li, C.-L. (2008) Scheduling Parallel Machines with Inclusive Processing Set Restrictions. Naval Research Logistics, 55, 328-338.
[3] Woeginger, G.J. (2009) A Comment on Parallel-Machine Scheduling under a Grade of Service Provision to Minimize Makespan. Information Processing Letters, 109, 341-342. [Google Scholar] [CrossRef] 
[4] Park, J., Chang, S.Y. and Lee, K. (2006) Online and Semi-Online Scheduling of Two Machines under a Grade of Service Provision. Operations Research Letters, 34, 692-696. [Google Scholar] [CrossRef] 
[5] Jiang, Y. (2008) Online Scheduling on Parallel Machines with Two GoS Levels. Journal of Combinatorial Optimization, 16, 28-38.
[6] Chen, X., Ding, N., Dosa, G., Han, X. and Jiang, H. (2015) Online Hierarchical Scheduling on Two Machines with Known Total Size of Low-Hierarchy Jobs. International Journal of Computer Mathematics, 92, 873-881. [Google Scholar] [CrossRef] 
[7] Luo, T.B. and Xu, Y.F. (2014) Semi-Online Scheduling on Two Machines with GoS Levels and Partial Information of Processing Time. The Scientific World Journal, 2014, Article ID: 576234. [Google Scholar] [CrossRef] [PubMed]
[8] Li, W., Liu, X., Zhang, X. and Cai, X. (2015) A Task-Type-Based Algorithm for the Energy-Aware Profit Maximizing Scheduling Problem in Heterogeneous Computing Systems. Proceedings of the 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Shenzhen, 4-7 May 2015, 1107-1110. [Google Scholar] [CrossRef] 
[9] Tarplee, K.M., Maciejewski, A.A. and Siegel, H.J. (2014) Ener-gy-Aware Profit Maximizing Scheduling Algorithm for Heterogeneous Computing Systems. 14th IEEE/ACM Interna-tional Symposium on Cluster, Cloud and Grid Computing, Chicago, 26-29 May 2014, 595-603. [Google Scholar] [CrossRef] 

为你推荐