極小化加權(quán)總完工時間的可拒絕單機(jī)排序問題

閆力君, 趙玉芳

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

?

極小化加權(quán)總完工時間的可拒絕單機(jī)排序問題

閆力君, 趙玉芳

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

在經(jīng)典的排序問題中,工件的加工時間是固定不變的。然而,在實際生產(chǎn)中,工件的實際加工時間會發(fā)生變化。同時,機(jī)器通常需要進(jìn)行保養(yǎng),或發(fā)生故障時進(jìn)行維修等原因,導(dǎo)致機(jī)器在某一時間段內(nèi)無法工作,即機(jī)器的不可用區(qū)間。研究帶有到達(dá)時間、退化效應(yīng)和拒絕工件,及機(jī)器帶有不可用區(qū)間的單機(jī)排序問題。在這一模型中,工件的開始加工時間越晚,其實際加工時間越大,實際加工時間是與其開始加工時間有關(guān)的函數(shù)。該問題中工件允許被拒絕。如果工件被拒絕,那么需要支付拒絕懲罰。討論的目標(biāo)函數(shù)是接受工件的加權(quán)總完工時間與所有拒絕工件的拒絕懲罰之和。首先說明該問題是一般意義NP-難的,進(jìn)而利用劃分程序的方法給出了一個全多項式近似方案,最后分析了該近似方案的時間復(fù)雜性。

拒絕懲罰; 退化效應(yīng); 全多項式近似方案; 不可用區(qū)間

在經(jīng)典的排序問題中,工件的實際加工時間是一個固定參數(shù)。但是,在實際生產(chǎn)中,工件的實際加工時間不一定是固定的。文獻(xiàn)[1-4]研究了帶有退化效應(yīng)模型的單機(jī)排序問題,其中工件的實際加工時間與其開始加工時間有關(guān)。分別研究了最大完工時間、總完工時間、加權(quán)總完工時間等問題。文獻(xiàn)[5-6]研究了工件允許被拒絕的排序問題,分別研究了最大完工時間、加權(quán)總完工時間問題。文獻(xiàn)[7]研究了工件的實際加工時間與其開始加工時間有關(guān)的平行機(jī)排序問題,目標(biāo)函數(shù)是總完工時間,利用劃分程序的方法給出該問題的全多項式近似方案。文獻(xiàn)[8-9]研究了工件加工時間帶有退化效應(yīng)的單機(jī)排序問題,證明了問題在多項式時間內(nèi)可解。文獻(xiàn)[10-11]研究了帶有不可用區(qū)間的最大完工時間問題。文獻(xiàn)[12]研究了目標(biāo)函數(shù)為加權(quán)總完工時間的單機(jī)和平行機(jī)排序問題,并且機(jī)器帶有不可用區(qū)間,說明了單機(jī)和平行機(jī)問題都是NP-難的,并且給出了啟發(fā)式算法。文獻(xiàn)[13]研究了2臺機(jī)器的流水作業(yè)排序問題,證明了最大完工時間問題是NP-難的,并且給出了擬多項式時間的動態(tài)規(guī)劃算法。文獻(xiàn)[14-15] 研究了帶有不可用區(qū)間的排序問題,分別對中斷繼續(xù)及中斷重復(fù)的情形進(jìn)行了研究。

同時帶有拒絕懲罰及不可用區(qū)間的現(xiàn)象非常普遍,本文將上述問題結(jié)合起來,討論了帶有到達(dá)時間、退化效應(yīng)、拒絕工件及機(jī)器帶有不可用區(qū)間的單機(jī)排序問題,目標(biāo)函數(shù)是接受工件的加權(quán)總完工時間與所有拒絕工件的拒絕懲罰之和。利用劃分程序的方法給出了一個全多項式近似方案,并分析該近似方案的時間復(fù)雜性。

1 問題描述

具體問題描述如下:n個互不相關(guān)的工件J1,J2,…,Jn在一臺機(jī)器上加工,所有工件具有相同的到達(dá)時間t0,且t0>0;工件Jj的實際加工時間為pj=bjt,其中bj>0為工件Jj的退化因子;t為其開始加工時間,顯然t≥t0>0;ej>0是工件Jj被拒絕時的懲罰。記被加工的工件的集合為S,所有被拒絕的工件的集合為R。[T1,T2)為機(jī)器的不可用區(qū)間,在此區(qū)間內(nèi)機(jī)器不能加工任何工件。nr-a表示機(jī)器為不可恢復(fù)的,即某個工件在不可用區(qū)間之前沒加工完,則在不可用區(qū)間之后需要重新加工這個工件。目標(biāo)函數(shù)是接受工件的加權(quán)總完工時間與所有拒絕工件的懲罰之和。同時具有到達(dá)時間、退化效應(yīng)、拒絕工件及機(jī)器帶有不可用區(qū)間的單機(jī)排序問題,利用三參數(shù)表示法α|β|γ可記為

2 全多項式近似方案

一個算法A稱為(1+ε)因子近似算法,如果極小化問題的一實例在算法A下得到的目標(biāo)值不超過該問題的最優(yōu)目標(biāo)值的(1+ε)倍且運算時間是關(guān)于輸入規(guī)模的多項式。一族近似算法稱為全多項式近似方案(FPTAS) ,如果對于任意的ε>0,算法Aε是一(1+ε)因子近似算法且運算時間是關(guān)于輸入規(guī)模及1/ε的多項式。不失一般性,令0<ε≤1。對0<ε≤1,假設(shè)bj,ej,r0,wj都是非負(fù)整數(shù)。

1) 將A中向量x進(jìn)行標(biāo)號x(1),x(2),…,x(|A|),使得0≤f(x(1))≤f(x(2))≤…≤f(x(|A|))。

假設(shè)xj=1,令δ1=δ。

同理,當(dāng)xj=0,xj=2時,有

這樣導(dǎo)出

從式(1)和式(7)得

類似地,有

令δk=δ+δk(1+δ),k=2,3,…,n-j+1,于是有

又通過引理4有

算法的時間復(fù)雜性:

3 結(jié) 論

本文研究的是帶有釋放時間、退化工件和拒絕工件,且機(jī)器帶有不可用區(qū)間的單機(jī)排序問題,目標(biāo)函數(shù)為最小化所有接受工件的加權(quán)總完工時間與所有拒絕工件的拒絕懲罰之和。首先說明該問題是一般意義下NP-難的,進(jìn)而利用劃分程序的方法給出了一個全多項式近似方案,最后確定了其時間復(fù)雜性為O(n7L5/ε4)。由于機(jī)器帶有不可用區(qū)間以及拒絕懲罰同時存在的現(xiàn)象很普遍,因此,進(jìn)一步研究機(jī)器帶有不可用區(qū)間以及拒絕懲罰的排序問題具有廣泛的應(yīng)用價值和實際意義。對于具有其他退化效應(yīng)的函數(shù)問題以及機(jī)器具有不可用區(qū)間的排序問題,還有待進(jìn)一步研究。

[1]MOSHEIOV G.Scheduling jobs under simple linear deterioration[J].Comput Ope Res, 1994,21(6):653-659.

[2]WU C C, HSU P H, CHEN J C, et al.Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times[J].Comput Ope Res, 2011,38(7):1025-1034.

[3]崔苗苗,趙玉芳,王松麗.機(jī)器具有可用性限制的加權(quán)總完工時間問題[J].沈陽師范大學(xué)學(xué)報:自然科學(xué)版, 2012,30(2):157-163.

[4]CHENG Yushao, SUN Shijie.Scheduling linear deteriorating jobs with rejection on a single machine[J].Eur J Oper Res, 2009,194(1):18-27.

[5]ZHANG Liqi, LU Lingfa, YUAN Jinjiang.Single machine scheduling with release dates and rejection[J].Eur J Oper Res, 2009,198(3):975-978.

[6]LI Shisheng, YUAN Jinjiang.Parallel-machine scheduling with deteriorating jobs and rejection[J].Theor Comp Sci, 2010,411(40):3642-3650.

[7]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.

[8]王吉波,王建軍,何平.具有共同松弛時間的惡化型工件排序問題研究[J].大連理工大學(xué)學(xué)報, 2012,52(3): 932-936.

[9]王吉波,劉璐,許揚韜,等.具有惡化工件的不同工期指派問題研究[J].沈陽航空航天大學(xué)學(xué)報, 2013,30 (5):83-87.

[10]KACEM I, HAOUARI M.Approximation algorithms for single machine scheduling with one unavailability period[J].Oper Res, 2009,7(1):79-92.

[11]WU C C, LEE W C.Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine[J].Infor Proc Let, 2003,87(2):89-93.

[12]LEE C Y.Machine scheduling with an availability constraint[J].J Glo Opt, 1996,9(3/4):395-416.

[13]LEE C Y.Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[J].Oper Res Let, 1997,20(3):129-139.

[14]CHEN W J.Minimizing total flow time in the single-machine scheduling problem with periodic maintenance[J].J Oper Res Soc, 2006,57(4):410-415.

[15]JI Min, HE Yong, CHENG T C E.Scheduling linear deteriorating jobs with an availability constraint on a single machine[J].Theor Comp Sci, 2006,362(1):115-126.

[16]KOVALYOV M Y, KUBIAK W.A fully polynomial approximation scheme for the weighted earliness-tardiness problem[J].Oper Res, 1999,47(5):757-761.

Single machine scheduling with rejection for minimizing total weighted completion time

YANLijun,ZHAOYufang

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

Traditional scheduling problems assume that the processing time of a given job is fixed.However, the processing time may change in the real world.At the same time, the machine may ba unavailable because of preventive maintenances and periodical repairs, namely, non-availability interval.This paper studied the scheduling problems with release dates, deteriorating effect, rejection and an availability constraint.In this model, job processing times are not fixed because jobs may deteriorate while wating to be precessed.We consider the processing time of a job is related with its starting time and jobs can be rejected.A job is either rejected, in which case a rejection penalty has to be paid.The objective is to minimize the total weighted completion time of the accepted jobs plus the total penalty of the rejected jobs.First, we indicate the problem is NP-hard in the ordinary sense.And then, a fully polynomial-time approximation scheme is given for the problem, and analyse the time complexity of the fully polynomial-time approximation scheme.

rejection penalty; deteriorating; fully polynomial time approximation scheme; non-availability interval

2014-05-23。

遼寧省教育廳科學(xué)技術(shù)研究項目(L2014433)。

閆力君(1990-),女,遼寧鐵嶺人,沈陽師范大學(xué)碩士研究生; 通信作者: 趙玉芳(1966-),女,遼寧遼陽人,沈陽師范大學(xué)副教授,博士,碩士研究生導(dǎo)師。

1673-5862(2015)01-0033-05

O223

A

10.3969/ j.issn.1673-5862.2015.01.008