帶惡化和綜合學習效應的成組排序問題研究

孫 麗, 馬衛民

(上海電機學院 商學院,上海 201306)

0 引言

隨著工業生產的發展，工件的加工時間通常會受到很多外部因素的影響而使工件實際加工時間發生改變。在排序中，這種工件加工時間的變化總的分為兩類：一類是工件的實際加工時間比其正常加工時間短，這類因素在排序中被稱為學習效應；另一類是工件的實際加工時間比其正常加工時間長，這類因素被稱為惡化效應。加工時間變化的排序問題是近年來的研究熱點之一。Przybylski[1]研究了基于積分學習效果的并行機排序問題。Bai等[2]討論了帶工件到達時間和學習效應的流水作業排序，對問題給出了分枝定界算法。Ji等[3]研究了一類帶DeJong學習效應的單機和平行機排序，對問題給出了最優算法。

1 模型分析

證明組內工件的排序按常用的相鄰工件交換法容易得證，這里從略；

Ci[1](S1)=θi+(1+δi)t+pi[1]

…

所以，

Ci[ni](S1)=θi+(1+δi)t+Ai[ni],

Cj[1](S1)=θj+(1+δj)Ci[ni](S1)+pj[1],

…

Cj[nj](S1)=θj+(1+δj)(θi+(1+δi)t+Ai[ni])+Aj[nj]

(1)

…

…

(2)

公式(1)和(2)作差可得:

=θi+(1+δi)(θj+(1+δj)t+Aj[nj])+

Ai[ni]-(θj+(1+δj)·

(θi+(1+δi)t+Ai[ni])+Aj[nj])

算法1

步驟1每組內工件按正常加工時間pij非減排列，j=1,2,…,n。

步驟2對每個工件組計算

組間按μ(Gi)非減排列，i=1,2,…,m。

證明組內工件的排序按常用的相鄰工件交換法容易得證，這里從略；

由定理1，可得:

=(ni(1+δi)δj-nj(1+δj)δi)t+ni(1+δi)(θj+Aj[nj])-nj(1+δj)(θj+Ai[ni])

ni(1+δi)δj-nj(1+δj)δi≥0

(3)

ni(1+δi)(θj+Aj[nj])-nj(1+δj)(θi+Ai[ni])≥0

(4)

因此，如果λ(Gi)和η(Gi)有一致關系，在最優排序中，組間排序按λ(Gi)非減排列。

算法2

步驟1組內工件按正常加工時間pij非減排列，j=1,2,…,ni，即pi[1]≤pi[2]≤pi[3]≤…≤pi[ni],i=1,2,3,…,m,(SPT規則)。

步驟3組間按λ(G[i])不減排列，即λ(G[1])≤λ(G[2])≤λ(G[3])≤…≤λ(G[m])。

顯然,算法2的計算復雜性是O(nlogn)。

2 算例分析

方法：

根據算法1， 我們按照如下步驟解決:

步驟1對于工件組G1， 最優的工件序是J11→J12；

對于工件組G2， 最優的工件序是J22→J21→J23；

對于工件組G3,最優的工件序是J31。

步驟2計算可得:μ(G1)=120.16，μ(G2)=75.97，μ(G3)=18.75。易知μ(G3)<μ(G2)<μ(G1)。因此， 最優的組序是：G3→G2→G1，總的最優排序是：[J31]→[J22→J21→J23]→[J11→J12]；各工件的完工時間是：G31=15，G22=27.5，C21=33.658,C21=33.658,G23=42.291，G11=51.5201，G12=58.5361；時間表長是：Cmax=58.5361。

對于問題1|GT,si=θi+δit,GLE|ΣCj，仍然假設第一個工件組開始安裝時間是t=0。

方法：

根據算法2, 我們按照如下步驟解決:

步驟1對于工件組G1， 最優的工件序是J11→J12；

對于工件組G2， 最優的工件序是J22→J21→J23；

對于工件組G3， 最優的工件序是J31→J32。

步驟2計算可得:

λ(G1)=0.0455，λ(G2)=0.077，λ(G3)=0.444，η(G1)=5.462，η(G2)=5.844，η(G3)=8.333，易知,λ(G1)<λ(G2)<λ(G3)，η(G1)<η(G2)<η(G3)。因此，最優的組序：G1→G2→G3，總的最優排序是[J11→J12]→[J22→J21→J23]→[J31]，各工件完工時間是G11=5，G12=12.016，G22=23.6208，G21=29.7788，G23=38.4118，G31=84.1412，總完工時間是：ΣCj=5+12.016+23.6208+29.7788+38.4118+84.1412=192.9686。

3 結論

本文討論了一類綜合學習效應下的成組排序問題。對于極小化時間表長問題給出多項式算法，并證明了具有一致關系的極小化總完工時間問題也是多項式可解的。