一台机器在加工时间相同准备时间可控时的L_(max)问题

一组n个工件需在一台机器上加工,工件j所需的加工时间、应交工时间、准备时间分别为p_j、d_j、r(?)准备时间可压缩量为x_j,0≤x_j≤r(?)压缩权因子为w_j,由最大延误(?)和压缩费用∑w_jx_j可构成文中(P_1)～(P_3)三个排序问题,在d_j≡0的条件下,引文的作者证明了(P_1)、（P_2）为强NP-C的。本文在d_j任意,p_j≡w_j≡l的条件下,对（P_1）～（P_3）给出了一个伪多项式时间算法。