摘要
一组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）给出了一个伪多项式时间算法。
A group of n jobs are need to be processed on one machine, for the jth job, the processing time, due date and preparing time needed are Pj, dj and rj0 respectively, the preparing time can be reduced is xj, 0≤xj≤rj0, and the cost for the reduced preparing time is wjtj. By the maximum latemess and the total cost for the reduced preparing times, we construct three scheduling problems. (P1)- (P3) in this paper. Under the condition of dj≡0, Nowicki and Zdralka proved (P1) and (P2) were NP-hard. This paper gives a pseudopolynomial algorithm for (P1)- (P3) under the condition Pj≡wj≡1 and for any dj.
出处
《应用数学与计算数学学报》
1995年第1期61-70,共10页
Communication on Applied Mathematics and Computation
基金
国家自然科学基金资助项目
