带等级约束的多维任务调度问题
Multidimensional Task Scheduling Problem under a Grade of Service Provision
摘要: 根据向量调度问题和带等级约束的任务调度问题，我们提出了带等级约束的多维任务调度问题。我们首先设计了一个5 d/4-近似算法。然后，我们给出一个动态规划算法和一个完全多项式时间近似方案。
Abstract: According to vector scheduling problem and task scheduling problem under a grade of service provision, we propose multidimensional task scheduling problem under a grade of service provision. We first design a 5 d/4 approximation algorithm. Then, we give a dynamic programming algorithm and a fully polynomial time approximation scheme.
文章引用：代兵飞. 带等级约束的多维任务调度问题[J]. 理论数学, 2018, 8(5): 480-485. https://doi.org/10.12677/PM.2018.85064

参考文献

[1] Graham, R.L., et al. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Dis-crete Mathematics, 5, 287-326. [Google Scholar] [CrossRef] 
[2] Chekuri, C. and Khanna, S. (2004) On Multidimensional Packing Problems. SIAM Journal on Computing, 33, 837-851. [Google Scholar] [CrossRef] 
[3] Bansal, N., Vredeveld, T. and Zwaan, R.V.D. (2014) Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. LATIN 2014: Theoretical Informatics, Springer, Berlin Heidel-berg.
[4] Zhu, X., Li, Q., Mao, W., et al. (2014) Online Vector Scheduling and Generalized Load Balancing. Journal of Parallel & Distributed Computing, 74, 2304-2309. [Google Scholar] [CrossRef] 
[5] Meyerson, A., Roytman, A. and Tagiku, B. (2013) Online Multidimensional Load Balancing. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, Berlin, Heidelberg, 287-302.
[6] Im, S., Kell, N., Kulkarni, J., et al. (2014) Tight Bounds for Online Vector Scheduling. 525-544.
[7] Hwang, H.C., Chang, S.Y. and Lee, K. (2004) Parallel Machine Scheduling under a Grade of Service Provision. Computers & Operations Research, 31, 2055-2061. [Google Scholar] [CrossRef] 
[8] Glass, C.A. and Kellerer, H. (2007) Parallel Machine Scheduling with Job Assignment Restrictions. Naval Research Logistics (NRL), 54, 250-257. [Google Scholar] [CrossRef] 
[9] Ou, J., Leung, J.Y.T. and Li, C.L. (2008) Scheduling Parallel Machines with Inclusive Processing Set Restrictions. Naval Research Logistics (NRL), 55, 328-338. [Google Scholar] [CrossRef] 
[10] Li, W., Li, J. and Zhang, T. (2012) Two Approximation Schemes for Scheduling on Parallel Machines under a Grade of Service Provision. Asia-Pacific Journal of Operational Research, 29, 1250029. [Google Scholar] [CrossRef] 
[11] Liu, X., Li, W. and Zhang, X. (2018) Strategy-Proof Mechanism for Provi-sioning and Allocation Virtual Machines in Heterogeneous Clouds. IEEE Transactions on Parallel & Distributed Systems, 99, 1650-1663.

为你推荐