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

黨 蕊, 趙玉芳

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

?

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

黨 蕊, 趙玉芳

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

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

排序; 可用性限制; 惡化效應; 學習效應; 指派問題

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

近年來,同時具有惡化效應和學習效應的排序問題備受關注。本文將機器帶有可用性限制的模型與同時具有惡化和學習效應的模型相結合,研究了目標函數為總完工時間的單機和2臺平行機問題,并給出相應的動態規劃算法。

問題可描述如下:

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

1 單機問題

證明 應用成對交換方法證明。

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

動態規劃算法(DP1)

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

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

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

定理2 動態規劃算法(DP1)的計算復雜性為O(n2T1D),其中

證明 此動態規劃算法中共有4個變量。其中i的取值范圍為0到n;r的取值范圍為0到n;x的取值范圍為0到T1;y為排在T2后工件的總加工時間,當所有工件都排在T2后時,y取得最大值,即

所以該動態規劃算法的計算復雜性為O(n2T1D)。

當T1=0時,工件都排在T2后加工,根據定理1,有如下結論。

2 2臺平行機問題

證明 類似定理1的證明。

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

動態規劃算法(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)=+∞。

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

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

定理4 此動態規劃算法的計算復雜性為O(n3T1D1D2),其中

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

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

下面給出此問題的一個數值例子:

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

表1 當n1=3,n2=2時對應的目標函數系數

根據表1的計算結果可知,當n1=3時,機器不帶可用性限制的最優排序的總完工時間為33.83。當機器具有可用性限制的時間為3時,最優排序的總完工時間為

此時機器1上的排序為(J4,J5,J3);機器2上的排序為(J1,J2)。

3 結 語

本文將研究機器帶有可用性限制的模型與同時具有惡化和學習效應的模型相結合。具有更廣泛的實際意義,對于單機和2臺平行機問題給出了動態規劃算法并分析了算法的復雜性。但對于機器多次的可用性限制、工件的實際加工時間函數為其他形式和其他目標函數等問題還有待于進一步研究。

[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]王純,趙傳立.帶有學習效應和機器可用性限制的排序問題[J].系統工程與電子技術, 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]王吉波,王建軍,何平.具有共同松弛時間的惡化型工件排序問題研究[J].大連理工大學學報, 2012,52(3):932-936.

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

[15]郭玲,趙傳立.在退化維修下帶有工期指派和加工時間可控的單機排序問題[J].沈陽師范大學學報:自然科學版, 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。

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

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

1673-5862(2015)01-0028-05

O223

A

10.3969/ j.issn.1673-5862.2015.01.007