帝國競爭算法求解資源約束混合流水車間調(diào)度問題

李俊青，李榮昊，陶昕瑞，曾清清，耿雅典

(聊城大學(xué) 計算機學(xué)院，山東 聊城 252059)

0 引言

混合流水車間調(diào)度問題(Hybrid Flowshop Scheduling Problem，HFSP)是傳統(tǒng)流水車間調(diào)度問題的擴展?；旌狭魉囬g調(diào)度問題的多進程和多階段的特點與其他類型的調(diào)度問題相比更加具有現(xiàn)實意義。在典型的生產(chǎn)制造業(yè)中，實際生產(chǎn)過程中可以會發(fā)生各種各樣的動態(tài)事件，如資源受限、機器故障等。因此，研究資源約束混合流水車間調(diào)度問題(Resource-constrained Hybrid Flowshop Problem，RCHFS)具有一定的現(xiàn)實意義。此外，制造業(yè)的生產(chǎn)活動所產(chǎn)生的能源消耗作為全球變暖的主要來源，應(yīng)該滿足環(huán)境保護和能源消耗的相關(guān)規(guī)定。本文研究了完工時間和能源消耗的資源受限混合流水車間問題，并且這個問題具有重要的實踐意義。

Rubén Ruiz等人已經(jīng)對于傳統(tǒng)的HFSP進行了許多對于變體形式和解決方案的討論[1]。一些研究人員采用了精確算法去解決HFSP問題，如拉格朗日松弛算法[2-4]和分支定界算法[5-7]。然而隨著問題規(guī)模的增加，精確算法的效率已經(jīng)受到了限制，因此，元啟式算法和啟發(fā)式算法得到了更廣泛的應(yīng)用，Behnamian等人[8]和Dugardin等人[9]運用的遺傳算法(Genetic Algorithm，GA)。Elmi和Topaloglu采用模擬退火算法(Simulated Annealing，SA)求解多機器人調(diào)度問題[10，11]。Figelska考慮了兩階段混合流水車間問題的禁忌搜索算法[12]。Marichelvam提出了離散螢火蟲算法求解雙目標HFSP[13]。Naden和Yazdani考慮了帝國主義競爭算法來解決帶有子模塊和準備時間窗的HFSP[14]。此外，混合人工蜂群算法[15]、混合果蠅優(yōu)化算法[16]、混合松鼠搜索算法[17]等也都在HFSP研究領(lǐng)域得到了應(yīng)用。

RCHFS作為HFSP的一種變體形式，幾年來一直受到許多研究者的關(guān)注和研究。Nishi開發(fā)了拉格朗日分解和協(xié)調(diào)方法[18]，Sural等人提出了分支定界算法來解決雙資源約束的調(diào)度問題[19]，Pei等人提出了蝙蝠算法和變鄰域搜索相結(jié)合的方法(Bat Algorithm combined with Variable Neighborhood Search，BA-VNS)[20]。Li等人研究和改進了人工蜂群算法(Artificial Bee Colony Algorithm，ABC)和兩階段編碼機制[21-23]。Cheng等人針對不同的情況提出了多項式算法[24]。Leu和Hwang提出了基于遺傳算法的搜索算法，并據(jù)此進行了靈敏度分析[25]。

近年來，綠色調(diào)度在制造業(yè)中已經(jīng)成為研究的主要方向之一。Gao等人[26]提供了一個完整的關(guān)于帶有能源目標的智能制造生產(chǎn)調(diào)度系統(tǒng)的文獻綜述，提出了基于遺傳規(guī)劃的生產(chǎn)調(diào)度啟發(fā)式自動設(shè)計的統(tǒng)一框架[27]。Dai等人采用了一種genetic-SA的方法[28]并在此問題求解上取得了重大進展。同時，基于分解的多目標進化算法[29]也是被許多學(xué)者研究。Li等人提出了一種基于Pareto的多目標優(yōu)化算法[30]。Lei等人提出了一種新穎的基于教與學(xué)優(yōu)化算法(Teaching-Learning-Based Optimization，TLBO)[31]用來最小化總能耗和總延遲。Ding等人提出了求解雙目標問題的多目標迭代貪婪算法[32]。此外，混合迭代貪心算法[33]、高效多目標算法[34]和改進的Jaya算法[35]也用于多目標問題的求解。許多專家還研究了能量感知模型[36-38]、機器開關(guān)方案[39]和不同類型的機器約束[40]問題等等。

自混合流水車間問題提出以來，早期的研究一般側(cè)重于生產(chǎn)效率的優(yōu)化，隨著生產(chǎn)力的提高，能源需求量越來越多，相應(yīng)的能耗造成的環(huán)境問題也日益嚴重。無論從經(jīng)濟成本還是環(huán)境影響方面來考慮，對制造業(yè)中能耗目標加以優(yōu)化已經(jīng)是大勢所趨。在RCHFS問題中考慮了能耗目標，將完工時間和能耗加權(quán)求和，所以設(shè)計了基于離散帝國主義競爭算法(Discrete Imperialist Competitive Algorithm，DICA)和模擬退火算法(SA)相結(jié)合的算法，對該問題進行求解。

目前的多約束HFSP大多考慮的是機器或者時間的約束[41]，然而在實際的工業(yè)生產(chǎn)中往往需要人力或者其它類型的資源，針對這方面的研究相對較少。由于實際的生產(chǎn)工藝和加工環(huán)境的復(fù)雜性，多約束HFSP更加貼近實際生產(chǎn)調(diào)度，但多樣化的約束、假設(shè)條件等也使得問題求解變得更加復(fù)雜，變量增加、建模難度增大、約束條件增多等導(dǎo)致了可行解很難尋找，全局最優(yōu)解的搜索更加困難。此外，要在解決問題的基礎(chǔ)上考慮算法的性能，使其更加充分的貼近實際工業(yè)生產(chǎn)的需要，加大了對于思考算法處理問題時的難度。

本文主要貢獻如下：(1) 考慮了最小化完工時間和總能耗的RCHFS問題，并提出了相應(yīng)的數(shù)學(xué)規(guī)劃模型。據(jù)我們對研究現(xiàn)狀的分析可知，最小化完工時間和總能耗的RCHFS問題是第一次被提出。(2) 采用了一種新穎的DICA方法來解決帶能耗的RCHFS問題。此外，還設(shè)計了適應(yīng)這一問題的編碼和解碼策略。(3) 將DICA和SA相結(jié)合來提高算法的性能。

本文中首先描述了經(jīng)典帝國主義競爭算法(Imperialist Competitive Algorithm，ICA)和改進算法以及編碼和解碼方法。然后，在隨機生成的一組實例上進行的仿真實驗，并將得到的結(jié)果與其他幾種算法的結(jié)果進行比較分析。最后，對本文的工作進行總結(jié)，并展望了未來可行的研究方向。

1 問題描述

1.1 問題建模

所研究的問題可以描述如下：工件需要經(jīng)過不同階段的機器處理，在整個過程中，至少有一個階段存在多于兩臺的并行機。第一階段加工完成后，第二階段才能繼續(xù)加工。如果第一階段的處理完成，工件可以暫存在無限容量的緩沖空間中，直到機器在第二階段可用為止。工件可以在后續(xù)階段上的任意一臺機器上加工，開始后加工不能中斷。

工廠里有h種資源，包括R1,R2,…,Rh。每種類型的資源數(shù)量都是預(yù)先給出的，每臺機器的加工來自不同類型資源的合作。因此，為了開始加工，必須確保機器和資源同時可用。

在車間之中，至少有一個階段存在兩臺或以上的并行機。其中每臺機器具有兩種狀態(tài)，即處理狀態(tài)和待機狀態(tài)，不同狀態(tài)消耗的能量是不同的。目標是使完工時間和能源消耗最小化。

1.2 變量描述

(1) 下標。i：工件下標,i=1,2,…，n;k：機器下標,k=1,2,…，m;j：加工階段下標,j=1,2,…，g;q：工件加工位置下標,q=1,2,…，n;r：工序數(shù)，r=1,2,…O；res：機床加工需要的資源，res=1,2,…h(huán)。

(2) 參數(shù)。n：工件總數(shù)；m：機器總數(shù)；s：加工階段總數(shù)；h：資源類型數(shù)量；L：一個很大的數(shù)；pi,j：工件i在加工階段j上的加工時間；O：工序總數(shù)；pek：機器k加工時單位能耗；sek：機器k空閑時單位能耗。

(3) 決策變量。Bk,q：加工機床k在加工位置q的開工時間；Ek,q：加工機床k在加工位置q的完工時間；bi,j：工件開工時間；ei,j：工件完工時間；rbr,res：資源開工時間；rer,res：資源完工時間；Yk,i,j,q：加工階段，加工機床上工件和加工位置的對應(yīng)關(guān)系；Ri,j,r,res：資源在某個位置對應(yīng)的工序編號；RMr,k,res：資源在某個位置加工的機床k；TEC：總能耗。

1.3 數(shù)學(xué)模型

根據(jù)上述變量和下標，所建立的數(shù)學(xué)模型如下。

最小化目標

w*Cmax+(1-w)*TEC，

(1)

約束條件

Bk,q+1-Ek,q+L*(1-Yk,i',j,q)≥0,

(2)

ei,j=bi,j+pi,k,

(3)

(4)

(5)

Ek,q≤Bk,q+1,

(6)

Bk,q≤bi,j+(1-Yk,i,j,q)*L,

(7)

Bk,q+(1-Yk,i,j,q)*L≥bi,j,

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

rbr,res≥rer-1,res,

(16)

(17)

(18)

TEC=E1+E2,

(19)

(20)

(21)

約束(1)表示目標為最小化完工時間。約束(2)確保同一階段分配在同一機器上的排位靠后的工件必須等靠前的工件加工完后才可進行。約束(3)表示同一階段上開始時間和完工時間的關(guān)系。約束(4)表示工件完成上一階段的加工后才能進行下一個階段加工。約束(5)表示一個階段中工件一旦開始加工就不能中斷。約束(6)表示每臺機器開工時間和完工時間對應(yīng)關(guān)系。約束(7)和約束(8)表示機器開始時間和工序時間對應(yīng)關(guān)系。約束(9)表示同一階段工件只能在一臺機器上加工。約束(10)確保每臺機床同一時刻只能加工一個工件。約束(11)和約束(12)保證同一階段調(diào)度排列中優(yōu)先級高的先加工。約束(13)-約束(16)表示同一時刻加工需要資源數(shù)量不超過單位總量。約束(17)表示資源的使用時間與對工序的時間關(guān)系。約束(18)表示機床與資源之間的對應(yīng)關(guān)系。約束(19-21)表示的機器的加工能耗，其中E1表示機器加工階段的能耗，E2表示機器空閑階段的能耗。

2 算法描述

2.1 問題編碼

針對考慮能耗的資源約束混合流水車間調(diào)度問題(ERHFS)，使用基于雙向量(TVB)解的表示和基于機器甘特圖(MGB)解的表示的兩階段編碼機制。在早期的進化階段，基于雙向量的表示可以識別具有廣泛搜索能力的并且有前途的搜索空間。在后期的進化階段，使用基于機器甘特圖的解的表示來編碼每臺機器的詳細調(diào)度，并通過足夠大的搜索空間來進行搜索。 兩種編碼策略的細節(jié)描述如下：

(1) TVB解的表示。在編碼表示中考慮了機器分配和操作排序，第一個向量為機器分配向量，長度為n×g，其中每個元素標識了每個工件所分配的機器號。如圖1所示，機器分配向量為{1，1，1，1，1，2，3，2，3，2}，向量第一個元素為1，表示加工的第一個階段中，1號工件被分配給了1號機器。

圖1 TVB解的表示舉例

調(diào)度向量為{1，2，3，4，5}，定義了第一階段的加工順序。在第一階段加工完成后，分配的機器和資源都可用時，立即將每個工件轉(zhuǎn)移到下一個階段進行加工。此外，由于機器和資源的占用，加工順序可能在后期發(fā)生變化。

(2) MGB解的表示。第二種向量MGB解的表示是根據(jù)當前的機器甘特圖設(shè)計的，基于MGB解的表示中每個階段的每臺機器都有一個向量，每個向量表示了當前機器上的調(diào)度序列。對于圖2中所舉的示例，MGB解的表示為{{1，2，3，4，5}，{{1，3，5}，{2，4}}}，其中第一個向量為第一個階段中1號機器的編碼，第二個向量為第二階段中2號機器和3號機器上的編碼。TVB解的表示和MGB解的表示主要區(qū)別在于，MGB解的編碼可以識別每個階段中每臺機器上的工件排序，而TVB解的編碼只識別第一階段中的工件排序。

圖2 機器甘特圖

2.2 問題解碼

在解碼過程中，我們使用TVB和MGB解決方案表示來確定每個操作的開始時間以及每臺機器的合適資源。開始操作需要同時滿足以下三個條件：工件到達指定機器；指定機器可用；指定機器所需的資源可用。

所有工件在當前加工階段完工后，需要根據(jù)當前資源是否可用做出如下選擇：如果當前資源可用，則安排到下一階段加工；否則推遲該工件，直到資源可用再開始加工，機器間的運輸時間忽略不計。

計算工件的開始加工時間時，需要考慮：(1) 上一階段ei,j-1的完成時間；(2) 機器可用時間Ik；(3)k機器所需資源的最大可用時間。因此，bi,j可以計算如

bi,j=max(bi,j-1+pi,j-1,Ik,ARk)，

(22)

(23)

其中Ar是資源r∈Rk的可用時間，ARk是機器k所需的所有資源的最大可用時間。如果Oi,j是工件i的第一個操作，則開始時間bi,j可以計算如

bi,j=max(IkARk)。

(24)

Oi,j完成后，Rk資源將被消耗并立即釋放以用于其他操作。因此，Rk和Ik的可用時間將更新如

Ik=ARk=bi,j+pi,j。

(25)

在所有的工件都安排好之后，總完工時間計算如

(26)

2.3 解集初始化

初始化過程分為四步：(1) 將所有解存放在數(shù)組中作為初始的國家，并計算其標準化國家勢力值。(2) 選出Nimp個國家勢力值較大的國家作為帝國，剩下的Ncol個國家作為殖民地。(3) 對選出來的Nimp個帝國，計算其標準化帝國勢力值。(4) 根據(jù)標準化帝國勢力計算帝國所擁有的殖民地數(shù)量，并將相應(yīng)數(shù)量的殖民地分配給相應(yīng)的帝國。初始帝國數(shù)量為解集大小的20%。

采用貪心的策略，將fitness較小的幾個解作為帝國，其余的作為殖民地，這樣可以在一定程度上加快算法的收斂速度。整個初始化的過程就是將所有解劃分為殖民地或者帝國，并將殖民地分配給相應(yīng)的帝國。

2.4 改進帝國同化行為

為了使ICA算法適用于求解離散的優(yōu)化問題，提出了離散帝國同化過程。在同化過程中，隨機選擇以下兩種交叉方式中的一種來實現(xiàn)解的變換。

第一種交叉方式，對每個帝國都進行交叉處理。其中一個父代為帝國，另一個父代為該帝國的殖民地，讓帝國與其擁有的每個殖民地都進行交叉，計算獲得子代的目標值。這里的交叉策略具體步驟如。

步驟1如圖3所示，隨機選擇一個帝國和他的殖民地(父代)中幾個工件編號的起止位置(兩父代個體被選位置相同)。

圖3 隨機選取帝國和他的殖民地

步驟2如圖4，交換帝國和殖民地的位置。

圖4 交換過程

步驟3看生成的子代工件編號是否重復(fù)，如果重復(fù)就把帝國和殖民地中選取的兩組工件編號建立相應(yīng)的映射關(guān)系，如圖5所示，即{2，5，0}，{8，3}，{1，4}。第二步中子代1交換完成后出現(xiàn)了兩個工件1，可以通過映射關(guān)系把1轉(zhuǎn)換為工件4并以此類推，直到最終形成的子代里工件編號只出現(xiàn)一次。

圖5 沖突檢測

最終結(jié)果如圖6所示。

圖6 交叉完的帝國和殖民地

第二種交叉方式，不區(qū)分帝國或殖民地，隨機選取兩個國家作為父代進行交叉，同樣采用上述的交叉操作。另外，在帝國對內(nèi)同化的過程中，有的殖民地不滿帝國的統(tǒng)治想要進行革命，革命成功則會成為帝國，革命失敗則繼續(xù)是殖民地，革命的過程類似于變異的過程，這里提出了一種變異策略。

(1) 對于機器分配向量隨機選擇幾個位置，更換工件所對應(yīng)的機器。

(2) 對于調(diào)度向量，隨機選擇交換算子和插入算子其中的一個。對于交換操作，在調(diào)度向量中隨機選擇兩個工件，然后交換兩個工件以生成不同的子代。對于插入算子，在調(diào)度向量中隨機選擇兩個工件，刪除其中一個工件并將其插入到另一個選定工件的前一個位置。具體過程如圖7所示。

圖7 變異操作

2.5 改進帝國競爭行為

帝國想要發(fā)展除了對內(nèi)的同化統(tǒng)治，還需要對外擴張，帝國競爭是算法的全局搜索過程。所有帝國都希望能夠占有其他帝國的殖民地并控制它們，這種帝國之間的競爭行為會逐漸導(dǎo)致較弱的帝國勢力下降而強大的帝國勢力增加。通過挑選較弱帝國的殖民地，將它分配給其他較強的帝國來模擬帝國競爭的過程。如何挑選較弱的帝國，提出了兩種策略。

算法1 帝國競爭策略1 輸入: 不可行的解 輸出: 可行的解1.For 每一個帝國 jdo 2.按殖民地數(shù)量排序3.End4.殖民地數(shù)量少的作為弱小帝國,反之則為強大帝國5.For 每一個帝國的殖民地的 ido6.按照弱小帝國的順序破壞殖民地7.從弱小帝國中隨機選擇殖民地歸入強大的帝國中8.End

算法2 帝國競爭策略2 輸入: 不可行的解 輸出: 可行的解1.For 每一個帝國 jdo 2.For 每個帝國的每個殖民地 do3.按目標值總和排序4.End5.根據(jù)帝國的總體適應(yīng)性將帝國從小到大進行排序6.End7.目標值大的作為弱小帝國,反之則為強大帝國8.For 每一個帝國的殖民地ido9.為了最弱小的帝國破壞殖民地10.從弱小帝國中隨機選擇殖民地歸入強大的帝國中11.End

首先，殖民地較少的帝國可以作為弱小帝國。按照帝國殖民地的數(shù)量排序，找到一些弱小帝國打亂他們的殖民地順序，隨機選擇一個殖民地歸屬到強大的帝國中。其次，還可以將帝國殖民地的目標值從小到大排序，選擇較大目標值的國家作為弱小帝國，然后打亂弱小帝國的殖民地順序，并隨機選擇一個殖民地歸屬到強大的帝國中。

2.6 帝國滅亡

如果一個帝國失去了所有的殖民地，就會滅亡。一段時間以后，所有的殖民地都被納入最后的帝國之中。通常情況下，經(jīng)典ICA是將滅亡的帝國直接刪除，DICA中把滅亡的帝國作為殖民地劃分給強大的帝國，這樣能夠增加解的多樣性。具體步驟如下。

步驟1 對于每一個帝國，判斷其殖民地數(shù)量。若殖民地數(shù)量小于1，則執(zhí)行步驟2；否則，執(zhí)行帝國競爭過程。

步驟2 將該帝國作為殖民地劃分給其他帝國。

步驟2.1計算帝國總勢力值。

步驟2.2該帝國作為殖民地劃分給最強大的帝國。

步驟2.3將該帝國從帝國里面刪除并添加到殖民地中。

步驟3 檢測是否還有其它帝國。

步驟3.1若還有其他帝國，回到步驟1。

步驟3.2若沒有其它帝國，記錄當前最優(yōu)解。

2.7 全局搜索過程

在經(jīng)典的ICA算法中，帝國競爭階段完成以后，帝國如果失去了所有的殖民地就會滅亡，相應(yīng)的會在所有的解中將這個帝國刪除，保留其它帝國。這樣雖然提高了算法的收斂速度和局部搜索能力，但是解的多樣性相對減少，算法容易陷入局部最優(yōu)。因此將DICA算法與模擬退火算法(Simulated Annealing，SA)相結(jié)合，進一步提升算法的全局搜索能力。

算法迭代時的溫度根據(jù)公式(27)定義

Tk=αTk-1=αkT0，

(27)

其中0<α<1是溫度的降低速率。很顯然，α越小，溫度下降的越慢。SA的算法流程如算法3所示。

算法3 模擬退火算法 輸入: 局部最優(yōu)解 輸出: 全局最優(yōu)解1.初始化溫度2.創(chuàng)建一個隨機解決方案x和評估函數(shù)f(x)3.在 xbest 保存x的最優(yōu)解4.While 標準不滿足時停止5.創(chuàng)建鄰域解決方案 xnew和評估函數(shù)f(xnew)6.接受 xnew的概率為P(x,xnew,T)7.If x比xbest更優(yōu),令 xbest存儲x8.降低溫度9.End while

算法4 鄰域創(chuàng)建方案 輸入: 帝國主義 輸出: 改進的帝國主義1.概率是1/2,執(zhí)行步驟2;否則執(zhí)行步驟3。2.在vector(機器分配向量)中選擇一個隨機元素,并將其替換為區(qū)間[0,1]中的一個隨機數(shù)。然后執(zhí)行步驟6。3.概率是1/2,執(zhí)行步驟4;否則執(zhí)行步驟5。4.在(調(diào)度向量)中選擇兩個不同的元素并交換它們的位置。執(zhí)行步驟6。5.選擇兩個不同的元素,并顛倒它們之間的順序(包括它們自己)。6.End

通常情況下，SA通過在鄰域結(jié)構(gòu)中創(chuàng)建新的解，迭代尋找更優(yōu)的解。不同的編碼方式有不同的鄰域結(jié)構(gòu)。因此，根據(jù)RCHFS的問題編碼定義了一個隨機過程來創(chuàng)建鄰域，創(chuàng)建鄰域的過程如算法4所示：

2.8 算法框架

針對ERCHFS問題的帝國競爭算法的具體框架如下。

步驟1系統(tǒng)設(shè)置階段。

步驟1.1系統(tǒng)參數(shù)設(shè)置。

步驟1.2初始化解集。

步驟2帝國初始化階段。

步驟2.1計算解集中解的目標值，將當前解集Npop中最好的Nimp個解作為帝國，剩下的Ncol個解作為殖民地。

步驟2.2計算帝國勢力大小，根據(jù)帝國勢力大小計算其擁有的殖民地數(shù)量。

步驟2.3將對應(yīng)數(shù)量的殖民地隨機分配給帝國。

步驟3如果滿足停止條件，則保存至當前最好解；否則執(zhí)行步驟4到6。

步驟4帝國同化階段。

步驟4.1執(zhí)行2.4章節(jié)中的交叉和變異策略。

步驟4.2重新評價當前的帝國和殖民地。

步驟5帝國競爭階段。

步驟5.1計算帝國總勢力，根據(jù)帝國總勢力計算每個帝國占有殖民地的概率。

步驟5.2從較弱帝國隨機選擇一個殖民地按一定概率加入其他帝國。

步驟6帝國滅亡階段。

步驟6.1若帝國還有殖民地，重復(fù)執(zhí)行步驟4到6。

步驟6.2若帝國失去所有殖民地，則將帝國作為殖民地加入其他帝國。

步驟7檢測是否只剩一個帝國。

步驟7.1若還有其他帝國，重復(fù)步驟4到7。

步驟7.2若只剩一個帝國，記錄至當前最優(yōu)解。

步驟8全局搜索過程。

步驟8.1從2.7節(jié)中的鄰域結(jié)構(gòu)隨機生成一個新解。

步驟8.2若新生成的解比當前最優(yōu)解好，則將新解記錄至最優(yōu)解。

步驟8.3若新解比當前最優(yōu)解差，則按概率P(x,xnew,T)保留新解。

步驟9回到步驟8。

2.9 算法復(fù)雜度分析

根據(jù)算法的全局分析可知，在種群規(guī)模為n，最大迭代m次時，算法的時間復(fù)雜度均為O(nlogn+n*m)。

3 實驗分析

3.1 實驗設(shè)置

以Visual Studio 2015為開發(fā)環(huán)境，使用Intel i5 2.40 GHz CPU、16 G內(nèi)存的電腦上進行實驗。為了解決RCHFS問題并驗證DICA的有效性，在經(jīng)典的混合流水車間問題算例的基礎(chǔ)上生成了20個ERCHFS問題的大規(guī)模測試用例。算例中工件的數(shù)量為(50、100、150、200)，階段的數(shù)量為(2、4、6、8、10)。另外，在RCHFS算例的基礎(chǔ)上加入了每臺機器加工和空閑階段的單位能耗。例如，算例1規(guī)定了車間中有50個工件、9臺加工機器、工件需要2個階段的加工、總共有3種資源、每種資源總量都是4個單位，另外還規(guī)定了9臺加工機器各自加工和空閑階段的單位能耗。實驗所得到的結(jié)果都是針對每個算例獨立運行30次取得的平均值，并采用相對百分比增長(RPI)指標來作為算法性能分析比較的標準。

3.2 實驗參數(shù)

實驗中，DICA主要參數(shù)有三個，分別是(1) 初始解集大小(Ps)；(2) 交叉概率(Pc),它表示了算法中每個個體交叉的概率；(3) 變異概率(Pm),它規(guī)定了算法中個體變異的概率。

采用實驗設(shè)計DOE Taguchi方法構(gòu)造了一套正交陣列L16對參數(shù)進行組合，參數(shù)組合如表1所示。圖8給出了因子水平和交點。經(jīng)過計算，DICA算法表現(xiàn)最優(yōu)的參數(shù)組合為50，0.7，0.05。

圖8 三個關(guān)鍵參數(shù)的因子水平趨勢

表1 參數(shù)值設(shè)置

DICA表現(xiàn)最優(yōu)的組合中三個參數(shù)的取值分別為50、0.7、0.05。其它算法所用的參數(shù)設(shè)置均得自相應(yīng)的參考文獻，所有算法均使用第3章中的編碼解碼策略。

3.3 小規(guī)模算例驗證

為了驗證所提出的優(yōu)化模型的有效性，通過精確求解器IBM ILOG CPLEX 12.7對10個小規(guī)模算例進行了計算。小規(guī)模算例是根據(jù)3.1節(jié)所用的算例隨機生成的。在精確求解器中，最大線程數(shù)為3，每次運行的CPU時間限制設(shè)置為3 h。

表2顯示了DICA算法和CPLEX求解器的比較結(jié)果。表格第一列表示算例編號，第二列表示問題規(guī)模(其中4-4-2表示實例包括4個工件、4臺機器和2個階段)。對每個實例運行30次DICA算法并取平均值。最后兩列顯示了這兩個方法的RPI值?？梢钥吹剑?1) 提出的DICA算法獲得了較高質(zhì)量的解；(2) 對于較大規(guī)模的計算實例，CPLEX的求解性能的表現(xiàn)不如DICA。(“-”表示CPLEX解算器在3 h內(nèi)找不到可行解，粗體表示比較算法中的最優(yōu)值)，性能指標為RPI。所得結(jié)果如下。

表2 DICA與CPLEX求解器比較

3.4 與現(xiàn)有算法進行比較

最后，為了評估提出的DICA算法的效率，將其與離散人工蜂群算法(Discrete Artificial Bee Colony Algorithm，DABC)[42]和帶遺傳算法的混合帝國主義競爭算法(Hybrid Imperialist Competitive Algorithm with Genetic Algorithm，ICA-G)[43]進行了比較。之所以選擇這三種方法是因為(1) DABC算法在資源受限的混合流水車間問題里已經(jīng)得到了有效證明；(2) ICA-G雖然沒有在RCHFS問題里得以應(yīng)用，但是在混合流水車間問題里也已經(jīng)有了一定的研究，只需稍作修改就可以用于求解提出的ERCHFS問題。上述對比算法參數(shù)取自于各自文獻。

為了讓完工時間和總能耗在相同大小的范圍內(nèi)，對兩個目標進行了歸一化處理，對完工時間和總能耗分別使用公式(28)和(29)計算。加權(quán)和的最終目標函數(shù)如式(30)所示。

Fvalue=F/Fmax，

(28)

Evalue=E/Emax，

(29)

min(f)=w*Fvalue+(1-w)*Evalue，

(30)

其中Fmax和Emax分別是當前種群中最大的完工時間和最大的總能耗，w是反映兩者相對重要性的權(quán)重，取值為0≤w≤1。通常情況下，把w的值設(shè)置為0.8。

每個算法在同一臺計算機上對每個算例分別運行30次，把得到的數(shù)據(jù)取平均值。比較實驗結(jié)果如表3。第一列寫明了算例名稱，第二列列出了每個算例求解得到的最優(yōu)值，后面三列提供了每個算法求解得到的最優(yōu)值。為了直觀地比較三種算法得到的解的質(zhì)量，計算了相對百分比增幅，并在最后三列給出了相應(yīng)的結(jié)果。表3中列出的結(jié)果可以總結(jié)如下：(1) DICA算法在給定的示例中獲得了14、13和12個最優(yōu)解，這遠遠優(yōu)于其他對比算法的結(jié)果；(2) 如表中最后一行所示，DICA平均目標值和平均百分比偏差遠遠低于其他算法。實驗結(jié)果表明，與其他最近提出的算法相比，所提出的DICA算法能夠更有效的解決RCHFS問題的方法。

表3 DICA算法與其他算法最好解比較

4 總結(jié)與展望

圖9 算法最優(yōu)解的比較

本文提出了DICA&SA方法來解決ERCHFS問題。主要內(nèi)容如下：首先針對經(jīng)典的HFS問題，考慮了資源受限約束和能耗目標，提煉出了ERCHFS問題，建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型。其次是算法求解，實現(xiàn)了離散的帝國競爭算法對問題進行求解，結(jié)合了SA增強了算法的全局搜索能力。最后是算法的實驗分析，根據(jù)經(jīng)典的HFS問題Benchmark算例，生成了與問題相符合的RCHFS問題算例。通過算法的實驗比較與分析，驗證了所提出的DICA&SA算法的有效性。

4.1 論文主要工作和創(chuàng)新點

隨著經(jīng)濟全球化以及現(xiàn)代工業(yè)生產(chǎn)技術(shù)的發(fā)展，迫使制造企業(yè)不得不尋找高質(zhì)量的調(diào)度方案來減少生產(chǎn)成本。另外，國家對環(huán)境以及綠色制造的重視，也使得降低制造能耗成為智能制造中的一個關(guān)鍵問題。因此，針對RCHFS調(diào)度問題，建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型。設(shè)計了離散帝國競爭算法求解該問題，通過實際工業(yè)生產(chǎn)仿真實驗，驗證了DICA求解RCHFS問題的性能。主要創(chuàng)新點包括：

(1) 根據(jù)文獻[41]Li等人所提出的HFS考慮時間約束上對HFS問題進行擴展，提出了考慮帶資源約束和能源消耗的HFS問題。擴展了經(jīng)典HFS算例，驗證了算法策略以及求解的有效性。基于實際生產(chǎn)車間生產(chǎn)的數(shù)據(jù)，對算法求解性能進行了驗證。

(2) 根據(jù)文獻[44]Qin等人在研究考慮一種約束的情形時只以最小化最大完工時間為優(yōu) 化目標。針對RCHFS問題，考慮了圍繞帶完工時間和總能耗為性能目標的ERCHFS問題，構(gòu)建了數(shù)學(xué)規(guī)劃模型，使ERCHSF問題結(jié)果更加貼近于實際生產(chǎn)需要。

(3) 根據(jù)文獻[45] Li等人在考慮資源約束類柔性作業(yè)車間調(diào)度問題(Flexible Job Shop Scheduling Problem，F(xiàn)JSP)時采用人工蜂群算法，相比針對RCHFS問題的求解，采用帝國競爭算法求解，設(shè)計了算法的離散化策略，改進了算法流程，提出了與編碼相適應(yīng)的局部搜索策略，結(jié)合了SA算法，提高了算法的搜索能力。同時，相比較于資源約束類FJSP，RCHFS問題增加了機床選擇的靈活性, 可以顯著優(yōu)化系統(tǒng)目標。

4.2 后續(xù)研究工作展望

目前針對優(yōu)化調(diào)度問題的研究已經(jīng)取得了較多的成果，但隨著工業(yè)技術(shù)以及制造產(chǎn)業(yè)的發(fā)展，理論研究與實際的工業(yè)生產(chǎn)還有一定的差距。針對資源受限的混合流水車間建立了數(shù)學(xué)模型，并且設(shè)計了一種有效的解決算法，取得了較好的結(jié)果。但目前研究還處在初級階段，未來的工作還需要更深入的研究，可以從以下幾個方面入手：一方面，在問題層面本文只考慮了混合流水車間中的資源約束，但實際的生產(chǎn)車間生產(chǎn)情況必定更為復(fù)雜，肯定還會存在其它各類工藝約束。如何在HFS問題中融合新的工藝約束，考慮多約束的混合流水車間問題，是未來研究的方向之一；此外，分布式生產(chǎn)是近年來生產(chǎn)的一種新型模式，圍繞HFS問題的分布式生產(chǎn)調(diào)度及其求解方法策略等也亟待更多關(guān)注。另一方面，在算法層面混合算法在求解方面表現(xiàn)出了較為優(yōu)越的性能，研究算法的混合策略、參數(shù)調(diào)整、平衡算法的局部和全局搜索能力等理論成果，還需要進一步的深入研究；另一方面，深度學(xué)習(xí)算法和大數(shù)據(jù)分析技術(shù)已經(jīng)成為研究的熱門方向，如何將帝國競爭算法與深度學(xué)習(xí)算法相結(jié)合，也將是我們未來研究的方向之一。