摘要
根据财务系统中的回避原则,构造了具有先序约束的平行机排序问题的模型,目标函数为最小化最大负载,证明了具有先序约束的平行机排序问题是一个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.
出处
《应用数学进展》
2021年第11期3693-3698,共6页
Advances in Applied Mathematics
