黨 蕊, 趙玉芳

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

?

帶有可變加工時(shí)間和可用性限制的排序問題

黨 蕊, 趙玉芳

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

研究帶有惡化效應(yīng)、學(xué)習(xí)效應(yīng)和可用性限制的單機(jī)和2臺平行機(jī)的排序問題。在這個(gè)模型中,工件的實(shí)際加工時(shí)間與其基本加工時(shí)間、加工過程中所排位置及開始加工時(shí)間有關(guān);同時(shí)由于維修、保養(yǎng)等原因,使得機(jī)器在某段時(shí)間不能加工工件,即機(jī)器具有可用性限制,且維修之后機(jī)器性能完全恢復(fù),討論的目標(biāo)函數(shù)為總完工時(shí)間。對于可以在任意時(shí)間只維修一次的單機(jī)問題,以及只有一臺機(jī)器具有可用性限制的2臺平行機(jī)問題,分別給出了擬多項(xiàng)式時(shí)間的動態(tài)規(guī)劃算法。特別對于一臺機(jī)器只在零時(shí)刻開始維修另一臺機(jī)器無可用性限制的特殊情況,通過將其轉(zhuǎn)化為指派問題,給出了復(fù)雜性為O(n4)的多項(xiàng)式時(shí)間最優(yōu)算法,并通過一個(gè)數(shù)值例子說明了其計(jì)算過程。

排序; 可用性限制; 惡化效應(yīng); 學(xué)習(xí)效應(yīng); 指派問題

在經(jīng)典排序模型中,工件的加工時(shí)間是一個(gè)常數(shù)。但在實(shí)際生產(chǎn)中,由于長時(shí)間的工作,機(jī)器受到一定的影響,使得工件的開始加工時(shí)間越晚,其所需的實(shí)際加工時(shí)間越長,此現(xiàn)象稱為惡化效應(yīng)。同時(shí),由于工人長期加工相同的工件獲得了經(jīng)驗(yàn),使得工件所排位置越往后其所需要的實(shí)際加工時(shí)間越短,此現(xiàn)象稱為學(xué)習(xí)效應(yīng)。文獻(xiàn)[1-2]研究帶有惡化效應(yīng)的單機(jī)排序模型,分別證明了最大完工時(shí)間問題和總完工時(shí)間問題是多項(xiàng)式時(shí)間可解的。文獻(xiàn)[3-4]研究帶有學(xué)習(xí)效應(yīng)的單機(jī)排序模型,證明了總完工時(shí)間問題是多項(xiàng)式時(shí)間可解的。文獻(xiàn)[5-8]研究了帶有學(xué)習(xí)效應(yīng)和惡化效應(yīng)的單機(jī)排序問題,證明了總完工時(shí)間問題是多項(xiàng)式時(shí)間可解的。

近年來,同時(shí)具有惡化效應(yīng)和學(xué)習(xí)效應(yīng)的排序問題備受關(guān)注。本文將機(jī)器帶有可用性限制的模型與同時(shí)具有惡化和學(xué)習(xí)效應(yīng)的模型相結(jié)合,研究了目標(biāo)函數(shù)為總完工時(shí)間的單機(jī)和2臺平行機(jī)問題,并給出相應(yīng)的動態(tài)規(guī)劃算法。

問題可描述如下:

設(shè)工件集J={J1,J2,…,Jn}由n個(gè)不相關(guān)的工件組成。機(jī)器在零時(shí)刻開始加工工件,且在每一時(shí)刻至多加工一個(gè)工件。若工件Ji在t時(shí)刻排在第r個(gè)位置加工,其實(shí)際加工時(shí)間為pira+bt(其中pi為工件Ji的基本加工時(shí)間,a≤0是學(xué)習(xí)因子,b>0是惡化因子)。記Ci為工件Ji的完工時(shí)間。nr-a表示如果一個(gè)工件在不可用區(qū)間之前沒有加工完,那么在不可用區(qū)間之后不能繼續(xù)加工,只能重新開始加工。對于單臺機(jī)器問題,假設(shè)機(jī)器在[T1,T2](0≤T1

1 單機(jī)問題

證明 應(yīng)用成對交換方法證明。

令狀態(tài)(i,x,y,r)表示工件J1,J2,…,Ji已排完;排在T1前工件的個(gè)數(shù)是r,總加工時(shí)間為x;排在T2后工件的個(gè)數(shù)是i-r,總加工時(shí)間為y。f(i,x,y,r)表示工件J1,J2,…,Ji的最小總完工時(shí)間。

動態(tài)規(guī)劃算法(DP1)

1) 置f(1,p1,0,1)=p1,f(1,0,p1+bT2,0)=p1+(1+b)T2,當(dāng)x?{0,p1}時(shí),f(1,x,y,r)=+∞。

當(dāng)x<0,或y<0,或r<0時(shí),有f(i,x,y,r)=+∞,i=1,2,…,n。

則f(n,x,y,r)為最優(yōu)值。

定理2 動態(tài)規(guī)劃算法(DP1)的計(jì)算復(fù)雜性為O(n2T1D),其中

證明 此動態(tài)規(guī)劃算法中共有4個(gè)變量。其中i的取值范圍為0到n;r的取值范圍為0到n;x的取值范圍為0到T1;y為排在T2后工件的總加工時(shí)間,當(dāng)所有工件都排在T2后時(shí),y取得最大值,即

所以該動態(tài)規(guī)劃算法的計(jì)算復(fù)雜性為O(n2T1D)。

當(dāng)T1=0時(shí),工件都排在T2后加工,根據(jù)定理1,有如下結(jié)論。

2 2臺平行機(jī)問題

證明 類似定理1的證明。

令狀態(tài)(i,x,y,z,r1,r2)表示工件J1,J2,…,Ji已排完;排在機(jī)器M1上T1前工件的個(gè)數(shù)是r1,總加工時(shí)間為x;排在機(jī)器M1上T2后工件的個(gè)數(shù)是r2,總加工時(shí)間為y;排在機(jī)器M2上工件的個(gè)數(shù)是i-r1-r2,總加工時(shí)間為z。f(i,x,y,z,r1,r2)表示工件J1,J2,…,Ji的最小總完工時(shí)間。

動態(tài)規(guī)劃算法(DP2)

1) 置f(1,p1,0,0,1,0)=p1,f(1,0,p1+bT2,0,0,1)=p1+(1+b)T2,f(1,0,0,p1,0,0)=p1;否則f(1,x,y,z,r1,r2)=+∞。

當(dāng)x<0,或y<0,或r1,r2<0時(shí),有f(i,x,y,z,r1,r2)=+∞,i=1,2,…,n。

f(n,x,y,z,r1,r2)為最優(yōu)值。

定理4 此動態(tài)規(guī)劃算法的計(jì)算復(fù)雜性為O(n3T1D1D2),其中

式(1)表示每臺機(jī)器的每個(gè)位置只能加工一個(gè)工件,式(2)表示每個(gè)工件只能被加工一次,xijr為0/1變量,如果工件Ji排在機(jī)器Mj上第r個(gè)位置時(shí),xijr=1;否則xijr=0。

證明 (n1,n2)表示機(jī)器M1上排有n1個(gè)工件,機(jī)器M2上排有n2個(gè)工件。對于每一對取值都有一個(gè)對應(yīng)的指派問題。由于指派問題的計(jì)算復(fù)雜性為O(n3),因此定理成立。

下面給出此問題的一個(gè)數(shù)值例子:

例 設(shè)m=2,n=5,p1=3,p2=5,p3=7,p4=2,p5=4,T1=0,T2=3,a=-1,b=1。此數(shù)值例子的(n1,n2)有6種情況,分別為(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)。對于(3,2)這種情況,表1給出了第i個(gè)工件排在第j臺機(jī)器上的第r個(gè)位置時(shí)目標(biāo)函數(shù)系數(shù),其中[j,r]表示工件排在第j臺機(jī)器上的第r個(gè)位置。

表1 當(dāng)n1=3,n2=2時(shí)對應(yīng)的目標(biāo)函數(shù)系數(shù)

根據(jù)表1的計(jì)算結(jié)果可知,當(dāng)n1=3時(shí),機(jī)器不帶可用性限制的最優(yōu)排序的總完工時(shí)間為33.83。當(dāng)機(jī)器具有可用性限制的時(shí)間為3時(shí),最優(yōu)排序的總完工時(shí)間為

此時(shí)機(jī)器1上的排序?yàn)?J4,J5,J3);機(jī)器2上的排序?yàn)?J1,J2)。

3 結(jié) 語

本文將研究機(jī)器帶有可用性限制的模型與同時(shí)具有惡化和學(xué)習(xí)效應(yīng)的模型相結(jié)合。具有更廣泛的實(shí)際意義,對于單機(jī)和2臺平行機(jī)問題給出了動態(tài)規(guī)劃算法并分析了算法的復(fù)雜性。但對于機(jī)器多次的可用性限制、工件的實(shí)際加工時(shí)間函數(shù)為其他形式和其他目標(biāo)函數(shù)等問題還有待于進(jìn)一步研究。

[1]BROWNE S, YECHIALI U.Scheduling deteriorating jobs on a single processor[J].Oper Res, 1990,38(3):495-498.

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

[3]BISKUP D.Single-machine scheduling with learning considerations[J].Eur J Oper Res, 1999,115(1):173-178.

[4]MOSHEIOV G, SIDNEY J B.Scheduling with general job-dependent learning curves[J].Eur J Oper Res, 2003,147(3):665-670.

[5]LEE W C.A note on deteriorating jobs and learning in single-machine scheduling problems[J].Int J Business and Economics, 2004,3(1):83-89.

[6]CHENG Mingbao, SUN Shijie.The single-machine scheduling problems with deteriorating jobs and learning effect[J].J Zhejiang University Sci A, 2006,7(4):597-601.

[7]YANG D L, KUO W H.Single-machine scheduling with both deterioration and learning effects[J].Ann Oper Res, 2009,172(1):315-327.

[8]YANG D L, KUO W H.Some scheduling problems with deteriorating jobs and learning effects[J].Comput Ind Eng, 2010,58(1):25-28.

[9]ADIRI I, BRUNO J, FROSTIG E, et al.Single machine flow-time scheduling with a single breakdown[J].Acta Inf, 1989,26(7):679-696.

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

[11]王純,趙傳立.帶有學(xué)習(xí)效應(yīng)和機(jī)器可用性限制的排序問題[J].系統(tǒng)工程與電子技術(shù), 2009,31(6):1372-1375.

[12]ZHAO Chuanli, JI Min, TANG Hengyong.Parallel-machine scheduling with an availability constraint[J].Comput Ind Eng, 2011,61(3):778-781.

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

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

[15]郭玲,趙傳立.在退化維修下帶有工期指派和加工時(shí)間可控的單機(jī)排序問題[J].沈陽師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2013,31(3):341-347.

Scheduling problem with variable processing times and machine availability constraints

DANGRui,ZHAOYufang

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

This paper considers some scheduling problems of single machine and two parallel machines with deteriorating effect, learning effect and an availability constraint.In such problems, the actual processing time of a job depends not only on its basic processing time but also on its scheduled position and starting time.Moreover machines may be unavailable because of preventive maintenances and periodical repairs, namely, the machine availability constraint.Machine conditions are perfectly restored to its initial state after the maintenance activity.The objective is to minimize the total completion time.We study the case that the machine is unavailable at any time.We consider a single machine scheduling problem with only once maintenance.We also consider a two parallel machines scheduling problem in that one machine is unavailable.Two pseudo-polynomial dynamic programming algorithms are proposed to solve the above problems respectively.Specifically, we give a polynomial time optimal algorithm withO(n4) for the two parallel machines scheduling problem, in which one machine is unavailable at time zero and anther is always available.Finally, we give a numerical example to illustrate its calculation process.

scheduling; availability constraints; deteriorating effect; learning effect; assignment problem

2014-05-23。

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

黨 蕊(1988-),女,遼寧葫蘆島人,沈陽師范大學(xué)碩士研究生; 通信作者: 趙玉芳(1966-),女,遼寧遼陽人,沈陽師范大學(xué)副教授,博士,碩士研究生導(dǎo)師。

1673-5862(2015)01-0028-05

O223

A

10.3969/ j.issn.1673-5862.2015.01.007