|
|
具有先序约束的平行机排序问题
|
Abstract:
根据财务系统中的回避原则，构造了具有先序约束的平行机排序问题的模型，目标函数为最小化最大负载，证明了具有先序约束的平行机排序问题是一个NP-完备问题。为之设计了LPTM算法，并分析了其近似比为3-1/m。
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.
| [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.
https://doi.org/10.1016/S0167-5060(08)70356-X |
| [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.
https://doi.org/10.1007/s10951-017-0519-z |
| [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.
https://doi.org/10.1016/j.cie.2019.03.051 |
| [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. https://doi.org/10.1016/j.ejor.2020.08.010 |
| [6] | Dolev, D. and Warmuth, M.K. (1984) Scheduling Precedence Graphs of Bounded Height. Journal of Algorithms, 5, 48-59. https://doi.org/10.1016/0196-6774(84)90039-7 |
| [7] | Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039 |
| [8] | David, P.W. and David, B.S. (2010) The Design of Approximation Algorithms. Cambridge University Press, New York, 39-42. |
