对工件之间带有链优先约束的平行机排序问题进行了研究.优先约束是n条链Ti,1≤i≤n,n为任意实数,目标函数为极小化最大完工时间.问题Pm|chains|Cmax是强NP完备的,对于强NP完备问题不可能有全多项式时间的近似方案(FPTAS)(除非P=NP),找...对工件之间带有链优先约束的平行机排序问题进行了研究.优先约束是n条链Ti,1≤i≤n,n为任意实数,目标函数为极小化最大完工时间.问题Pm|chains|Cmax是强NP完备的,对于强NP完备问题不可能有全多项式时间的近似方案(FPTAS)(除非P=NP),找到一个多项式时间的近似方案(PTAS,Polyomial Time Approximation Scheme)是最好的结果.本文利用LPT算法,给出了问题Pm|chains|Cmax的一个多项式时间的近似方案(PTAS).展开更多
文摘对工件之间带有链优先约束的平行机排序问题进行了研究.优先约束是n条链Ti,1≤i≤n,n为任意实数,目标函数为极小化最大完工时间.问题Pm|chains|Cmax是强NP完备的,对于强NP完备问题不可能有全多项式时间的近似方案(FPTAS)(除非P=NP),找到一个多项式时间的近似方案(PTAS,Polyomial Time Approximation Scheme)是最好的结果.本文利用LPT算法,给出了问题Pm|chains|Cmax的一个多项式时间的近似方案(PTAS).