張敏嬌，羅成新

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

帶有退化工件和機器維修區(qū)間的單機排序問題

張敏嬌，羅成新

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

考慮的是機器需要維護，且需要對若干個退化工件進行加工的單機排序問題。所謂退化情況是指每個工件的加工時間是關(guān)于它本身的開始時間的一個線性單增函數(shù)。該問題中工件允許被拒絕，如果工件被拒絕，那么需要支付拒絕懲罰；如果被加工，那么工件被排在機器上（機器需要在某一個固定的時間段內(nèi)進行維修以提高其加工速度，且在這段時間內(nèi)機器不能加工任何工件）進行加工。目標是尋找一個最優(yōu)排序使得被加工工件的總完工時間與被拒絕工件的總懲罰之和最小。對于單機情形，利用劃分程序的方法給出了一個全多項式近似方案，并得出該近似方案的時間復(fù)雜性，說明該問題是一般意義下NP-難的。

拒絕工件；退化；全多項式近似方案；維修區(qū)間；排序

在經(jīng)典排序問題［1－2］中，工件的加工時間都是常值且機器連續(xù)加工，但在實際生產(chǎn)中，工件的加工時間可能會因等待時間過長而使工件退化，或是機器需要在一段時間內(nèi)進行維修以提高他的工作效率。

對于帶有拒絕工件和釋放時間的單機排序問題已由文獻［3-4］給出全多項式近似方案，并且有較好的時間復(fù)雜性。帶有退化工件的排序問題由文獻［5-6］利用文獻［7］的方法在較好的時間復(fù)雜性下給出一全多項式近似方案，文獻［5-15］對此排序問題也進行了相應(yīng)的研究，并給出相應(yīng)的算法。文獻［2］對工件退化且工件允許拒絕的單機排序問題進行了研究，且給出相應(yīng)的近似算法。

本文對工件退化和機器需要維修的單機排序問題進行研究，主要的思路來源于文獻，目標是極小化被加工工件的總完工時間與被拒絕工件的總懲罰之和，對于該排序問題本文利用劃分程序的方法構(gòu)造出一個全多項式近似方案。

1 問題描述

相互獨立的工件集J＝｛J1，J2，…，J n｝，機器在0時刻開始連續(xù)加工，且機器在每一時刻至多加工一個工件。每個工件J j要么在機器上被加工，加工時間為p j＝a j＋b jt（其中b j為工件J j的退化率，t為工件J j的開始加工時間）；要么被拒絕，需要支付拒絕懲罰w j。記U和ˉU為被加工工件集和被拒絕工件集且機器在某一時間區(qū)間［T1，T2］內(nèi)不可用（其中不可用是指機器在這段時間內(nèi)需要進行維修處理不能對任何一個工件進行加工）。

2 全多項式近似方案

一個算法A稱為（1＋ε）-因子近似算法，如果極小化問題的一實例在算法A下得到的目標值不超過該問題的最優(yōu)目標值的（1＋ε）倍且運算時間是關(guān)于輸入規(guī)模的多項式。一族近似算法稱為全多項式近似方案（FPTAS），如果對于任意的ε＞0，算法Aε是一（1＋ε）-因子近似算法且運算時間是關(guān)于輸入規(guī)模及的多項式。不失一般性，令0＜ε≤1。對?0＜ε≤1，假設(shè)a j，b j，w j都是非負整數(shù)。首先給出一個引理。

其中，S1表示排在T1之前加工的工件集，中已排工件在T1之前被加工的工件中最大完工時間，S2表示排在T2之后的加工工件集，中已排工件在T2之后被加工的工件的最大完工時間，而中被拒絕工件的總懲罰。

1）將A中向量x進行標號

2）將向量x（1），x（2），…，x（i1）按順序逐個遞增放入集合中，直到找出i1使得，如果這樣的i1不存在，那么令且劃分停止。

3 結(jié) 論

［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－h(huán)ard 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。

國家自然科學(xué)基金資助項目（61070242）。

張敏嬌（1986-），女，黑龍江雙鴨山人，沈陽師范大學(xué)碩士研究生；羅成新（1958-），男，遼寧新賓人，沈陽師范大學(xué)教授，博士，碩士研究生導(dǎo)師。