考慮加工時間和交貨期模糊的批調(diào)度問題研究

王雷雷，趙永中，司佳佳，李小林

（中國礦業(yè)大學(xué)礦業(yè)工程學(xué)院，江蘇 徐州 221116）

1 引言

批處理機調(diào)度問題廣泛存在于半導(dǎo)體加工、鋼鐵的熱處理、港口貨物裝卸等生產(chǎn)場景中。不同于經(jīng)典調(diào)度問題，批處理機可以將多個工件作為一批同時進行加工。其中，半導(dǎo)體加工的熱處理操作是典型的批處理機調(diào)度過程，該加工過程中，多個工件作為一批同時進行預(yù)燒處理以識別出早期失效的產(chǎn)品，根據(jù)產(chǎn)品的類型、質(zhì)量等級等要求不同，預(yù)燒的時間甚至?xí)L達(dá)120h，從而很容易成為瓶頸工序。

當(dāng)產(chǎn)品可靠度水平要求不同時，其預(yù)燒時間通常會是一個區(qū)間值，同時隨著當(dāng)前生產(chǎn)實際中顧客需求不確定性提高，產(chǎn)品的交期也經(jīng)常出現(xiàn)大幅波動，因此對考慮模糊加工時間和交期的成批調(diào)度問題進行研究，并以滿意度為目標(biāo)設(shè)計算法對問題進行求解。

對于單機環(huán)境下批處理機調(diào)度問題，文獻［1］首先對工件具有差異尺寸的預(yù)燒模型進行研究，證明該問題是強NP 難的。文獻［2］提出了一種改進的粒子群算法，解決了求最小化最大延遲懲罰的單機批調(diào)度問題。文獻［3］研究了相同交貨期的差異尺寸工件批調(diào)度問題，用精確算法對最小化工件總提前和延遲的目標(biāo)進行求解。文獻［4］研究了目標(biāo)為最小化工件最大延遲的單機批調(diào)度問題，提出了一種改進的粒子群優(yōu)化算法。文獻［5］提出了蟻群-魚群混合算法來解決最小化工件制造跨度的目標(biāo)。文獻［6］研究了在單批處理機上最小化工件完工時間的問題，提出了最大最小蟻群算法對該問題進行求解。

上述研究均是建立在時間參數(shù)確定的基礎(chǔ)上，但工件在實際加工過程中，由于工人和機器的不確定性，產(chǎn)品可靠性要求不同，加工信息不能準(zhǔn)確預(yù)知，相關(guān)的時間參數(shù)是模糊的，進而具體交貨期也無法確定。隨著模糊調(diào)度理論在生產(chǎn)實際中的運用越來越廣泛，更多的學(xué)者開始投入到模糊環(huán)境批調(diào)度的研究中。文獻［7］考慮了模糊加工時間，建立了模糊完工時間模型，設(shè)計了蟻群算法，并采用特殊標(biāo)準(zhǔn)來選擇螞蟻的路徑。文獻［8］用梯形模糊數(shù)表示模糊交貨期，研究目標(biāo)轉(zhuǎn)化為決策者對該工件完成時間具有的滿意度，并使用改進的帝國主義競爭算法（MICA）對問題進行求解。文獻［9］建立了模糊環(huán)境下的批容量問題、優(yōu)先約束問題、交貨期問題和加工時間問題的一些單機批加工調(diào)度模型，并且給出了相應(yīng)的求解算法。文獻［10］基于模糊加工時間和模糊交貨期建立了三種調(diào)度問題的模型，并采用遺傳算法搜索最優(yōu)排序。文獻［11］同時考慮模糊加工時間和模糊交貨期，兩者均用三角模糊數(shù)表示，對于最小化工件的提前和延遲目標(biāo)提出了一種混合的差分粒子群算法。文獻［12］研究了模糊環(huán)境下的并行批處理機問題，以最小化完工時間為優(yōu)化目標(biāo)，提出了模糊蟻群優(yōu)化算法對問題進行求解。

現(xiàn)有研究大多考慮一種模糊量或者使用相同模糊數(shù)表示多個模糊量，而實際生產(chǎn)中，工件加工時間受加工特征及機器的影響與生產(chǎn)計劃所確定的顧客訂單交期通常具有不同的模糊數(shù)特征。因此，對工件加工時間與交貨期采用不同模糊數(shù)的批處理機調(diào)度問題進行研究，結(jié)合現(xiàn)有文獻中對加工時間和交期的模糊處理方式，分別采用三角模糊數(shù)和梯形模糊數(shù)表征工件的模糊加工時間和模糊交貨期。由于不同類型模糊數(shù)運算的差異，進一步將工件延遲轉(zhuǎn)化為完工時間相對于交期的滿意度，建立了工件模糊交貨期和模糊加工時間的隸屬度函數(shù)與決策滿意度的函數(shù)關(guān)系。在此基礎(chǔ)上提出模糊批調(diào)度數(shù)學(xué)模型，設(shè)計了改進帝國主義競爭算法對該問題進行求解，并通過仿真實驗對算法求解效果進行分析。

2 模糊環(huán)境下單機批調(diào)度問題

2.1 問題描述

模糊環(huán)境下單機批調(diào)度問題可描述如下：將n個工件的集合J={1 ，2，3，…，n} 安排在一臺批處理機M上加工，任一工件j具有差異化的尺寸sj。在滿足機器容量的條件下，可將多個工件分配至同一批進行加工。任一工件只分配至一個批中進行加工，批加工過程不允許中斷。

考慮實際生產(chǎn)中加工時間的不確定性，采用三角模糊數(shù)表示工件模糊加工時間，即工件j在批處理機上的加工時間為(pj1，pj2，pj3)，采用梯形模糊數(shù)表示工件模糊交貨期，任一工件j具有模糊交貨期晚于交貨期完工的工件j賦予一定的延遲懲罰βj。

工件j的加工時間隸屬函數(shù)，如圖1所示。

圖1 工件加工時間隸屬函數(shù)圖Fig.1 Membership Function Graph for Processing Time of Job

在模糊加工環(huán)境下，工件j的完工時間等于所屬批的模糊完工時間，任一批b的模糊完工時間由批工件的模糊加工時間取大得到，即批b的完工時間可由其所處位置k計算得到則工件完工時間隸屬度函數(shù)，如式（1）所示。

2.2 優(yōu)化目標(biāo)

當(dāng)采用梯形模糊數(shù)表示模糊交期時，工件的最優(yōu)交期會處于一個模糊區(qū)間，為了避免拖期，需要將工件盡量安排在模糊交期范圍內(nèi)完成交貨。因此，批完工時間相對于交貨期梯形模糊數(shù)所處的位置即表達(dá)了顧客對于該完工時間的滿意程度。即顧客滿意度可根據(jù)交貨期梯形模糊數(shù)的后半部分與工件模糊完工時間運算取得?？捎枚M（dj1，dj2）來表示完工時間相對于交期的滿意度，這里，dj1和dj2分別表示工件j交貨期模糊數(shù)的后兩個參數(shù)，即工件j按時交貨時間與拖后交貨時間。從而，工件j的交貨期隸屬函數(shù)可，如圖2所示。相應(yīng)的隸屬度函數(shù)，如式（2）所示。

圖2 工件交貨期隸屬函數(shù)圖Fig.2 Membership Function Graph for Due Date of Job

顯然，滿意度指數(shù)隨著交貨期隸屬度函數(shù)與完工時間隸屬度函數(shù)疊加區(qū)域的變化而變化，可能具有重疊區(qū)域，也可能無交集。當(dāng)二者無重疊區(qū)域時S1=0 ，則滿意度指數(shù)AI=0 ；當(dāng)二者重疊區(qū)域S1=S，則滿意度指數(shù)AI=1 ；否則重疊區(qū)域會出現(xiàn)如下三類部分重疊的情況，如圖3所示。

圖3 隸屬度函數(shù)重疊區(qū)域Fig.3 Membership Function Overlap Region

根據(jù)圖3中完工時間及交貨期隸屬函數(shù)重疊區(qū)域，可得三種情況下滿意度指數(shù)分別為：

2.3 優(yōu)化模型

問題所涉及參量說明如下：

cap：機器容量；sj：工件j尺寸；

SIj：工件j不滿意度指數(shù)，SIj=1-AIj；

βj：工件j延遲懲罰系數(shù)。

結(jié)合問題描述及滿意度定義，建立考慮模糊加工時間和交貨期的批調(diào)度問題數(shù)學(xué)優(yōu)化模型如下：

式（6）表示目標(biāo)函數(shù)為最小化不滿意度UD，其中SI由上述不滿意度公式計算；約束（7）表示決策變量；約束（8）表示一個工件僅出現(xiàn)在一個批中；約束（9）表示任一個批的工件加工尺寸之和不得超過機器容量；約束（10）表示任一個批的模糊加工時間取決于對該批中所有工件進行模糊取大操作；約束（11）表示模糊批完工時間；約束（12）表示工件模糊完工時間與所在批相同；約束（13）和（14）確保每批的開始時間大于或等于其前一批的完成時間。

3 求解算法設(shè)計

帝國主義競爭算法（ICA）由文獻［13］首次提出，其基本思想來源于帝國主義殖民競爭機制。近年來帝國主義競爭算法的應(yīng)用越來越廣泛，文獻［14］對帝國競爭算法進行了改進，解決了虛擬裝配過程中裝配序列規(guī)劃的問題。

ICA把種群比喻為世界，種群中的個體為國家，解的優(yōu)越性與國家能力的大小具有一致性。一個帝國由一個宗主國組成，宗主國擁有多個殖民地。殖民地受所屬宗主國以及其他帝國中的宗主國和殖民地的影響，會發(fā)生移動。當(dāng)殖民地的成本低于其宗主國成本時，兩者位置互換，然后帝國之間競爭吞并。在下一次競爭中，強者獲勝，循環(huán)往復(fù)直至最后，世界只剩下一個帝國，完成算法搜索。

3.1 帝國集團編碼與初始化

在帝國主義算法中，每個解稱為一個國家，對于n個工件的成批調(diào)度問題，每一個解可以表示成一個n維的向量，Ki=(k1，k2，k3，...，kn)，即表示第i個國家，向量中的每個分量為該位置的工件編號，采用隨機鍵（Random Key）編碼的方式隨機生成工件序列集合作為初始國家集合。

3.2 國家成本函數(shù)計算

為了直觀的評判一個國家勢力的強弱，用成本函數(shù)作為標(biāo)準(zhǔn)：Ci=f(Ki)。成本函數(shù)與國家勢力成反比。成本函數(shù)用于計算給定問題的目標(biāo)函數(shù)，對應(yīng)不滿意度。

對于任一工件序列，設(shè)計BFEDD分批規(guī)則來求解每個國家的成本函數(shù)如下：

算法BFEDD（Best Fit Earliest Due Date）：

（1）選擇工件序列首部第一個工件，將其放入到當(dāng)前可以容納它且該批次剩余容量為最小的批中。如果所有工件分配完畢，轉(zhuǎn)（3）；

（2）若現(xiàn)有批次均無法容納該工件，創(chuàng)建新批，轉(zhuǎn)（1）。

（3）將批列表按交期非減排序，并順序安排至機器，得出任一批的完工時間。

（4）結(jié)合2.2節(jié)中各AI計算公式，計算任一工件滿意度指數(shù)，以及總體不滿意度指數(shù)，即為成本函數(shù)。

假設(shè)所有國家數(shù)為N，其中有Nimp個國家由于勢力強大成為宗主國，則剩下的Ncol個國家成為殖民地，且N=Nimp+Ncol。殖民地按一定的比例分配給宗主國，Nimp個宗主國獲取相應(yīng)的殖民地后，則建立了Nimp個帝國。

3.3 帝國同化殖民地策略改進

同化政策發(fā)生在每個帝國內(nèi)部，是殖民地向宗主國不斷靠近的過程，具體是指沿著宗主國和該殖民地間連線隨機移動一個距離x，其中，x必須滿足均勻分布：x～U(0，α*d)，α為大于1的數(shù)，通常取α=2。為了增加算法的搜索廣度，賦予一個隨機角度偏移量θ，且θ滿足均勻分布：θ～(-γ，γ)，通常情況下γ=π/4。

為了避免在同化過程中搜索方向單一，即殖民地只受所屬宗主國的影響的情況，這里考慮殖民地同時受所屬宗主國和帝國中的其他殖民地以及其他帝國中的宗主國的影響。同時，國家之間的“距離”越小，產(chǎn)生的影響越大。為了提高算法的全局搜索能力，同時考慮不同國家之間距離的非線性影響，國家之間的吸引力計算設(shè)計如下。

用OFi表示目標(biāo)函數(shù)，wi代表國家勢力，di代表兩個國家間的距離。其他宗主國對該殖民地的吸引力為γi，殖民地對殖民地的吸引力為η。

當(dāng)國家1受到超過三個國家的影響時，此時國家1移動后的情況如式（16）。

式中：α1—國家1維持原狀的可能性；αi(i=2，3，4)—國家1向各個國家移動的概率，0 ≤αi≤1，—當(dāng)事國的現(xiàn)狀；ximp1—所屬宗主國的現(xiàn)狀；ximp2+ximp3+...+ximpN—相鄰宗主國的現(xiàn)狀；xcol2+xcol3+...+xcolM—同一帝國中，其他殖民地的近況，隨機數(shù)ri(i=1，2，3，4)∈[ 0，1 ]。

當(dāng)殖民地在多方國家影響下到達(dá)一個新位置時，在新位置上的勢力可能比其宗主國的勢力更大，其成本也更低。此時，就將該殖民地和宗主國的位置互換。

3.4 改進的帝國主義競爭算法

改進的帝國主義競爭算法（IICA）步驟如下：

（1）根據(jù)帝國集團編碼方法，生成N個國家，完成國家初始化。

（2）根據(jù)國家成本函數(shù)計算方法，對帝國集團任一國家Ki計算其當(dāng)前的成本函數(shù)。確定了Nimp個帝國后，每個帝國中的宗主國對應(yīng)的成本函數(shù)做為當(dāng)前帝國的最優(yōu)解。

（3）根據(jù)同化策略改進方法，計算每個帝國中殖民地同化后的成本函數(shù)，若小于其宗主國的成本，則將當(dāng)前最優(yōu)解更新。帝國之間進行競爭，計算每個帝國的總成本，勢力大的帝國吞并勢力小的帝國中的國家，消除最弱帝國。

（4）判斷算法終止條件（達(dá)到最大迭代次數(shù)Nmax或最終剩下一個帝國），若滿足終止條件，則輸出最終的調(diào)度方案及不滿意度，否則轉(zhuǎn)（3）。

4 仿真實驗

4.1 參數(shù)選取

這里采用隨機方法產(chǎn)生算例，算例的規(guī)模包括工件個數(shù)（n），工件的加工時間工件尺寸和工件交貨期。pj2大小服從均勻分布，分別在［1，10］和［1，20］隨機產(chǎn)生。設(shè)機器的容量cap為10。工件尺寸sj分別從均勻分布［1，10］、［2，4］和［4，8］中產(chǎn)生。因此，算例類別共計10×2×3=60 類。具體的參數(shù)和水平，如表1所示。

表1 實驗數(shù)據(jù)的工件參數(shù)Tab.1 Various Parameters of Experimental Data

其中，交貨期的產(chǎn)生方式如下，確定單個工件平均模擬加工時間和平均模擬批數(shù)，由此獲得總模擬加工時間BP。

交貨期參數(shù)dj由以下均勻分布產(chǎn)生：

式中：l和h—下限和上限，分別設(shè)置為0.1和0.7。

4.2 實驗結(jié)果及分析

在本節(jié)中，將IICA 算法的結(jié)果與原始ICA 和文獻［8］提出的MICA 算法進行比較。IICA 算法中設(shè)置國家規(guī)模為1.5n，Nimp的比例為0.15，α1，α2，α3，α4分別為0.25，0.125，0.125，0.5。對每類算例生成10個實例，以平均值進行比較。按照加工時間不同，將工件尺寸分別為［1，10］，［2，4］［4，8］求得的結(jié)果取均值。由于目標(biāo)函數(shù)是最小化UD，定義任一算法A相對于所提IICA算法差距公式Gap（A）%如下。

式中：UD（A）—算法A所求的目標(biāo)函數(shù)UD值。

由表2可看出，IICA 算法總體上優(yōu)于MICA 算法，平均幅度達(dá)到3.2%，IICA算法優(yōu)于ICA 算法的幅度平均達(dá)到7.5%。將表2獲得的ICA、MICA和IICA的結(jié)果按照加工時間不同做比較，P1和P2時間下的分類顯示，如圖4、圖5所示。

圖4 P1類中每個算法的結(jié)果Fig.4 The Result of Each Algorithm in Class P1

圖5 P2類中每個算法的結(jié)果Fig.5 The Result of Each Algorithm in Class P2

工件的總不滿意度隨著工件規(guī)模越大呈現(xiàn)上升趨勢，當(dāng)工件規(guī)模較小時，無論是P1類還是P2類，ICA、MICA和IICA獲得的最終結(jié)果差別不大，但隨著工件規(guī)模的增加差別越來越明顯，ICA的優(yōu)化效果最差，IICA的優(yōu)化效果要優(yōu)于ICA和MICA。

為了進一步比較算法的性能，這里設(shè)計了統(tǒng)計分析實驗對算法進行統(tǒng)計檢驗。首先將實驗輸出結(jié)果數(shù)據(jù)進行正態(tài)性檢驗得出數(shù)據(jù)符合正態(tài)分布，隨后利用方差分析（ANOVA）模型進行檢驗。

模型顯示為：

式中：μ—整體平均值；

τi(i=1，2，3)—3種不同算法的效果；

βj(j=1，2...60)—第j個樣本的實例效果；

εij—隨機誤差。

采用95%的置信度進行檢驗，檢驗結(jié)果，如表3所示?；赑值對三種算法進行比較，可認(rèn)為置信度檢驗是可靠的。為了比較各算法之間的性能排序，選用Least Significant Difference（LSD）進行檢驗結(jié)果，如表4所示。

表3 算法的ANOVA結(jié)果Tab.3 ANOVA Results of Algorithm

根據(jù)LSD測試的結(jié)果，可知三種算法的性能之間存在顯著差異。通過分析可以得出，IICA具有最佳性能。這表明，改進后的殖民地移動策略提高了ICA的性能，同時，嵌入有效地啟發(fā)式規(guī)則，能夠有效地提升搜索解空間的效率。

5 結(jié)論

對加工時間和交貨期模糊的成批調(diào)度問題進行了研究，將確定型環(huán)境下的工件總延遲目標(biāo)轉(zhuǎn)化為模糊制造系統(tǒng)中的不滿意度，構(gòu)建了問題的模糊數(shù)學(xué)模型。針對帝國主義算法容易陷入局部最優(yōu)的問題，改進殖民地的移動策略，結(jié)合批調(diào)度的啟發(fā)式規(guī)則設(shè)計IICA算法對問題進行求解。設(shè)計仿真實驗對IICA的有效性進行分析，IICA算法在各類算例平均優(yōu)于MICA和ICA算法的幅度分別為3.2%和7.5%。這里所研究問題可擴展到考慮工件到達(dá)時間的不確定性以及多機環(huán)境等情況，對于模糊環(huán)境下工件準(zhǔn)時交貨的目標(biāo)也可進一步研究。