关于有固定工件和序约束的单机最小化最大流程排序问题的注记(英文)

A short note on the approximability of the single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints

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

The single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints is considered. There are some fixed jobs which are already fixed in the schedule. The remaining free jobs are to be assigned to the machines in such a way that they do not overlap with the fixed jobs. The order of job processing between the free jobs is restricted by given precedence constraints ≤, and the jobs are processed without preemption. The objective is to minimize the makespan. In the literature this problem has been proved to be strongly NP-hard even without precedence constraints. It is shown that this problem has a linear-time 2-approximation algorithm, but has no pseudopolynomial time （2-δ） approximation algorithm, for every δ〉0, if P≠NP.