摘要
考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.
A problem of scheduling n tasks with four chain-precedence constraints on three parallel machines is considered.The objective is minimize the makespan.This paper explain the NP-hardness of this problem,which computational complexity is characterized by giving a pseudo-polynomial time algorithm and a FPTAS.
出处
《聊城大学学报（自然科学版）》
2011年第4期37-40,51,共5页
Journal of Liaocheng University:Natural Science Edition
基金
国家自然科学基金(11071142)
山东省自然科学基金(ZR2010AM034)
关键词
排序
约束链
动态规划
计算复杂性
FPTAS
scheduling
chain-precedence constraints
dynamic program
computational complexity
FPTAS
