具有先序约束的平行机排序问题  

Parallel Machine Scheduling Problem with Precedence Constraints

作　　者：陈雪 廖礼琴 张同全[2] 

机构地区：[1]云南民族大学数学与计算机科学学院,云南 昆明 [2]云南民族大学预科教育学院,云南 昆明

出　　处：《应用数学进展》2021年第11期3693-3698,共6页Advances in Applied Mathematics

摘　　要：根据财务系统中的回避原则,构造了具有先序约束的平行机排序问题的模型,目标函数为最小化最大负载,证明了具有先序约束的平行机排序问题是一个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.

关 键 词：平行机 排序 先序约束 近似算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]