论文部分内容阅读
研究关于有固定工件序约束的单机最小化最大流程排序问题模型．在该模型中，有些固定工件已事先安排好，其余的自由工件之间的加工顺序满足给定的序约束．工件之间不允许抢先中断，在同一时间，机器最多只能加工一个工件．其目标是使得最大流程达到最小．该问题即使是对没有序约束的特殊情形也已被证明是NP-困难的．给出了该问题的一个线性时间的2-近似算法，并且证明了除非P=NP，对任意的δ〉0，该问题甚至没有拟多项式时间的（2-δ）近似算法．