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

Scheduling Jobs with Chain Precedence Constraints on Identical Parallel Machines

作　　者：张传林 胡明才 

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

出　　处：《西安工业大学学报》2008年第6期598-600,共3页Journal of Xi’an Technological University

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

摘　　要：提出一种工件之间带有链优先约束的平行机排序问题,目标函数为极小化最大完工时间,优先约束为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.

关 键 词：排序 链优先约束 平行机 最长加工时间优先 多项式时间近似方案 

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