改進區塊遺傳算法解決分布式車間調度問題

裴小兵，孫志衛

（天津理工大學 管理學院，天津 300384）

隨著生產全球化和制造規模化，大型制造企業為降低成本、提高生產柔性與生產效率以快速滿足全球市場需求，生產方式正由集中性單車間生產向分布式車間生產轉變。但是相關文獻研究還主要集中在單個車間生產調度[1]。近年來，分布式車間調度問題(distributed job-shop scheduling problem，DJSP)在車間調度研究領域逐漸受到關注，如對關鍵路徑的二車間綜合調度問題[2]、分布式流程車間問題[3]、多工序同時結束的多車間逆序綜合調度[4]和分布式工作車間問題[5-6]等。

經典的單車間調度問題[7](job-shop scheduling problem, JSP)中所有的工件都在同一車間內加工完成的，DJSP是將工件分配到更多的車間共同加工完成。DJSP是對JSP的擴展，結合了工件在分布式車間的分配和單個車間內調度兩種問題，并且允許任何一個車間擁有加工完成任何一個工件的能力。

由于分布式車間調度需要考慮分配和排序兩個階段，因而DJSP更加復雜[8]：第一階段將待加工的零件分配到f家車間中；第二階段對已經分配到同一車間的工件進行排序(即單個車間調度問題)。第一階段的工件分配很大程度上決定了多車間之間的工作量協同程度，對算法的結果具有至關重要的影響。為了更好地解決DJSP，Wagner[9]提出了DJSP模型，經過不斷的改進能夠準確地描述出分布式工作車間調度問題的特征，該模型的建立對求解DJSP具有重要意義。在該數學模型被提出之前，研究者一般使用標準遺傳算法來解決分布式車間調度問題[10]，之后的研究也是在標準遺傳算法的基礎上進行的局部改進，以解決中小規模的分布式車間調度問題[11]。該數學模型的提出促進了DJSP的研究進度，擴大了問題的可研究規模。Naderi等[12]運用工件-車間分配原則將所有工件分配到每個車間后，再用貪婪式啟發算法對每個車間內的工件進行排序，有效地解決了分布式車間調度問題；Chaouch等[13]在分配工件時結合運用了機器加工工件的工作量均衡原則和甘特圖，再用改進的蟻群優化算法對每個車間的工件進行排序；Naderi等[14]在分配和排序的基礎上又進行了優化，對當前解中不同車間中相同位置的工件進行隨機挑選和互換形成新的解。楊敬松等[15]將遺傳和模擬退火算法結合，相互補充彌補各自搜索能力的弱點形成混合遺傳算法，用于尋找分布式車間調度問題的最短工藝路徑。

遺傳算法(genetic algorithm，GA)通過各種遺傳算子(選擇，交叉和突變)搜索解空間中的最優解，得出較優的解決方案[16]。GA已用于解決生產調度、設施布局、資源分配等生產制造中的問題，而GA沒有機械學習能力，當迭代到一定代數后評價數值陷入局部最優，產生大量的無用計算降低了求解的精度和效率。為了跳出GA的局部最優，Chang等[17]提出了區塊，并將區塊與進化算法結合應用于解決組合優化問題，取得了不錯的效果。近年來，通過挖掘區塊保留優勢解序列信息中的高頻率基因鏈與啟發式算法結合，優化原算法的搜索路徑，減少無效迭代[18]。區塊與貓群算法結合，統計貓群算法中的跟蹤模式更新貓的速度和位置，從而更新優秀解序列產生子群體，增強了貓群算法的魯棒性和全局搜索能力[19]。張敏等[20]運用區塊的關聯規則組合成大量的人造解注入到GA中，提高了解的多樣性，并通過單點突變機制和兩種不同的母體重組方式，保證算法的競爭優勢。裴小兵等[21]提出一種將遺傳算法與蟻群算法相結合的改進區塊遺傳算法，通過蟻群算法中的信息素濃度和區塊兩種方式分別統計搜索路徑和搜索關聯度，提煉精英染色體中的有效信息，比人造解與遺傳算法結合的混合算法等更具有競爭性。區塊能較大程度地平衡分布式車間之間和機器之間的工作量，使分配到同一車間的工件在每個機器上的加工時間相近，發揮加工車間之間的系統效應。在構建人工染色體的過程中，通過以工件為單位或以區塊為單位插入到人工染色體的空白位置，提高了染色體的質量，加快了解的收斂速度[16]。

目前關于分布式車間調度問題的文獻相對較少，現有研究將分配和排序兩階段分別考慮，在分配階段僅考慮每個車間每臺機器的工作量均衡，未涉及下一階段的工件排序，其結果可能會增加分布式車間的最大完工時間。同時大部分針對分布式車間調度問題的優化算法沒有清晰地說明如何通過變異、重組等操作使當前解集不斷進化，部分文獻僅對分配到不同車間的n個工件中的兩個或少數幾個工件進行連續調換來優化當前解，本文嘗試同時調整解序列中車間的分配和工件的排序來增加解的多樣性。本文基于區塊構建高質量人工染色體改進傳統遺傳算法，應用區塊保留并傳遞精英染色體中的高頻率基因鏈，協調分布式車間調度問題中的分配和排序兩階段；改進區塊遺傳算法中的基因重組和人工染色體的構建，使之適應于分布式車間調度問題。本研究以改進后適應于分布式車間調度問題的遺傳算法為構架，引入基于區塊的人工染色體跳出遺傳算法的局部最優。

1 數學模型的闡述

為更好地解決調度問題，Wagner[9]提出了整數規劃模型，將調度問題模型化，明確地描述了調度問題的特征。在Naderi等[12]首次嘗試構建分布式車間調度問題數學模型之前，沒有直接研究分布式車間調度問題的論文，用混合整數線性規劃模型構建分布式車間調度問題為該問題的解決提供了基礎。

分布式工作車間調度問題是將n件工件分配到f間車間中，每個車間以一定的順序共同加工完成這批零件，確定這批工件分配和排序的方案。每個車間擁有m臺機器，且具有獨立加工完成每個工件的能力，與車間調度問題中的條件相同。假設分布在不同區域的f個車間的生產能力是相同的，具有相同的機器和車間布局；所需加工的工件可以在任意車間內加工完成，且加工所需的時間是相同的；不考慮工資水平、運輸距離等因素。在工件加工過程中，已經分配到加工車間的工件禁止轉移到其他車間加工，因為工件在車間之間的交叉加工將增加成本和技術難度。DJSP的約束條件為：1）每個工件只能分配到一個車間內，且每個工件都由特定的車間加工；2）每臺機器只能同時加工一個零件，每個零件只能同時由一臺機器加工；3）分配到同一車間內的工件都在該車間內順序加工；4）n件工件的最大完工時間就是f個車間中完工時間最長的車間的最大完工時間。則DJSP整數線性規劃模型為：

模型中用到的參數為：n表示工件數, j, k={1,2,…,n}；m表示車間內機器數, i，u={1,2,…,m}；f表示車間數, r={1,2,…, f}；pj,i表示工件j在機器i上的加工時間；aj,i,u：如果工作j在機器u上加工完之后立即在機器i上進行加工，則 aj,i,u=1，否則aj,i,u=0；M為一個較大的正數。

決策變量為： Xk,j,u取0，1值，如果機器u在加工完工件k之后加工工件j，則 Xk,j,u=1，否則Xk,j,u=0。 Yj,r取0，1值，如果工件j在車間r加工，則 Yj,r= 1，否則 Yj,r= 0。Cj,i：工件j在機器i上累計加工時間的連續變量。

整體線性規劃模型為：

式(1)是目標函數，尋找最小化的最大完工時間：

Subject to:

式(2)表示將每個工件都安排到唯一的車間內進行加工：

式(3)表示工件的完成時間大于該工件的加工時間：

式(4)表示在同一時間內，一個工件最多能在一臺機器上加工。

式(5)和(6)表示在同一工廠內，一臺機器最多能同時加工一個工件；當且僅當 Xk,j,i=1 時，式(5)和(6)才能夠同時成立，換而言之，同一工廠的機器i加工完成工件k之后才能加工工件j。

在實際的分布式車間調度問題中，安排到每個車間的工件數n應該遠遠大于機器臺數m，這樣才能使得機器的生產能力得到有效的應用，縮短平均加工時間。

2 改進區塊遺傳算法

為適應分布式車間調度問題的特征，對傳統遺傳算法進行了改進，將基因交叉過程中重疊的工件放入重組工件基因池中，再重新插入到解序列中進行重組。在遺傳算法中注入基于區塊的高質量的人工染色體增加解的多樣性；從挑選的精英染色體中統計出工件-車間分配矩陣和工件-機器位置矩陣，然后根據概率矩陣挖掘區塊，運用兩種組合機制構建人工染色體，協調工作車間和車間內機器的工作量，優化搜索路徑。算法步驟如下：

1)生成初始解。為保證初始解的質量和多樣性，本文運用NEH和隨機性兩種方式，按照最早完工的原則初始化種群。

2)計算適應度并挑選精英染色體。計算每個染色體的適應值，并使適應度按從小到大的順序進行排序，挑選出前30%的染色體作為精英染色體。

3)更新概率矩陣。分別建立工件-車間分配矩陣和工件-機器排序矩陣，并隨著迭代過程不斷地更新概率矩陣中的信息。

4)組合區塊。根據概率矩陣中的信息，組合區塊。

5)構建人工染色體。根據區塊庫和概率矩陣中的信息，運用輪盤賭的方式構建人工染色體。

6)對分布式車間調度問題的解序列進行重組。將父代的染色體以某一車間中工件加工的解序列片段為單位進行重組。

7)篩選優精英染色體。將從重組后的染色體與原父代的染色體進行融合，篩選出新的精英染色體作為下一次迭代的父代。

MBGA算法流程圖(見圖1)中，ΔR 為概率模型迭代計數器，Rthe為概率模型迭代的門檻值，ΔA和 Athe分別為構成人工染色體的計數器和門檻值。

圖 1 MBGA流程Fig. 1 Flow chart of MBGA

2.1 生成初始解

傳統GA隨機生成初始解，生成的個體適應度較低，影響解的收斂速度和最終解的質量。本文混合應用NEH(Nawaz-Enscore-Ham)算法和完全隨機兩種方式構造初始解，既保證解的質量，又保持解的多樣性。MBGA運用其中前n/2件工件用NEH算法排序，剩余的工件隨機插入到f家車間的解序列片段中。分別計算n件工件中的每一個工件j在m臺機器上的總加工時間，并對每個工件的總加工時間進行降序排序，將優先排序權賦予排序在前的工件。先將排序中的前f件工件分別分配到f家車間中，車間根據接受到工件的先后次序進行編號，第1個接受到工件的車間為f1，第2個接受到工件的車間為f2，依次生成車間編號。將前f件工件固化到f家車間中，剩余的n-f件工件可以跨車間分配。假設f家車間完全相同，將前f件工件固化到車間之后，能夠有效地區分車間，避免在迭代過程中造成車間之間的混亂。其中前(n-f)/2的工件運用NEH進行排序，剩余的工件進行隨機排序，生成不同的解序列。

每個工件在機器上(的總加)工時間為

式中：Rj,i為工件j在機器i上加工之前所經過機器的集合；pj,i為工件j在機器i上的加工時間。

表1是分布式車間調度問題的案例，將8個需要加工的零件分配到兩個車間進行加工，工件在車間上的加工路徑和在每個機器上的加工時間已經確定。計算出每個工件的總加工時間并進行排序(如表2)，確定工件分配的優先權。先將排序中的前兩個工件分配到車間中確定車間的編碼，再將排序在后的4件工件隨機插入到車間1和車間2的加工序列中，根據獲得的優先權和NEH原則對剩余的工件進行分配和排序，最終形成 可行的分布式車間調度方案。

表 1 分布式工作車間中工件的加工時間和路徑Table 1 Processing time and path in distributed job shop

表 2 優先排序權Table 2 Job priority

2.2 構建概率矩陣模型

精英染色體是篩選出來的高適應度解序列。為了有效地挖掘區塊，MBGA依據迭代過程中篩選的精英染色體構建了兩個概率矩陣：一個是工件-車間分配矩陣，另一個是工件-機器排序矩陣。工件-車間排序矩陣強調的是工件和車間之間的關系，工件-機器排序矩陣強調的是工件在車間內機器上的加工順序。

本文采用世代累加的方式建立概率模型，統計工件在機器上加工的頻次，構建工件-機器排序矩陣。在構建和更新矩陣的過程中，工件j被分配到車間r，工件-車間分配矩陣中相應位置的頻次就會增加1。工件k和工件j分配到同一車間，且在機器上先后加工，工件-機器排序矩陣中的相應位置增加1。然后，將相應的頻次轉化為概率矩陣，并隨著迭代不斷更新。

工件-車間分配矩陣的迭代公式為

工件-機器排序矩陣的迭代公式為

式中：表示工件i在機器j上的總加工次數。

具體的工件-車間分配矩陣的更新過程如圖2所示，假設C1,C2,…,C5為5個用于更新分配矩陣的精英染色體；以工件5為例，有1個精英染色體將工件5分配到車間1，有4個精英染色體將工件5分配到車間2，因此工件5分配到車間1的概率為1/5，分配到車間2的概率為4/5。工件-機器排序矩陣的更新原理同分配矩陣的更新原理相同(如圖3)。

為確保工件j擁有分配到每個車間中每個位置的機會，將概率矩陣中每個位置的概率值增加0.01；在構建人工染色體的時，每個位置可以選到剩余工件的任意一個，增加了樣本的多樣性，避免縮小搜索空間。

圖 2 工件-車間分配概率矩陣示意Fig. 2 Schematic diagram of job-shop assignment probability matrix

圖 3 工件-位置排序矩陣示意Fig. 3 Schematic diagram of job-position sorting matrix

2.3 區塊挖掘

精英染色體的解序列中擁有相似的解序列片段，算法以區塊的形式將這部分信息進行挖掘用于構建高質量的人工染色體。區塊是高適應度解序列中的部分片段，由精英染色體中的高頻率的基因鏈接組成。區塊將不同機器上加工時間互補的工件組合起來，用于平衡工件在機器上的加工時間，優化同一車間內工件的排序過程，并確定工件的分配過程。高質量的區塊保證了人工染色體的優勢，又降低了排序的復雜程度。區塊的規模越大，構建人工染色體的過程就越簡單，但由于工件-車間分配矩陣和工件-機器排序矩陣中的概率都小于1(圖4中的Pblock為挖掘該區塊的頻率)，所以區塊規模越大，挖掘該區塊的概率就越低。本文運用了動態門檻值，適當地增加區塊的規模；區塊的長度為3～5，具體的長度根據門檻值來確定，并且門檻值隨著迭代的進行從0.5～0.8不斷增加。

圖 4 工件-車間分配區塊挖掘方式Fig. 4 Job-shop assignment block mining method

區塊的組合過程如圖5，根據工件-機器排序概率矩陣，通過累積計算區塊生成的概率，再依據 一定的篩選規則組合成區塊庫。

圖 5 工件-位置排序區塊挖掘方式Fig. 5 Job-location sorting block Mining method

在區塊庫中存在部分重復的區塊，通過區塊競爭剔除質量較差并含有重疊部分的區塊。區塊重疊分為兩種：區塊中工件的重復和區塊內機器重復次數超過所需要加工的工序數。在篩選高質量區塊時，優化指標為組合區塊的平均概率，平均概率越小，構建的區塊質量就越差。平均概率為

式中：B(n)為第n塊區塊；L為區塊長度；P(p)是由位 置矩陣得出的概率。

2.4 構建人工染色體

構建人工染色體是算法的另一個重點，既要加快解的匯集速度，又要避免過早收斂，保證解的多樣性和質量。MBGA運用了兩種組合機制構造人工染色體，每種組合機制又分為兩個階段，第一階段是將工件分配到車間中，第二階段是為分配到同一車間的工件排序。組合機制1先根據分配概率和區塊庫將工件分配到車間中，再對分配到同一車間的工件進行排序，若挑選出的工件包含于區塊中第一個位置，則將該區塊插入到該染色體中，若沒有找到相應的區塊，則根據概率矩陣挑選下一個位置的工件；組合機制2先將區塊庫中的區塊復制到染色體中的空白位置，減少工件排序的數量，再隨機將沒有分配的工件復制到人工染色體中剩余的空白位置。

組合機制一的具體過程為：先根據工件-車間分配矩陣運用輪盤賭的方式分配工件，若所選的工件包含于工件-車間區塊中，則將該區塊中所包含的所有工件都分配到同一車間中；若沒有包含于區塊中，則繼續為下一個車間篩選工件，依次將工件分配到總加工時間最少的車間。其次，依據工件-機器排序矩陣運用輪盤賭的方式為同一車間內的工件排序，如果挑選的工件位于工件-機器區塊庫中區塊的第一個位置且包含的工件都在該車間加工，那么就將該區塊插入到相應的位置；如果不是在區塊的首位或者沒有包含該工件的工件-機器排序區塊，那么繼續為下一個工件排序，直到所有確定所有工件的加工順序。如圖6，工件8分配到第一個車間即f1，工件6和工件3與工件8在同一個區塊中，故工件8，6和3被分配到f1中，在剩余工件中隨機的挑選出工件4，7，5和1分配到f2中，最后的工件2分配到f1中。在排序階段，依據工件-機器排序矩陣運用輪盤賭的方式將工件8第排在第一個位置，將工件4排在f2中的第一個位置；工件4位于區塊中的首位，將該區塊復制到染色體的相應位置上；剩余的工件依據工件-機器排序矩陣運用輪盤賭進行排序，直到完成所有工件的排序。

圖 6 第1種組合機制Fig. 6 The first combination mechanism

組合機制2，先將工件-車間區塊庫中的區塊隨機地復制到人工染色體中的空白位置，具體位置由區塊中首個工件分配到車間的概率和在機器上排序的概率決定；然后根據分配和排序矩陣，將未分配的工件插入到人工染色體的空白位置。首先，隨機地將區塊 516復制到染色體中的空白位置(如圖7)具體位置應該根據首個工件(工件1)在各個位置的概率，運用輪盤賭來確定。剩余的工件，還是分為兩個階段根據工件-車間和工件-機器的概率矩陣用輪盤賭進行排序，直到所 有的工件都排序完成。

圖 7 第2種組合機制Fig. 7 The second combination mechanism

2.5 基因重組

通過基因重組發現改良的染色體，直到生成最優的染色體，MBGA改進了基因重組中的交叉產生新的子代。染色體中每行的解序列片段是某一車間內的工件加工順序，所有工件恰好在f間車間內加工完成。在基因交叉的過程中，以每個車間內的工件加工序列(即每行的解序列片段)為交換單位，既能保留父代和每個車間的有效信息，又能搜索每個車間的所有可能解。

適應DJSP的MBGA中，基因交叉的例子如圖8所示，挑選兩個染色體為父代(P1,P2)，從一個父代的解序列中隨機選取f/2行解序列片段，剩余的f/2行解序列片段從另一個父代中選取，按照原行數重新構造解序列(G1)，剩余的解序列片段恰好構成另一個子代(G2)。在兩個新構造的解序列中，挖出解序列中重復加工的工件放進重組工件池，再將重組工件池中的工件分別、依次插入到總加工時間最短的行內，直到所有的工件都被插入到解序列中。重組工件池中的工件都是兩個同時存在的，在選取工件時，應同時將兩個工件分別插入到兩個構造的解序列中。

圖 8 基因交叉Fig. 8 Gene crossing

3 計算結果與分析

為了測試和驗證MBGA的求解能力，在Microsoft Visual Studio 2012中的C++上編寫該算法程序，并在Window8、32位系統、主頻3.40的酷睿CPU、4 GB內存的電腦上運行完成測試。本文測試所用的數據來自Taillard中的生產車間調度問題的基準實例，選取工件個數為15、20、30和機器臺數為15、20共50個組合進行比較分析。比較標準是相對百分比偏差(relative percentage deviation, RPD)，計算公式為

式中：Alg表示運用MBGA獲得最優的最大完工時間；Min表示基準實例所給出的最小化的最大完工時間。

從Taillard中選擇50種具有代表性的例題測試該算法的尋優性能[22]。表3中是在不同的n、m以及加工順序下生成的50種實例組合下，每個組合的平均RPD是對不同車間數f=2,f=3,f=4,f=5的最優RPD平均值。有一半以上的平均RPD為0，證明一半以上的測算實例達到了目前已知的最大完工時間的下限值。

為進一步證明算法的準確性，將例題測算結果文獻[14]提出的模擬退火算法(simulated annealing，SA)、啟發式模擬退火算法(heuristic simulated annealing，HAS)和文獻[22]總結的遺傳算法得出的結果進行比較。表4給出了MBGA的平均PRD與其他算法的平均PRD的數值，MBGA的平均PRD數值最小為0.21。相較于GA、SA和HAS，MBGA得出的最大完工時間最小。

表 3 實例測試結果Table 3 Example test results

表 4 不同算法的RPDTable 4 RPD of different algorithms

圖9顯示了每個算法的平均RPD與工件數的關系。從圖中，能夠清楚的看出，GA和SA的RPD值隨著工件數的增加而增加，HAS的RPD值隨著工件數的增加而波動，而MBGA的RPD比較穩定，且MBGA的RPD值均小于其他3個算法的RPD值，表明MBGA得到的解序列更加接近標準解序列。圖10表示一批工件在不同數目工作車間加工，4種算法的RPD值變化趨勢。GA的RPD隨著車間數的增加而減小，SA、HAS和MBGA的RPD值都隨著車間數的增加而減小，表明MBGA中基于區塊的人工染色體對原有GA的改進更適合分布式車間調度問題。綜上可得，MBGA具有較優的穩定性和準確性。

圖 9 平均RPD與工件數的關系Fig. 9 Relationship between average RPD and number of jobs

圖 10 平均RPD與車間數的關系Fig. 10 Relationship between average RPD and the num- ber of jobs

4 結束語

本文針對分布式工作車間調度問題，提出了MBGA。算法構建了分配區塊庫和排序區塊庫，保留和傳遞了精英染色體中的高頻率基因鏈，統一考慮了排序過程中每個車間機器工作量的平衡性和排序過程中工件加工的先后順序。借助區塊庫中的區塊，運用兩種組合機制構建了高質量的人工染色體；一種組合機制應用區塊通過先分配后排序的順序構建了一類人工染色體，另一種組合機制先在人工染色體中填充區塊，同步進行工件的分配和排序兩個階段，再將剩余的工件按照先分配后排序的順序構建第二類人工染色體，增加了人工染色體的多樣性。改進區塊遺傳算法中的基因重組大幅度地改良了當前代的人工染色體，保留了父代和每個車間的有效信息，又具有搜索每個車間的能力。算例測算表明，該算法具有較好的穩定性和準確性。

MBGA有效地解決了分布式生產車間調度問題，未來還可以嘗試深入研究，如改變假設條件，當每個車間的工件的加工能力存在差異時，求解最優的調度方案。