论文部分内容阅读
对工件之间带有链优先约束的平行机排序问题进行了研究，优先约束是n条链Ti，1≤i≤n，n为任意实数，目标函数为极小化最大完工时间，问题Pm｜chains｜Cmax是强NP完备的，对于强NP完备问题不可能有全多项式时间的近似方案（FPTAS）（除非P-NP），找到一个多项式时间的近似方案（PTAS，Polyomial Time Approximation Scheme）是最好的结果，本文利用LPT算法，给出了问题Pm｜chains｜Cmax的一个多项式时间的近似方案（PTAS）。