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

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

1 引言

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

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

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

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

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

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

2.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

2.3 優(yōu)化模型

問(wèn)題所涉及參量說(shuō)明如下：

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

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

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

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

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

3 求解算法設(shè)計(jì)

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

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

3.1 帝國(guó)集團(tuán)編碼與初始化

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

3.2 國(guó)家成本函數(shù)計(jì)算

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

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

算法BFEDD（Best Fit Earliest Due Date）：

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

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

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

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

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

3.3 帝國(guó)同化殖民地策略改進(jìn)

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

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

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

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

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

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

3.4 改進(jìn)的帝國(guó)主義競(jìng)爭(zhēng)算法

改進(jìn)的帝國(guó)主義競(jìng)爭(zhēng)算法（IICA）步驟如下：

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 參數(shù)選取

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

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

在本節(jié)中，將IICA 算法的結(jié)果與原始ICA 和文獻(xiàn)［8］提出的MICA 算法進(jìn)行比較。IICA 算法中設(shè)置國(guó)家規(guī)模為1.5n，Nimp的比例為0.15，α1，α2，α3，α4分別為0.25，0.125，0.125，0.5。對(duì)每類算例生成10個(gè)實(shí)例，以平均值進(jìn)行比較。按照加工時(shí)間不同，將工件尺寸分別為［1，10］，［2，4］［4，8］求得的結(jié)果取均值。由于目標(biāo)函數(shù)是最小化UD，定義任一算法A相對(duì)于所提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é)果按照加工時(shí)間不同做比較，P1和P2時(shí)間下的分類顯示，如圖4、圖5所示。

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

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

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

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

模型顯示為：

式中：μ—整體平均值；

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

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

εij—隨機(jī)誤差。

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

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

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

5 結(jié)論

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