关于问题P_m|chains|C_(max)的PTAS算法  

PTAS for Problem of P_m|chains|C_(max)

作　　者：张传林 曹丽霞 郑培华 

机构地区：[1]日照广播电视大学教学科研处,山东日照276826 [2]日照广播电视大学数学系,山东日照276826

出　　处：《北方工业大学学报》2008年第3期49-51,共3页Journal of North China University of Technology

基　　金：国家自然科学基金资助项目(10671108);山东省自然科学基金资助项目(Y2005A04)

摘　　要：对工件之间带有链优先约束的平行机排序问题进行了研究.优先约束是n条链Ti,1≤i≤n,n为任意实数,目标函数为极小化最大完工时间.问题Pm|chains|Cmax是强NP完备的,对于强NP完备问题不可能有全多项式时间的近似方案(FPTAS)(除非P=NP),找到一个多项式时间的近似方案(PTAS,Polyomial Time Approximation Scheme)是最好的结果.本文利用LPT算法,给出了问题Pm|chains|Cmax的一个多项式时间的近似方案(PTAS).The problem of scheduling jobs with chain precedence constraints on identical paral- lel machines is discussed in this article. The precedence constraints are characterized by n chains Ti, and 1≤i≤n, in which n is any real number and the objective function is to minimize the make span. The problem of Pm｜chains｜Cmax is NP-complete in the strong sense, which cannot have a FPTAS （unless P= NP）, so the best result is to find a PTAS（Polyomial Time Approximation Scheme）. By using LPT, PTAS to the problem of Pm｜chains｜Cmax is obtained.

关 键 词：排序 平行机 链优先约束 PTAS 

分 类 号：O223[理学—运筹学与控制论]