富晓双，赵玉芳，田 野

(1.沈阳师范大学 数学与系统科学学院，辽宁 沈阳 110034；2.北京市第五中学通州校区，北京 101100)

0 引言

在大多数经典的排序问题中，假设工件的加工时间是常数.然而，在实际的生产过程中，当机器连续加工工件时，可能会出现退化现象，即工件在排序中的开始加工时间越晚，它的实际加工时间越长，例如钢铁生产、消防、资源分配等.Jatinder N.D.Gupta和Sushil K.Gupta[1],Browne和Yechiali[2]分别提出了退化工件的概念，工件j的实际加工时间为aj+bjt,bj>0,aj是工件j的基本加工时间，bj是退化率，t是工件j的开始加工时间，对于最大完工时间的问题，他们证明了工件按aj/bj不减顺序排序可以得到最优解.Mosheiov[3]研究了带有简单线性退化的单机排序问题，工件j的实际加工时间为pj=αjt,αj是退化率，t>0是工件j的开始加工时间，目标函数分别为最大完工时间、流程时间、总延误、延误工件数等，证明了这些问题都是多项式时间可解的.Bachman等[4]研究了带有退化工件的单机排序问题，目标为极小化总加权完工时间，证明了这个问题是NP-难的.王吉波等[5]研究了具有恶化效应和可控加工时间的单机排序问题，目标是确定工件的最优排序、最优资源分配和共同工期(松弛工期)，使所有工件的排序费用(包括提前时间、延误时间、共同工期(松弛工期))和资源的消耗费用的线性加权和最小,证明了此问题可以在多项式时间内求解.Ji和Cheng[6]研究了带有退化工件的平行机排序问题，目标为极小化总完工时间，对于这个NP-难问题，提出了一个FPTAS.此后，带有退化……