带有链优先约束工件的平行机排序问题

Scheduling Jobs with Chain Precedence Constraints on Identical Parallel Machines

提出一种工件之间带有链优先约束的平行机排序问题,目标函数为极小化最大完工时间,优先约束为n条链Ti(1≤i≤n,n为任意实数),处理机为m台同速机,用三参数法表示为Pm|chains|Cmax.问题Pm|chains|Cmax是强NP完备的,利用启发式算法的最长加工时间优先规则,给出了一个多项式时间的近似方案.

The problem of scheduling jobs with chain precedence constraints on identical parallel machines is put forward, where the objective funelion is the makespan. The precedence constraints is n chains Ti （1≤i≤n. n-arbitrary real number） ,and processors are m identical processors. This problem is denoted by Pm｜chains｜Cmax. It is the strong problem NP-complete. Using longest processing time first （LPT） rule of heuristic algorithm,a polynomial time approximation scheme （PTAS） is obtained.