極小化兩種目標函數的具有學習效應的單機排序問題

婁 敏，婁宗山

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

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

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

本文研究了具有學習效應和遺忘效應的間歇批生產的單機排序問題，分別討論批與批之間沒有學習效應的傳遞，批與批之間有部分學習效應的傳遞這兩種情形是多項式可解的，針對批與批之間有總的學習效應傳遞的情形，我們給出了在每一批內工件個數都相等這一特殊情形下的多項式時間算法.

1 符號表示

m表示批的個數，m≥2;

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

ai表示Bi內工件的學習因子，0＜ai≤1;

bi表示Bi的學習因子，0＜bi≤1;

pij表示工件Jij的正常加工時間;

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

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

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

Cij表示工件Jij的完工時間;

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

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

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

然而，如果生產線之間中斷的時間比較長，那么可能會出現遺忘效應，即可能出現批與批之間沒有學習效應的傳遞，有部分學習效應的傳遞，有總的學習效應的傳遞這樣三種情形.下面兩部分分別對兩種目標函數下的情形進行探討.

2 極小化最大完工時間

2.1 批與批之間沒有學習效應的傳遞

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

引理1 對于問題1|LE|Cmax的最優排序可以通過工件的正常加工時間的SPT規則得到.

定理1 對于問題1|B，LE，Tno|Cmax存在一個最優排序滿足下面兩個條件:

(1)對于每一批內的工件，按正常加工時間的SPT規則排列;

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

證明(1)每一批內的工件的最優排序問題等價于問題1|LE|Cmax，根據引理1，按工件的正常加工時間的SPT規則排列即可得最優排序.

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

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

算法2.1 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

2.2 批與批之間有部分學習效應的傳遞

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

用Tpart表示批與批之間有部分學習效應的傳遞，那么該問題用三參數表示法記為1|B，LE，Tpart| C.

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

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

算法2.2 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

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

(a)對于每一批內的工件，按正常加工時間的SPT規則排列;

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

證明 (a)對于每一批內的工件，根據引理1可知按照SPT規則得到最優排序;

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

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

2.3 批與批之間有總的學習效應的傳遞

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

定理2 對于問題1|B，LE，Ttotal|Cmax，每一批的最大完工時間的最優值可以按工件的正常加工時間的SPT規則排列得到.

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

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

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

這說明π'也是最優排序.對π中不滿足SPT規則排序的工件進行調整，直到它們都滿足SPT序為止，由此得到滿足定理的最優排序.

推論2 對于問題1|B，LE，Ttotal|Cmax，存在一個最優排序使得每一批內的工件都按正常加工時間的SPT規則排列.

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

第1種特殊情況:

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

如果

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

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

(a)對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

下面給出當n1=n2=…nm=ˉn時，求解問題1|B，LE，Ttotal|Cmax的最優算法:

算法2.3 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

3 極小化總完工時間

3.1 批與批之間沒有學習效應的傳遞

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

引理2 對于問題1‖ΣCj，其最優排序可以通過SPT規則得到.

引理3 對于問題1|LE|ΣCj的最優排序可以通過正常加工時間的SPT規則得到.

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

算法3.1 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

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

證明 對于每一批內的工件的最優排序問題等價于問題1|LE|ΣCj，根據引理3，每一批的工件按照正常加工時間的SPT規則排序即可得最優排序.

因為批與批之間沒有學習效應的傳遞，所以可以把每一批看做一個工件，批的完工時間Pi作為Bi的加工時間，則問題1|B，LE，Tno|ΣΣCij等價于問題1‖ΣCj，那么由引理2知，批與批之間按照Pi不減的順序排列即可得最優排序.

3.2 批與批之間有部分學習效應的傳遞

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

記

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

算法3.2 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

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

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

證明 對于每一批內的工件，根據引理3知，按照SPT規則得到最優排序;如果所有批的學習因子都相等，那么可以將每一批看做一個工件，Pi作為Bi的加工時間，那么問題1|B，LE，Tpart|ΣΣCij等價于問題1|LE|ΣCj，由引理3知按照Pi不減的順序排列即可得最優排序.

3.3 批與批之間有總的學習效應的傳遞

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

定理6 對1|B，LE，Ttotal|ΣΣCij問題，每一批內工件的總完工時間的SPT最優值可以按正常加工時間的規則排列得到.

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

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

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

這說明π'也是最優排序.對π中不滿足SPT規則排序的工件進行調整，直到它們都滿足SPT序為止，由此得到滿足定理的最優排序.

推論4 對于問題1|B，LE，Ttotal|ΣΣCij存在一個最優排序使得每一批內的工件按正常加工時間的SPT規則排列.

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

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

下面給出當n1=n2=…=nm=ˉn時，求解問題1|B，LE，Ttotal|ΣΣCij的最優算法:

算法3.3 第1步 對于每一批內的工件，按正常加工時間的SPT規則排列;

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

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

定理7 當每一批內工件的個數都相等時，算法3.3能最優的解決問題1|B，LE，Ttotal|ΣΣCij.

［1］唐國春，張峰，羅守成，等.現代排序論［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］王吉波，王明征.具有一般學習效應的單機排序問題［J］.數學研究與評論，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.