具有先序约束的平行机排序问题
Parallel Machine Scheduling Problem with Precedence Constraints
DOI: 10.12677/AAM.2021.1011392, PDF,   
作者: 陈 雪, 廖礼琴：云南民族大学数学与计算机科学学院，云南 昆明；张同全*：云南民族大学预科教育学院，云南 昆明
关键词: 平行机；排序；先序约束；近似算法；Parallel Identical Machines； Scheduling； Precedence Constraints； Approximation Algorithms
摘要: 根据财务系统中的回避原则，构造了具有先序约束的平行机排序问题的模型，目标函数为最小化最大负载，证明了具有先序约束的平行机排序问题是一个NP-完备问题。为之设计了LPTM算法，并分析了其近似比为3-1/m。
Abstract: According to the avoidance principle in the financial system, a model of the parallel machine scheduling problem with precedence constraints is constructed, and the objective function is to minimize the maximum load, which is proved that the parallel machine scheduling problem with precedence constraints is an NP-complete problem. We design the LPTM algorithm and analyze its approximate ratio to 3-1/m.
文章引用：陈雪, 廖礼琴, 张同全. 具有先序约束的平行机排序问题[J]. 应用数学进展, 2021, 10(11): 3693-3698. https://doi.org/10.12677/AAM.2021.1011392

参考文献

[1] Graham, R.L., Lawler, E.L., Lenstra, J.K., et al. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. [Google Scholar] [CrossRef] 
[2] Prot, D. and Bellenguez-Morineau, O. (2018) A Survey on How the Structure of Precedence Constraints May Change the Complexity Class of scheduling Problems. Journal of Scheduling, 21, 3-16. [Google Scholar] [CrossRef] 
[3] Báez, S. and Angel-Belloa, F. (2019) A Hybrid Metaheuristic Algorithm for a Parallel Machine Scheduling Problem with Dependent Setup Times. Computers & Industrial Engineering, 131, 295-305. [Google Scholar] [CrossRef] 
[4] 柴幸. 带有工件约束的平行机排序问题的近似算法研究[D]: [博士学位论文]. 郑州: 郑州大学, 2019.
[5] Jiang, X., Lee, K. and Pinedo, L. (2021) Ideal Schedules in Parallel Machine Settings. European Journal of Operational Research, 290, 405-806. [Google Scholar] [CrossRef] 
[6] Dolev, D. and Warmuth, M.K. (1984) Scheduling Precedence Graphs of Bounded Height. Journal of Algorithms, 5, 48-59. [Google Scholar] [CrossRef] 
[7] Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics, 17, 416-429. [Google Scholar] [CrossRef] 
[8] David, P.W. and David, B.S. (2010) The Design of Approximation Algorithms. Cambridge University Press, New York, 39-42.

为你推荐