極小化兩種目標(biāo)函數(shù)的具有學(xué)習(xí)效應(yīng)的單機(jī)排序問題

婁 敏，婁宗山

(1.曲阜師范大學(xué)管理學(xué)院，山東日照 276826;2.山東省諸城第一中學(xué)，山東諸城 262200)

最近幾年來，關(guān)于學(xué)習(xí)效應(yīng)的排序問題受到了國(guó)內(nèi)外許多學(xué)者的廣泛關(guān)注.在經(jīng)典的排序理論中，工件的加工時(shí)間通常都被看做是一個(gè)固定的常數(shù).然而，在許多現(xiàn)實(shí)情況中，如機(jī)器或工人反復(fù)或連續(xù)加工相同或類似的工件時(shí)，由于他們能從中學(xué)習(xí)到如何更加有效的完成工件的生產(chǎn)，因此越在后面的工件它所需要的加工時(shí)間就越少，這種現(xiàn)象就是“學(xué)習(xí)效應(yīng)”.

唐國(guó)春等［1］對(duì)現(xiàn)代排序問題的10個(gè)分支進(jìn)行了系統(tǒng)詳細(xì)的討論.Biskup［2］首次將學(xué)習(xí)效應(yīng)應(yīng)用于排序問題當(dāng)中，他提出了一個(gè)工件的加工時(shí)間與工件所在位置有關(guān)的學(xué)習(xí)效應(yīng)模型;在單機(jī)條件下，他研究了目標(biāo)函數(shù)為極小化總完工時(shí)間的排序問題，得到了工件按照規(guī)則排列獲得最優(yōu)排序.Yang和Kuo［3］對(duì)于Biskup［2］提出的學(xué)習(xí)效應(yīng)模型研究了具有學(xué)習(xí)效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問題，并且給出了目標(biāo)函數(shù)為極小化最大完工時(shí)間這一問題的多項(xiàng)式時(shí)間算法.Kuo和Yang［4－5］給出一種與時(shí)間有關(guān)的學(xué)習(xí)效應(yīng)模型并且進(jìn)行了深入研究，給出了相應(yīng)的多項(xiàng)式時(shí)間算法.王吉波等［6－7］繼續(xù)對(duì)帶學(xué)習(xí)效應(yīng)的排序問題進(jìn)行了探討，將安裝時(shí)間，惡化效應(yīng)等應(yīng)用到帶學(xué)習(xí)效應(yīng)的排序問題中，并且給出了最優(yōu)算法.

本文研究了具有學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問題，分別討論批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞，批與批之間有部分學(xué)習(xí)效應(yīng)的傳遞這兩種情形是多項(xiàng)式可解的，針對(duì)批與批之間有總的學(xué)習(xí)效應(yīng)傳遞的情形，我們給出了在每一批內(nèi)工件個(gè)數(shù)都相等這一特殊情形下的多項(xiàng)式時(shí)間算法.

1 符號(hào)表示

m表示批的個(gè)數(shù)，m≥2;

Bi表示第i批，i=1，2，…，m; ni表示第i批的工件個(gè)數(shù)，i=1，2，…，m; n表示工件的總個(gè)數(shù)，n1+n2+…+nm=n; Jij表示第i批中的第j個(gè)工件，j=1，2，…，ni;

ai表示Bi內(nèi)工件的學(xué)習(xí)因子，0＜ai≤1;

bi表示Bi的學(xué)習(xí)因子，0＜bi≤1;

pij表示工件Jij的正常加工時(shí)間;

pr表示工件J在B中排在第r個(gè)位置上加工的實(shí)際加工時(shí)間;ijiji

pi［k］表示工件Ji［k］在Bi中排在第k個(gè)位置上加工的正常加工時(shí)間;

pk表示工件J在B中排在第k個(gè)位置上加工的實(shí)際加工時(shí)間;i［k］i［k］i

Cij表示工件Jij的完工時(shí)間;

Ci［k］表示工件Ji［k］在Bi中排在第k個(gè)位置上加工的完工時(shí)間;

Cmax表示所有工件的最大完工時(shí)間;為所有工件的總完工時(shí)間.

所有n個(gè)工件被分成m批放在一臺(tái)機(jī)器上進(jìn)行加工，并且所有工件在0時(shí)刻都是準(zhǔn)備就緒的.如果工件被安排在第一批的第一個(gè)位置上進(jìn)行加工，那么它的實(shí)際加工時(shí)間就是它的正常加工時(shí)間.由于學(xué)習(xí)效應(yīng)的存在，被加工的工件越往后，它所需要的加工時(shí)間就越少.為描述方便，我們用LE表示學(xué)習(xí)效應(yīng);B表示間歇的批生產(chǎn)問題.定義，其中α，β，ai均為常數(shù)，且滿足α≥0，β≥0，α+ β=1，0＜ai＜1.

然而，如果生產(chǎn)線之間中斷的時(shí)間比較長(zhǎng)，那么可能會(huì)出現(xiàn)遺忘效應(yīng)，即可能出現(xiàn)批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞，有部分學(xué)習(xí)效應(yīng)的傳遞，有總的學(xué)習(xí)效應(yīng)的傳遞這樣三種情形.下面兩部分分別對(duì)兩種目標(biāo)函數(shù)下的情形進(jìn)行探討.

2 極小化最大完工時(shí)間

2.1 批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞

Jij被安排在Bi中的第r個(gè)位置上加工的實(shí)際的加工時(shí)間表示為prij=pij(αari－1+β).因此，若Bi在第i批加工，那么所有工件的最大完工時(shí)間為).用Tno表示批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞，因此根據(jù)排序理論中經(jīng)典的三參數(shù)表示法將該問題記為:1|B，LE，Tno|Cmax.

引理1 對(duì)于問題1|LE|Cmax的最優(yōu)排序可以通過工件的正常加工時(shí)間的SPT規(guī)則得到.

定理1 對(duì)于問題1|B，LE，Tno|Cmax存在一個(gè)最優(yōu)排序滿足下面兩個(gè)條件:

(1)對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

(2)批與批之間按照任意次序在機(jī)器上加工.

證明(1)每一批內(nèi)的工件的最優(yōu)排序問題等價(jià)于問題1|LE|Cmax，根據(jù)引理1，按工件的正常加工時(shí)間的SPT規(guī)則排列即可得最優(yōu)排序.

(2)批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞，因此批的加工時(shí)間并不受其所在位置的影響，所以批與批之間按照任意次序在機(jī)器上加工即可.

下面給出求解問題1|B，LE，Tno|Cmax的最優(yōu)算法:

算法2.1 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 批與批之間按照任意次序在機(jī)器上加工.

在第1步中，將Bi內(nèi)的工件按照SPT規(guī)則排列，其時(shí)間復(fù)雜性為O(nilog ni)，那么對(duì)所有批內(nèi)的工件排序花費(fèi)時(shí)間為iΣm=1O(nilog ni)，所以第1步的時(shí)間復(fù)雜性為O(n log n);第2步，批與批之間按照任意次序排列花費(fèi)時(shí)間為O(1)，因此算法A的時(shí)間復(fù)雜性為O(n log n).

2.2 批與批之間有部分學(xué)習(xí)效應(yīng)的傳遞

假設(shè)每一批內(nèi)的工件的學(xué)習(xí)效應(yīng)與2.1一致.定義Bi被安排在第r批加工的實(shí)際加工時(shí)間:Pir= Pi(αbri－1+β)，其中Pi為Bi內(nèi)的工件按照SPT規(guī)則排序的完工時(shí)間，并且Pi不受批所在位置的影響.若Bi在第i批加工，于是有

用Tpart表示批與批之間有部分學(xué)習(xí)效應(yīng)的傳遞，那么該問題用三參數(shù)表示法記為1|B，LE，Tpart| C.

max記|C，那么問題1|B，LE，Tpartmax的批的加工次序問題可轉(zhuǎn)化為下面的指派問題來求解:

下面給出求解問題1|B，LE，Tpart|Cmax的最優(yōu)算法:

算法2.2 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 根據(jù)指派問題(i)來安排批的加工次序.

第1步的時(shí)間復(fù)雜性為O(n log n)，第2步求解指派問題花費(fèi)的時(shí)間是O(m3)，因此算法2.2的時(shí)間復(fù)雜性為O(n log n+m3).

推論1 若所有批的學(xué)習(xí)因子都相等，即bi=b(i=1，…，m)，那么對(duì)于問題1|B，LE，Tpart|Cmax存在一個(gè)最優(yōu)排序滿足下面兩個(gè)條件:

(a)對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

(b)批與批之間按照Pi不減的順序排列.

證明 (a)對(duì)于每一批內(nèi)的工件，根據(jù)引理1可知按照SPT規(guī)則得到最優(yōu)排序;

(b)如果所有批的學(xué)習(xí)因子都相等，那么可以將每一批看做一個(gè)工件，批的完工時(shí)間Pi作為Bi的加工時(shí)間，因此問題1|B，LE，Tpart|Cmax等價(jià)于問題1|LE|Cmax，根據(jù)引理1知按照Pi不減的順序排列即可得最優(yōu)排序.

由推論1知，(a)的時(shí)間復(fù)雜性為O(n log n);(b)中對(duì)批的次序排列需花費(fèi)時(shí)間O(m log m)，由于n＞m，因此在bi=b(i=1，…，m)這一特殊情形下，問題1|B，LE，Tpart|Cmax的時(shí)間復(fù)雜性為O(n log n).

2.3 批與批之間有總的學(xué)習(xí)效應(yīng)的傳遞

不失一般性，我們假設(shè)Bi是在第i批加工，那么Bi中的工件Jij在第r個(gè)位置上加工時(shí)，其實(shí)際加工時(shí)間為，因此有.用T表示批與批之間有總的total學(xué)習(xí)效應(yīng)的傳遞，那么該問題用三參數(shù)表示法記為1|B，LE，Ttotal|Cmax.

定理2 對(duì)于問題1|B，LE，Ttotal|Cmax，每一批的最大完工時(shí)間的最優(yōu)值可以按工件的正常加工時(shí)間的SPT規(guī)則排列得到.

證明 假設(shè)π為一最優(yōu)排序，對(duì)于Bi中的兩個(gè)工件Jij和Jil，滿足pij≥pil，Jij在Bi中的第r個(gè)位置上加工，Jil在Bi中的第r+1個(gè)位置上加工.令s為第r－1個(gè)位置上工件的完工時(shí)間，B為在Jij和Jil之后加工的工件的加工時(shí)間之和.

交換工件Jij和Jil的位置得到一個(gè)新的排序π'，π'中交換Jij和Jil的位置后s和B不變

由α≥0，β≥0，α+β=1，0＜ai≤1知.因此有

這說明π'也是最優(yōu)排序.對(duì)π中不滿足SPT規(guī)則排序的工件進(jìn)行調(diào)整，直到它們都滿足SPT序?yàn)橹?，由此得到滿足定理的最優(yōu)排序.

推論2 對(duì)于問題1|B，LE，Ttotal|Cmax，存在一個(gè)最優(yōu)排序使得每一批內(nèi)的工件都按正常加工時(shí)間的SPT規(guī)則排列.

下面我們討論問題1|B，LE，Ttotal|Cmax的兩種特殊情況:

第1種特殊情況:

定義1 Bi?Bj表示Bi被Bj支配或者Bj支配Bi:

如果

定義2 如果B1?B2?…?Bm，就說形成了支配批的增序.

定理3 若B1?B2?…?Bm并且a1=a2=…=am，那么對(duì)于問題1|B，LE，Ttotal|Cmax存在一個(gè)最優(yōu)排序滿足下面兩個(gè)條件:

(a)對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

(b)批與批之間按支配批的增序排列.

第2種特殊情況: =n=…=n=ˉn如果每一批內(nèi)工件的個(gè)數(shù)都相等，即n12m，記，則問題1|B，LE，Ttotal|Cmax的批的加工次序問題可轉(zhuǎn)化為下面的指派問題來求解:

下面給出當(dāng)n1=n2=…nm=ˉn時(shí)，求解問題1|B，LE，Ttotal|Cmax的最優(yōu)算法:

算法2.3 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 根據(jù)指派問題(ii)來安排批的加工次序.

算法2.3的時(shí)間復(fù)雜性為O(n log n+m3).

3 極小化總完工時(shí)間

3.1 批與批之間沒有學(xué)習(xí)效應(yīng)的傳遞

根據(jù)排序理論中經(jīng)典的三參數(shù)表示法將該問題記為:1|B，LE，Tno|ΣΣCij.

引理2 對(duì)于問題1‖ΣCj，其最優(yōu)排序可以通過SPT規(guī)則得到.

引理3 對(duì)于問題1|LE|ΣCj的最優(yōu)排序可以通過正常加工時(shí)間的SPT規(guī)則得到.

記P為B按照SPT規(guī)則排序的完工時(shí)間ii，下面我們給出求解問題1|B， LE，Tno|ΣΣCij的最優(yōu)算法:

算法3.1 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 批與批之間按照Pi非減的次序在機(jī)器上加工.

算法3.1的時(shí)間復(fù)雜性為O(n log n).

定理4 算法3.1最優(yōu)的解決了問題1|B，LE，Tno|ΣΣCij.

證明 對(duì)于每一批內(nèi)的工件的最優(yōu)排序問題等價(jià)于問題1|LE|ΣCj，根據(jù)引理3，每一批的工件按照正常加工時(shí)間的SPT規(guī)則排序即可得最優(yōu)排序.

因?yàn)榕c批之間沒有學(xué)習(xí)效應(yīng)的傳遞，所以可以把每一批看做一個(gè)工件，批的完工時(shí)間Pi作為Bi的加工時(shí)間，則問題1|B，LE，Tno|ΣΣCij等價(jià)于問題1‖ΣCj，那么由引理2知，批與批之間按照Pi不減的順序排列即可得最優(yōu)排序.

3.2 批與批之間有部分學(xué)習(xí)效應(yīng)的傳遞

假設(shè)每一批內(nèi)的工件的學(xué)習(xí)效應(yīng)與3.1一致.定義Bi被安排在第r批加工的實(shí)際加工時(shí)間:Pir=，其中為Bi內(nèi)的工件按照SPT規(guī)則排序的完工時(shí)間，并且Pi不受批所在位置的影響.記Ci表示在批與批之間沒有學(xué)習(xí)效應(yīng)傳遞的情況下每一批內(nèi)的所有工件的總完工時(shí)間，有該問題用三參數(shù)表示法記為1|B，LE，Tpart|ΣΣCij.

記

那么問題1|B，LE，Tpart|ΣΣCij的批的加工次序問題可轉(zhuǎn)化為下面的指派問題來求解:

算法3.2 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 根據(jù)指派問題(iii)來安排批的加工次序.

算法3.2的時(shí)間復(fù)雜性為O(n log n+m3).

定理5 算法3.2最優(yōu)的解決了問題1|B，LE，Tpart|ΣΣCij.

推論3 如果所有批的學(xué)習(xí)因子都相等，即bi=b(i=1，…，m)，那么對(duì)于問題1|B，LE，Tpart|ΣΣCij，算法3.1為最優(yōu)算法.

證明 對(duì)于每一批內(nèi)的工件，根據(jù)引理3知，按照SPT規(guī)則得到最優(yōu)排序;如果所有批的學(xué)習(xí)因子都相等，那么可以將每一批看做一個(gè)工件，Pi作為Bi的加工時(shí)間，那么問題1|B，LE，Tpart|ΣΣCij等價(jià)于問題1|LE|ΣCj，由引理3知按照Pi不減的順序排列即可得最優(yōu)排序.

3.3 批與批之間有總的學(xué)習(xí)效應(yīng)的傳遞

不失一般性，我們假設(shè)Bi是在第i批加工，那么Bi中的工件Jij在第r個(gè)位置上加工時(shí)，其實(shí)際加工時(shí)間為，該問題可以用三參數(shù)表示法記為1|B，LE，Ttotal|ΣΣCij.

定理6 對(duì)1|B，LE，Ttotal|ΣΣCij問題，每一批內(nèi)工件的總完工時(shí)間的SPT最優(yōu)值可以按正常加工時(shí)間的規(guī)則排列得到.

證明 假設(shè)π為一最優(yōu)排序，對(duì)于Bi中的兩個(gè)工件Jij和Jil，滿足pij≥pil，Jij在Bi中的第r個(gè)位置上加工，Jil在Bi中的第r+1個(gè)位置上加工.令s表示在Bi中第r－1個(gè)位置上加工工件的完工時(shí)間，A和B分別表示在Jij和Jjl之前和之后加工的工件的總完工時(shí)間.

交換工件Jij和Jil的位置得到一個(gè)新的排序π'，π'中交換Jij和Jjl的位置后，A不變.

由α≥0，β≥0，α+β=1，0＜ai≤1知，所以有

這說明π'也是最優(yōu)排序.對(duì)π中不滿足SPT規(guī)則排序的工件進(jìn)行調(diào)整，直到它們都滿足SPT序?yàn)橹?，由此得到滿足定理的最優(yōu)排序.

推論4 對(duì)于問題1|B，LE，Ttotal|ΣΣCij存在一個(gè)最優(yōu)排序使得每一批內(nèi)的工件按正常加工時(shí)間的SPT規(guī)則排列.

下面我們討論問題1|B，LE，Ttotal|ΣΣCij的一種特殊情況:

如果每一批內(nèi)工件的個(gè)數(shù)都相等，即n1=n2=…=nm=ˉn，記，則問題1|B，LE，Ttotal|ΣΣCij的批的加工次序問題可轉(zhuǎn)化為下面的指派問題來求解:

下面給出當(dāng)n1=n2=…=nm=ˉn時(shí)，求解問題1|B，LE，Ttotal|ΣΣCij的最優(yōu)算法:

算法3.3 第1步 對(duì)于每一批內(nèi)的工件，按正常加工時(shí)間的SPT規(guī)則排列;

第2步 根據(jù)指派問題(iv)來安排批的加工次序.

算法3.3的時(shí)間復(fù)雜性為O(n log n+m3).

定理7 當(dāng)每一批內(nèi)工件的個(gè)數(shù)都相等時(shí)，算法3.3能最優(yōu)的解決問題1|B，LE，Ttotal|ΣΣCij.

［1］唐國(guó)春，張峰，羅守成，等.現(xiàn)代排序論［M］.上海:上海出版社，2003.

［2］Biskup D.Single－machine schedulingwith learning considerations［J］.European Journal of Operational Research，1999，(115):173－178.

［3］D.L.Yang，W.H.Kuo.A single－machine Scheduling problem with learning effects in intermittent batch production［J］.Computer and Industrial Engineering，2009，(57):762－765.

［4］KuoW H，Yang D L.Minimizing themakespan in a single－machine scheduling problem with a time－based learning effect［J］.Information Processing Letters，2006，(97):64－67.

［5］KuoW H，Yang D L.Minimizing the total completion time in a single－machine scheduling problem with a time－dependent learning effect［J］.Eruopean Journal of Operational Research，2006，(174):1184－1190.

［6］王吉波，王明征.具有一般學(xué)習(xí)效應(yīng)的單機(jī)排序問題［J］.數(shù)學(xué)研究與評(píng)論，2005，25(4):642－646.

［7］Wang JB.Singlemachine scheduling with a time－dependent learning effect and deteriorating jobs［J］.Journal of the Operational Research Society，2009，(57):9－16.