改進(jìn)區(qū)塊遺傳算法解決分布式車間調(diào)度問題

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

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

隨著生產(chǎn)全球化和制造規(guī)?；?，大型制造企業(yè)為降低成本、提高生產(chǎn)柔性與生產(chǎn)效率以快速滿足全球市場需求，生產(chǎn)方式正由集中性單車間生產(chǎn)向分布式車間生產(chǎn)轉(zhuǎn)變。但是相關(guān)文獻(xiàn)研究還主要集中在單個(gè)車間生產(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]、多工序同時(shí)結(jié)束的多車間逆序綜合調(diào)度[4]和分布式工作車間問題[5-6]等。

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

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

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

目前關(guān)于分布式車間調(diào)度問題的文獻(xiàn)相對較少，現(xiàn)有研究將分配和排序兩階段分別考慮，在分配階段僅考慮每個(gè)車間每臺機(jī)器的工作量均衡，未涉及下一階段的工件排序，其結(jié)果可能會增加分布式車間的最大完工時(shí)間。同時(shí)大部分針對分布式車間調(diào)度問題的優(yōu)化算法沒有清晰地說明如何通過變異、重組等操作使當(dāng)前解集不斷進(jìn)化，部分文獻(xiàn)僅對分配到不同車間的n個(gè)工件中的兩個(gè)或少數(shù)幾個(gè)工件進(jìn)行連續(xù)調(diào)換來優(yōu)化當(dāng)前解，本文嘗試同時(shí)調(diào)整解序列中車間的分配和工件的排序來增加解的多樣性。本文基于區(qū)塊構(gòu)建高質(zhì)量人工染色體改進(jìn)傳統(tǒng)遺傳算法，應(yīng)用區(qū)塊保留并傳遞精英染色體中的高頻率基因鏈，協(xié)調(diào)分布式車間調(diào)度問題中的分配和排序兩階段；改進(jìn)區(qū)塊遺傳算法中的基因重組和人工染色體的構(gòu)建，使之適應(yīng)于分布式車間調(diào)度問題。本研究以改進(jìn)后適應(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間車間中，每個(gè)車間以一定的順序共同加工完成這批零件，確定這批工件分配和排序的方案。每個(gè)車間擁有m臺機(jī)器，且具有獨(dú)立加工完成每個(gè)工件的能力，與車間調(diào)度問題中的條件相同。假設(shè)分布在不同區(qū)域的f個(gè)車間的生產(chǎn)能力是相同的，具有相同的機(jī)器和車間布局；所需加工的工件可以在任意車間內(nèi)加工完成，且加工所需的時(shí)間是相同的；不考慮工資水平、運(yùn)輸距離等因素。在工件加工過程中，已經(jīng)分配到加工車間的工件禁止轉(zhuǎn)移到其他車間加工，因?yàn)楣ぜ谲囬g之間的交叉加工將增加成本和技術(shù)難度。DJSP的約束條件為：1）每個(gè)工件只能分配到一個(gè)車間內(nèi)，且每個(gè)工件都由特定的車間加工；2）每臺機(jī)器只能同時(shí)加工一個(gè)零件，每個(gè)零件只能同時(shí)由一臺機(jī)器加工；3）分配到同一車間內(nèi)的工件都在該車間內(nèi)順序加工；4）n件工件的最大完工時(shí)間就是f個(gè)車間中完工時(shí)間最長的車間的最大完工時(shí)間。則DJSP整數(shù)線性規(guī)劃模型為：

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

決策變量為： Xk,j,u取0，1值，如果機(jī)器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在機(jī)器i上累計(jì)加工時(shí)間的連續(xù)變量。

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

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

Subject to:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 生成初始解

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

每個(gè)工件在機(jī)器上(的總加)工時(shí)間為

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

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

表 1 分布式工作車間中工件的加工時(shí)間和路徑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)建了兩個(gè)概率矩陣：一個(gè)是工件-車間分配矩陣，另一個(gè)是工件-機(jī)器排序矩陣。工件-車間排序矩陣強(qiáng)調(diào)的是工件和車間之間的關(guān)系，工件-機(jī)器排序矩陣強(qiáng)調(diào)的是工件在車間內(nèi)機(jī)器上的加工順序。

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

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

工件-機(jī)器排序矩陣的迭代公式為

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

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

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

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

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

區(qū)塊的組合過程如圖5，根據(jù)工件-機(jī)器排序概率矩陣，通過累積計(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)機(jī)器重復(fù)次數(shù)超過所需要加工的工序數(shù)。在篩選高質(zhì)量區(qū)塊時(shí)，優(yōu)化指標(biāo)為組合區(qū)塊的平均概率，平均概率越小，構(gòu)建的區(qū)塊質(zhì)量就越差。平均概率為

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

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

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

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

圖 6 第1種組合機(jī)制Fig. 6 The first combination mechanism

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

圖 7 第2種組合機(jī)制Fig. 7 The second combination mechanism

2.5 基因重組

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

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

圖 8 基因交叉Fig. 8 Gene crossing

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

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

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

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

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

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

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

圖9顯示了每個(gè)算法的平均RPD與工件數(shù)的關(guān)系。從圖中，能夠清楚的看出，GA和SA的RPD值隨著工件數(shù)的增加而增加，HAS的RPD值隨著工件數(shù)的增加而波動，而MBGA的RPD比較穩(wěn)定，且MBGA的RPD值均小于其他3個(gè)算法的RPD值，表明MBGA得到的解序列更加接近標(biāo)準(zhǔn)解序列。圖10表示一批工件在不同數(shù)目工作車間加工，4種算法的RPD值變化趨勢。GA的RPD隨著車間數(shù)的增加而減小，SA、HAS和MBGA的RPD值都隨著車間數(shù)的增加而減小，表明MBGA中基于區(qū)塊的人工染色體對原有GA的改進(jìn)更適合分布式車間調(diào)度問題。綜上可得，MBGA具有較優(yōu)的穩(wěn)定性和準(zhǔ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)一考慮了排序過程中每個(gè)車間機(jī)器工作量的平衡性和排序過程中工件加工的先后順序。借助區(qū)塊庫中的區(qū)塊，運(yùn)用兩種組合機(jī)制構(gòu)建了高質(zhì)量的人工染色體；一種組合機(jī)制應(yīng)用區(qū)塊通過先分配后排序的順序構(gòu)建了一類人工染色體，另一種組合機(jī)制先在人工染色體中填充區(qū)塊，同步進(jìn)行工件的分配和排序兩個(gè)階段，再將剩余的工件按照先分配后排序的順序構(gòu)建第二類人工染色體，增加了人工染色體的多樣性。改進(jìn)區(qū)塊遺傳算法中的基因重組大幅度地改良了當(dāng)前代的人工染色體，保留了父代和每個(gè)車間的有效信息，又具有搜索每個(gè)車間的能力。算例測算表明，該算法具有較好的穩(wěn)定性和準(zhǔn)確性。

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