裴小兵，孫志衛(wèi)

（天津理工大學(xué) 管理學(xué)院，天津 300384）

隨著生產(chǎn)全球化和制造規(guī)?；笮椭圃炱髽I(yè)為降低成本、提高生產(chǎn)柔性與生產(chǎn)效率以快速滿足全球市場需求，生產(chǎn)方式正由集中性單車間生產(chǎn)向分布式車間生產(chǎn)轉(zhuǎn)變。但是相關(guān)文獻研究還主要集中在單個車間生產(chǎn)調(diào)度[1]。近年來，分布式車間調(diào)度問題(distributed job-shop scheduling problem，DJSP)在車間調(diào)度研究領(lǐng)域逐漸受到關(guān)注，如對關(guān)鍵路徑的二車間綜合調(diào)度問題[2]、分布式流程車間問題[3]、多工序同時結(jié)束的多車間逆序綜合調(diào)度[4]和分布式工作車間問題[5-6]等。

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

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

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

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

1 數(shù)學(xué)模型的闡述

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

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

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

決策變量為： 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上累計加工時間的連續(xù)變量。

整體線性規(guī)劃模型為：

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

Subject to:

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

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

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

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

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

2 改進區(qū)塊遺傳算法

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

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

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

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

4)組合區(qū)塊。根據(jù)概率矩陣中的信息，組合區(qū)塊。

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

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

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

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

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

2.1 生成初始解

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

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

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

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

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

表 2 優(yōu)先排序權(quán)Table 2 Job priority

2.2 構(gòu)建概率矩陣模型

精英染色體是篩選出來的高適應(yīng)度解序列。為了有效地挖掘區(qū)塊，MBGA依據(jù)迭代過程中篩選的精英染色體構(gòu)建了兩個概率矩陣：一個是工件-車間分配矩陣，另一個是工件-機器排序矩陣。工件-車間排序矩陣強調(diào)的是工件和車間之間的關(guān)系，工件-機器排序矩陣強調(diào)的是工件在車間內(nèi)機器上的加工順序。

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

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

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

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

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

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

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

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

2.3 區(qū)塊挖掘

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

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

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

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

在區(qū)塊庫中存在部分重復(fù)的區(qū)塊，通過區(qū)塊競爭剔除質(zhì)量較差并含有重疊部分的區(qū)塊。區(qū)塊重疊分為兩種：區(qū)塊中工件的重復(fù)和區(qū)塊內(nèi)機器重復(fù)次數(shù)超過所需要加工的工序數(shù)。在篩選高質(zhì)量區(qū)塊時，優(yōu)化指標為組合區(qū)塊的平均概率，平均概率越小，構(gòu)建的區(qū)塊質(zhì)量就越差。平均概率為

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

2.4 構(gòu)建人工染色體

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

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

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

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

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

2.5 基因重組

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

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

圖 8 基因交叉Fig. 8 Gene crossing

3 計算結(jié)果與分析

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

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

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

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

表 3 實例測試結(jié)果Table 3 Example test results

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

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

圖 9 平均RPD與工件數(shù)的關(guān)系Fig. 9 Relationship between average RPD and number of jobs

圖 10 平均RPD與車間數(shù)的關(guān)系Fig. 10 Relationship between average RPD and the num- ber of jobs

4 結(jié)束語

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

MBGA有效地解決了分布式生產(chǎn)車間調(diào)度問題，未來還可以嘗試深入研究，如改變假設(shè)條件，當(dāng)每個車間的工件的加工能力存在差異時，求解最優(yōu)的調(diào)度方案。