趙玉芳, 葛秋利

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

0 引 言

近年來(lái),帶有維修活動(dòng)與退化效應(yīng)的問(wèn)題受到越來(lái)越多的關(guān)注。在加工過(guò)程中,機(jī)器產(chǎn)生損耗,會(huì)使工件加工時(shí)間增加。工件的加工時(shí)間與位置有關(guān),這種現(xiàn)象稱為退化效應(yīng)。Yang和Kuo[1]討論了帶有退化效應(yīng)與學(xué)習(xí)效應(yīng)的單機(jī)排序問(wèn)題,給出了不同問(wèn)題的多項(xiàng)式算法。Zhang等[2]討論了帶有退化效應(yīng)的單機(jī)排序問(wèn)題,分別給出了不同問(wèn)題的多項(xiàng)式算法。Zhao和Tang[3]討論了帶有安裝時(shí)間的單機(jī)排序問(wèn)題,分別給出了不同問(wèn)題的多項(xiàng)式算法。Rustogi和Strusevich[4]討論了帶有退化效應(yīng)與維修活動(dòng)的單機(jī)排序問(wèn)題,排序中的工件是成組加工的極小化最大完工時(shí)間,給出了復(fù)雜性為O(n4)的多項(xiàng)式算法。

在實(shí)際生活中,為了提高機(jī)器的加工效率,可以對(duì)機(jī)器進(jìn)行維修。Mor和Mosheiov[5]研究了帶有交貨期窗口和維修的單機(jī)排序問(wèn)題,根據(jù)維修的位置不同,考慮了維修活動(dòng)的3種情況,分別給出了多項(xiàng)式最優(yōu)算法。Cheng等[6]研究了帶有退化效應(yīng)和交貨期窗口與維修活動(dòng)的單機(jī)排序問(wèn)題,分析了維修活動(dòng)發(fā)生在交貨期窗口前、交貨期窗口內(nèi)和交貨期窗口后3種情況,分別給出了多項(xiàng)式算法。

另一方面,在某些情況下,工件在加工之前需要有安裝時(shí)間。Koulamas和Kyparisis[7]提出了線性和非線性的安裝時(shí)間模型,對(duì)于不同問(wèn)題,分別給出了計(jì)算復(fù)雜性都為O(nlogn)的多項(xiàng)式算法。Wang等[8]研究了帶有安裝時(shí)間和學(xué)習(xí)效應(yīng)與退化效應(yīng)的單機(jī)排序問(wèn)題,分別給出了加權(quán)總完工時(shí)間、總延誤、總誤工任務(wù)數(shù)的極小化問(wèn)題的多項(xiàng)式算法。Huang等[9]討論了帶有安裝時(shí)間、學(xué)習(xí)效應(yīng)和退化效應(yīng)的單機(jī)排序問(wèn)題,實(shí)際加工時(shí)間是位置和基本加工時(shí)間的不減函數(shù),證明了最大完工時(shí)間、總完工時(shí)間、總完工時(shí)間θ次冪的極小化問(wèn)題,可以通過(guò)SPT規(guī)則求解。Lee[10]討論了帶有安裝時(shí)間和退化效應(yīng)的單機(jī)排序問(wèn)題,給出了最大完工時(shí)間和總完工時(shí)間的多項(xiàng)式算法。王吉波等[11]討論了帶有學(xué)習(xí)與退化效應(yīng)的單機(jī)排序問(wèn)題,并給出了多項(xiàng)式算法。

Yang和Yang[12]討論了帶有退化效應(yīng)與維修活動(dòng)的單機(jī)排序問(wèn)題,分別給出了最大完工時(shí)間問(wèn)題的多項(xiàng)式算法。Li和Zhao[13]討論了帶有交貨期窗口、安裝時(shí)間的單機(jī)排序問(wèn)題,目標(biāo)函數(shù)是使得總提前、延誤與交貨期窗口的費(fèi)用之和最小,給出了計(jì)算復(fù)雜性為O(nlogn)的多項(xiàng)式算法。Rustogi和Strusevich[14]討論了帶有維修區(qū)間與退化效應(yīng)的單機(jī)排序問(wèn)題,根據(jù)工件的實(shí)際加工時(shí)間、工件無(wú)關(guān)或工件有關(guān)的具體情況分類討論,分別給出了多項(xiàng)式算法。本文在文獻(xiàn)[12]的基礎(chǔ)上,考慮帶有退化效應(yīng)、安裝時(shí)間與維修活動(dòng)的模型,在工件加工時(shí)間與組和位置有關(guān)、只與組有關(guān)2種情況下,分別給出了多項(xiàng)式算法。

1 問(wèn)題描述

本文考慮n個(gè)獨(dú)立的工件N={J1,…,Jn}在1臺(tái)機(jī)器上加工,所有工件在零時(shí)刻到達(dá)。工件在加工時(shí)被分成組,假設(shè)機(jī)器在零時(shí)刻處于最好的狀態(tài),隨著加工工件的增多,機(jī)器的加工能力退化,維修活動(dòng)可以使機(jī)器得到修復(fù)。在維修過(guò)程中不能加工其他工件,且維修活動(dòng)在組間發(fā)生,若工件分為k組,共進(jìn)行k-1次維修。維修使機(jī)器恢復(fù)到初始狀態(tài)。

假設(shè)維修區(qū)間D[i](τ)是位于第i組后的維修,其中維修長(zhǎng)度D[i](τ)是前1組工件的實(shí)際加工時(shí)間τ的線性函數(shù),若i=1,τ指第1組工件的加工時(shí)間;若i≠1,τ是指第i組工件的實(shí)際加工時(shí)間。有

D[i](τ)=aτ,1≤i≤n-1

其中a>0為常量。每組加工之前需要有安裝時(shí)間,第i組工件安裝時(shí)間為s[i],其中

令F[i]表示第i組的完工時(shí)間,P[i]表示第i組工件的加工時(shí)間(1≤i≤k≤n)。

對(duì)于一個(gè)特定的排序,k-1次維修時(shí),1≤k≤n,工件j的實(shí)際加工時(shí)間取決于工件所在的組及工件在組內(nèi)的位置。用MP表示維修活動(dòng),下面用三參數(shù)表示法將帶有退化效應(yīng)、維修活動(dòng)與安裝時(shí)間的問(wèn)題表示為

1pjg[i](r),MP[k-1],SpsdCmax

2 極小化最大完工時(shí)間問(wèn)題

性質(zhì)1 對(duì)于1pjg[i](r),MP[k-1],SpsdCmax問(wèn)題,在第x組內(nèi)工件的加工時(shí)間非增排序得到的結(jié)果最優(yōu)。

序列S′中工件Ji的完工時(shí)間與S中工件Jj的完工時(shí)間之差為

退化參數(shù)滿足

若無(wú)維修活動(dòng),工件一組加工。對(duì)于無(wú)維修活動(dòng)的問(wèn)題,有推論1結(jié)論成立:

推論1 對(duì)于1pjg[i](r),MP[k-1],SpsdCmax問(wèn)題,若無(wú)維修活動(dòng),將pj由大到小排序得到的結(jié)果最優(yōu)。

在1pjg[i](r),MP[k-1],SpsdCmax問(wèn)題中,第1組的完工時(shí)間為第1組的準(zhǔn)備時(shí)間與第1組的實(shí)際加工時(shí)間之和,第1組的安裝時(shí)間s[1]=0,即

F[1]=S[1]+P[1]=P[1]

第2組的完工時(shí)間包括第1組的完工時(shí)間與第1次的維修時(shí)間及第2組的準(zhǔn)備時(shí)間、第2組的實(shí)際加工時(shí)間之和:

F[2]=F[1]+D[1]+S[2]+P[2]=P[1]+aP[1]+bP[1]+P[2]=(1+b+a)P[1]+P[2]

第i組的完工時(shí)間包括第i-1組的完工時(shí)間與第i-1次維修的時(shí)間及第i組的準(zhǔn)備時(shí)間、第i組的實(shí)際加工時(shí)間之和:

F[i]=F[i-1]+D[i-1]+S[i]+P[i]

最大完工時(shí)間就是第k組的完工時(shí)間,即

其中W[i](r)為

W[i](r)是一列常數(shù),目標(biāo)是找到工件的最優(yōu)排序極小化最大完工時(shí)間。設(shè)S(k)表示維修活動(dòng)的數(shù)量為k時(shí)的最優(yōu)排序,Cmax(s(k))表示最優(yōu)排序?yàn)镾(k)時(shí)的最大完工時(shí)間。令H(k)=(g[k](1),g[k](2),…,g[k](n))表示第k組的退化參數(shù),G(k)表示k個(gè)組中,將前n個(gè)最小退化系數(shù)依次記為G(k)=(γ1(k),γ2(k),…,γn(k)),其中γj(k)表示G(k)中第j個(gè)位置的元素。將pj按從大到小排序,將n個(gè)工件依次排在前n個(gè)最小退化系數(shù)對(duì)應(yīng)的位置上,假設(shè)其余位置所排工件的加工時(shí)間等于0。目標(biāo)函數(shù)可表示為

(1)

1pjg[i](r),MP,SpsdCmax問(wèn)題可由算法1的到最優(yōu)排序。

算法1

步驟1 將所有工件按pj由大到小排序。

步驟2 令k=1,H(1)=(g[1](1),g[1](2),…,g[1](n)),G(1)=H(1),γj(r)=g[1](r),1≤r≤n,用公式(1)計(jì)算Cmax(S(1)),令k′=n。

步驟3 令k=2,…,n,定義L(i)=[1+a+(k-i)b](g[i](1),g[i](2),…,g[i](n-k+1)),1≤i≤k-1,在L(i)與H(k)中依次取出n個(gè)最小元素記為G(k),G(k)=(γ1(k),γ2(k),…,γn(k))。用公式(1)計(jì)算Cmax(S(k)),若Cmax(S(k))=Cmax(S(k-1)),則定義k′=k-1,轉(zhuǎn)到第4步,否則繼續(xù)下一個(gè)k值。

步驟4 找到組數(shù)最優(yōu)值k*,k*=k′,用公式(1)計(jì)算Cmax(S(k*)),則Cmax(S(k*))為最優(yōu)解。

步驟3中Cmax(S(k))=Cmax(S(k-1))成立,說(shuō)明G(k)與G(k-1)相同,即第k組沒(méi)有比k-1組中更小的位置退化參數(shù),增加維修活動(dòng)不能使最大完工時(shí)間減小,因此打破循環(huán)得到最優(yōu)解。

結(jié)論1 對(duì)于問(wèn)題1pjg[i](r),MP,SpsdCmax,算法1的計(jì)算復(fù)雜性為O(n2)。

3 特殊情況

特殊的,當(dāng)g[i](r)=g(r),i=1,2,…,k時(shí),問(wèn)題描述為:1pjg(r),MP[k-1],SpsdCmax。問(wèn)題1pjg(r),MP[k-1],SpsdCmax可由算法2得到最優(yōu)排序。

算法2

步驟1 將所有工件按pj由大到小排序。

步驟2 令k=1,定義H(1)=(g(1),g(2),…,g(n)),G(1)=H(1),因此γj(r)=g(r),1≤r≤n,用公式(1)計(jì)算Cmax(S(1)),令k′=n。

步驟3 令k=2,…,n,定義H(k)=[1+a+(k-1)b](g(1),g(2),…,g(n-k+1)),在H(k)與G(k-1)中依次取出n個(gè)最小元素記為G(k),G(k)=(γ1(k),γ2(k),…,γn(k))。用公式(1)計(jì)算Cmax(S(k)),若Cmax(S(k))=Cmax(S(k-1)),則定義k′=k-1,轉(zhuǎn)到第4步,否則繼續(xù)下一個(gè)k值。

步驟4 找到組數(shù)最優(yōu)值k*,k*=k′,用公式(1)計(jì)算Cmax(S(k*)),則Cmax(S(k*))為最優(yōu)解。

結(jié)論2 對(duì)于問(wèn)題1pjg[i](r),MP,SpsdCmax,算法1的計(jì)算復(fù)雜性為O(n2)。

例求下列工件的最優(yōu)排序及在最優(yōu)排序下的最大完工時(shí)間,5個(gè)工件需要在1臺(tái)機(jī)器上進(jìn)行加工,工件的基本加工時(shí)間及退化率分別為

解 按pj由大到小排序?yàn)?J4→J2→J3→J1→J5,

k=1時(shí),

k=2時(shí),

k=3時(shí),

4 結(jié) 語(yǔ)

本文研究了帶有安裝時(shí)間與維修活動(dòng)、退化效應(yīng)的單機(jī)排序問(wèn)題。工件的實(shí)際加工時(shí)間與組合工件的位置有關(guān),最優(yōu)排序不滿足組平衡規(guī)則。在這種情況下,給出了計(jì)算復(fù)雜性為O(n2)的多項(xiàng)式算法。另外,在此基礎(chǔ)上可以進(jìn)行模型推廣,比如工件的實(shí)際加工時(shí)間與工件有關(guān)的情況,也可以考慮工件的加工時(shí)間是帶有資源分配的。