带有退化工件和机器维修区间的单机排序问题

张敏娇，罗成新

（沈阳师范大学数学与系统科学学院，沈阳 110034）

带有退化工件和机器维修区间的单机排序问题

张敏娇，罗成新

（沈阳师范大学数学与系统科学学院，沈阳 110034）

考虑的是机器需要维护，且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝，如果工件被拒绝，那么需要支付拒绝惩罚；如果被加工，那么工件被排在机器上（机器需要在某一个固定的时间段内进行维修以提高其加工速度，且在这段时间内机器不能加工任何工件）进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形，利用划分程序的方法给出了一个全多项式近似方案，并得出该近似方案的时间复杂性，说明该问题是一般意义下NP-难的。

拒绝工件；退化；全多项式近似方案；维修区间；排序

在经典排序问题［1－2］中，工件的加工时间都是常值且机器连续加工，但在实际生产中，工件的加工时间可能会因等待时间过长而使工件退化，或是机器需要在一段时间内进行维修以提高他的工作效率。

对于带有拒绝工件和释放时间的单机排序问题已由文献［3-4］给出全多项式近似方案，并且有较好的时间复杂性。带有退化工件的排序问题由文献［5-6］利用文献［7］的方法在较好的时间复杂性下给出一全多项式近似方案，文献［5-15］对此排序问题也进行了相应的研究，并给出相应的算法。文献［2］对工件退化且工件允许拒绝的单机排序问题进行了研究，且给出相应的近似算法。

本文对工件退化和机器需要维修的单机排序问题进行研究，主要的思路来源于文献，目标是极小化被加工工件的总完工时间与被拒绝工件的总惩罚之和，对于该排序问题本文利用划分程序的方法构造出一个全多项式近似方案。

1 问题描述

相互独立的工件集J＝｛J1，J2，…，J n｝，机器在0时刻开始连续加工，且机器在每一时刻至多加工一个工件。每个工件J j要么在机器上被加工，加工时间为p j＝a j＋b jt（其中b j为工件J j的退化率，t为工件J j的开始加工时间）；要么被拒绝，需要支付拒绝惩罚w j。记U和¯U为被加工工件集和被拒绝工件集且机器在某一时间区间［T1，T2］内不可用（其中不可用是指机器在这段时间内需要进行维修处理不能对任何一个工件进行加工）。

2 全多项式近似方案

一个算法A称为（1＋ε）-因子近似算法，如果极小化问题的一实例在算法A下得到的目标值不超过该问题的最优目标值的（1＋ε）倍且运算时间是关于输入规模的多项式。一族近似算法称为全多项式近似方案（FPTAS），如果对于任意的ε＞0，算法Aε是一（1＋ε）-因子近似算法且运算时间是关于输入规模及的多项式。不失一般性，令0＜ε≤1。对∀0＜ε≤1，假设a j，b j，w j都是非负整数。首先给出一个引理。

其中，S1表示排在T1之前加工的工件集，中已排工件在T1之前被加工的工件中最大完工时间，S2表示排在T2之后的加工工件集，中已排工件在T2之后被加工的工件的最大完工时间，而中被拒绝工件的总惩罚。

1）将A中向量x进行标号

2）将向量x（1），x（2），…，x（i1）按顺序逐个递增放入集合中，直到找出i1使得，如果这样的i1不存在，那么令且划分停止。

3 结 论

［1］KOVAl LYOV M Y，KUBIAK W.A fully polynomial approximation scheme for the weighted earliness-tardiness problem［J］.Oper Res，1999，47（5）：757-761.

［2］LI Shisheng，YUAN Jinjiang.Parallel-machine scheduling with deteriorating jobs and rejection［J］.Theor Comput Sci，2010，11（40／42）：3642-3650.

［3］AFRATA F，BAMPIS E，CHEKURI C，et al.Approximation schemes for minimizing average weighted completion time with release dates［J］.Found Com Sci，1999，40：32-44.

［4］ZHANG Liqi，LU Linfa，YUAN Jinjiang.Single machine scheduling with release dates and rejection［J］.Eur J Oper Res，2009，198：975-978.

［5］KANG Liying，NG C T.A note on fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs［J］.Int J Prod Econ，2007，109（1／2）：180-184.

［6］JI Min，CHENG T C E.Parallel-machine scheduling with simple linear deterioration to minimize total completion time［J］.Eur J Oper Res，2008，188（2）：342-347.

［7］KOVAl LYOV M Y，KUBIAK W.A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs［J］.J Heur，1998，32：87-297.

［8］BROWNE S，YECHINALI U.Scheduling deteriorating jobs on a single processor［J］.Oper Res，1990，38（3）：495-498.

［9］KANG Liying，NG C T.A note on a fully polynomial-time approximation scheme for parallel scheduling with deteriorating jobs［J］.Int J Prod Econ，2007，109：180-184.

［10］KUO W H，YANG D L.Parallel-machine scheduling with time dependent processing times［J］.Theor Comput Sci，2008，393：204-210.

［11］HSIEH Y C，BRICKER A L.Scheduling linearly deteriorating on multiple machines［J］.Com Ind Eng，1997，32：727-734.

［12］GRAHAM R L，LAWLER E L，LESTRA J K，et al.Optimization and approximation in sequencing and scheduling：a survey［J］.Annals Disc Math，1979，5（1）：287-326.

［13］WEGLARZ J.Multiprocessor scheduling with memory allocation a deterministic approach［J］.Tran Com，1980，29（8）：703-709.

［14］WANG Jibo，Ng C T，CHENG T C E.Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint［J］.Com Opera Res，2008，35（8）：2684-2693.

［15］WANG Jibo，Ng C T，CHENG TCE，et al.Minimizing total completion time in a two-machine flow shop with deteriorating jobs［J］.Appl Math Comput，2006，180（1）：1.

Single-machine scheduling problem with deteriorating jobs and fixed machine non-availability interval

ZHANG Minjiao，LUO Chengxin

（School of Mathematics and System Science，Shenyang Normal University，Shenyang 110034，China）

In this paper we consider the scheduling problem of schedulingndeteriorating jobs on a single machine.Each jobs processing time is a linear non-decreasing function of its start time and jobs can be rejected.A job is either rejected，in which case a rejection penalty has to be paid，or accepted and processed on a single machine（requires a fixed time interval during which the machine is turned off and production is stopped）.The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs.We give a fully polynomial time approximation scheme（FPTAS）for the case with a single machine and the time complexity，thus indicating that the problem is NP－hard in the ordinary sense only.

rejection job；deteriorating；fully polynomial time approximation scheme；non－availability interval；scheduling

O223

A

10.3969／j.issn.1673-5862.2013.03.008

1673-5862（2013）03-0348-05

2012-06-20。

国家自然科学基金资助项目（61070242）。

张敏娇（1986-），女，黑龙江双鸭山人，沈阳师范大学硕士研究生；罗成新（1958-），男，辽宁新宾人，沈阳师范大学教授，博士，硕士研究生导师。