基于混合元胞遺傳算法的柔性車間調度問題研究

楊宇琪 張 屹 張貴東 陸曈曈

(1. 三峽大學 機械與動力學院， 湖北 宜昌 443002； 2. 三峽大學 經濟與管理學院， 湖北 宜昌 443002)

生產調度是制造型企業生產過程中至關重要的環節之一，與生產效率密切相關．運用合理的調度方法可以縮短工期，按時交貨且達到機器利用的合理化．作業車間調度問題(job-shop scheduling problem，JSP)是當前生產制造及組合優化等領域的熱點問題之一．在JSP中，每道工序均被指定在一臺設備上完成加工．若某一工序能夠在若干臺設備上加工，則作業車間調度問題就擴展為了柔性作業車間調度(flexible job-shop scheduling problem，FJSP)[1-2]．由于FJSP的設備約束減少，導致生產調度柔性更高，更符合制造企業生產現場的實際情況．

目前，海內外諸多研究人員對柔性車間調度問題開展了相關研究．黎冰[3]等針對非確定約束限制的流水作業車間調度問題，構建了含多種參數的混合機會約束規劃模型．巴黎[4]等將成品件的完工時間作為優化目標，對該批量裝配的FJSP進行建模，運用了粒子群算法求解．唐自玉[5]基于多色集合理論對FJSP進行了研究，提升了機器負荷率、產線負荷均衡率、產線柔性度及有效生產面積利用率，但在解的收斂性方面仍有改進空間．

針對遺傳算法在求解FJSP時通常出現的早熟和收斂較慢等問題，本文通過引入多色集合理論，建立了FJSP的多色集合約束模型，并與多目標元胞遺傳算法結合，提出了一種基于多色集合的元胞遺傳算法，通過在編碼、解碼及變異過程中，將搜索范圍限定為圍道布爾矩陣，即有效解范圍，以致在保證所得解均是有效解的同時，還能優化最優解的收斂速度．同時還可以利用圍道布爾矩陣簡化適應度的計算，降低算法復雜度．最后應用改進的元胞遺傳算法求解FJSP，并與其它遺傳算法求解相同實例的結果進行對比，進而驗證該算法的有效性．

1 FJSP優化數學模型的建立

1.1 目標函數的確定

考慮到單目標車間調度優化研究已難以滿足制造企業實際的生產要求，于是考慮多個目標，分別是工件的最大完工時間(Cm)，最大負荷機器的負荷(Wm)和機器總負荷(Wt)．其中，最大完工時間影響著每個工件的生產周期，機器負荷與各臺機器的使用率成正相關．

1)最大完工時間最小：每個工件開始加工到最后一個工序加工完成之間耗時最長的時間最小，它是評價車間生產高效與否的主要體現．

Cm=min(max(Ck)) 1≤k≤m

2)機器最大負荷最小：負荷最大的機器是瓶頸設備，為提高每臺機器的使用率，應使各臺機器的負荷盡量小以達到平衡．

Wm=min(max(Wk)) 1≤k≤m

式中，Wm表示序號為m的機器的總時間負荷．

3)總機器負荷最小：不同機器加工同一工序的耗時不同，因此總時間負荷因調度方案的差異性而不同，若最大完工時間相同，則機器的總負荷越小越好．

1.2 約束條件的確定

柔性作業車間調度指的是在生產加工系統中，存在一個需生產加工的作業集，其中包含n個待加工的工件，用集合表示為J=(J1，J2，…，Jn)，包含加工機床集合M=(M1，M2，…，Mm)，該集合中共有m臺可供加工的機床，每個待加工的工件均必須經由若干工序才能夠完成最終生產．Ojik可被定義為工件i在機床k上加工第j道工序．

工序的加工路徑并非唯一，一道工序能在一臺或多臺機器上完成加工，并且在不同機器上加工耗時均不同．現對常規加工條件進行一定的約束如下：i為工件的序號，i=1，2，…，n；k為機器序號，k=1，2，…，m；j為加工工序號；hij為工件i的加工工序數；tijk為工件i的第j道工序在機器k上加工的耗時；sij為工件i的第j道工序的起始時間；eij為工件i的第j道工序的完工時間；Tij為工件i的第j道工序的加工時間；R為一個無窮大的正整數；ci為每個工件的所有工序完成后的時間；Cmax為最大完工時間；

1)工序約束：在工件加工過程中，必須按照確定的工藝順序加工，即必須在前一道工序完工之后，下一道工序才可以被加工，故需滿足如下條件：

sij+xijk×tijk≤eij

i=1，2，…，n；k=1，2，…，m；1≤j≤hij

(1)

eij≤Cmax

i=1，2，…，n；1≤j≤hij

(2)

2)完工時間約束：工件加工進程中，任意一個工件的完工時間均小于全部工件完成加工的總完工時間，即

cij≤Cmaxi=1，2，…，n；1≤j≤hij

(3)

3)加工時間約束1：工件加工過程中，同一時間內任意一臺機床只能加工一道工序，不能加工多道工序，即

eij+eijk≤sef+R(1-yijefk)

i=1，2，…，n；k=1，2，…m；1≤j≤hij

(4)

4)加工時間約束2：工件加工過程中，任意一個工件的任意一道工序的結束時間小于等于該工件下道工序的起始時間，即

eij≤si(j+1)+R(1-yefi(j+1)k)

i=1，2，…，n；k=1，2，…m

(5)

5)機床約束：工件加工過程中，在某一時刻，某道工序只能在某一臺允許的機床上加工，不能出現兩臺或更多機床進行加工的情況，則

；1≤j≤hij

(6)

6)其它約束：上述約束中所提到的各項參數均是大于等于零的正數，即

sij≥0，eij≥0

(7)

2 柔性車間調度的多色集合約束模型的建立

多色集合理論主要用于表達車間調度模型中的約束關系，利用多色集合理論的統一著色及個體著色等概念，建立能夠表達柔性車間調度優化模型中的工序與工件之間、工序與機床之間約束關系的圍道布爾矩陣．多色集合的顏色集合F(ai)用于描述元素ai的本身屬性，稱為元素的個人顏色．集合A與全部元素的個體著色F(a)構成的布爾矩陣A×F(a)可表示如下：

F1…Fj…Fm

(8)

矩陣(8)表示了元素的圍道組成，對象A所對應的集合F(A)，元素ai所對應的圍道集合為F(ai)，ai∈A．如果F(A)∈F(ai)，則cij=1，反之cij=0．基于工件與工序、工序與設備之間存在對應關系，所以用多色集合的圍道布爾矩陣可以較為準確地描述作業車間中工件、工序和機床之間的相互關系．

本文以表1中3×5的FJSP為例，說明如何使用多色集合的圍道矩陣來描述待加工工序的工藝約束和機床約束之間的關系．

表1 柔性車間調度問題實例

1)工藝約束模型

3個工件的工件-工序圍道布爾矩陣見式(9).該矩陣表明：工件1有3道工序，分別為101，102，103．工件2和工件3分別也有3道工序，即為201，202，203；301，302，303．

(9)

2)設備約束模型

3個工件的工序-機床圍道布爾矩陣見式(10)．

(10)

矩陣(10)的行代表工序編碼，列代表機床編碼，布爾值為1代表該工序能夠使用該機床加工，0則反之．上述矩陣即為加工關系的約束模型，它的功能就是表示同一類工件的工序及對應加工機床的狀態．

3 基于多色集合約束模型的元胞遺傳算法(PCGA)

Nebro[6]等人在2009年提出的多目標元胞遺傳算法(a cellular genetic algorithm for multi-objective optimization，CGA)是一種基于對種群結構進行改進的遺傳算法，該算法涵蓋了多目標優化理論的核心思想，具有遺傳算法的原始理論基礎，除此之外，與元胞自動機模型進行了有機結合，是一種包含多種優異特征的集成式優化算法．其算法兼具遺傳算法和元胞自動機的優良特性，在求解多目標優化問題時表現出了較好的多樣性和收斂性，并在許多實際工程應用中表現效果顯著[7]．元胞遺傳算法架構如圖1所示．

圖1 元胞遺傳算法架構圖

3.1 基于約束模型的編碼和解碼

目前很多方法均采取基于工序的編碼求解經典調度問題，其主要思想是把調度編碼成工序序列，單個基因對應單一工序，同樣工件的工序采用同樣的符號進行表達，繼而可由其在指定染色體中出現的次序來詮釋．但是該法傾向于解決設備事先確定的調度問題．本文采用雙層編碼法，即基于工序的編碼和基于設備的編碼．

1)編碼

第1層編碼采取自然數編碼，因為子代經由遺傳操作可以獲得父代的優良特征，所以具有優先權原則和Lamarckian特點[8]，同時調度的可行性可以得到有效保證，具有2類解碼復雜性，因此可直接采用隨機數作為編碼基因．如表2所示，101-303共9道工序的第1層編碼為1-9的自然數隨機排列．

表2 編碼方案

第2層編碼采用實數編碼法，由上述可知第1層編碼表達的是所有工序對應的可加工設備編號，因此，已知某道工序，搜索圍道矩陣式(10)獲得統一顏色為1的對應的多臺設備，然后從這些設備編號里任意選取一個作為第2層編碼中相應位置的基因，來保證每一個基因的有效性．

2)解碼

解碼的目的是確定工序的加工順序．由于第1層編碼具有2類解碼復雜性[9]，第2層編碼卻具有0類解碼復雜性，即不需要解碼，于是，解碼是針對第1層編碼．

Step1：搜索矩陣(9)，從矩陣中找到每一列首個非0的元素，記下該元素所在行對應的那一道工序．矩陣(9)的行表示同一工件的所有工序的允許先后加工順序，這樣可表示各個工件所有工序之間先后加工的關系約束．

Step2：比較從Step1中挑選出的工序在首層編碼中相應的基因值的大小，篩選出值最小的那道工序．

Step3：由Step2可得到基因最小的工件及工序，把矩陣(9)中該工件的相應位置的數值置為0，即摒棄該工序．

不斷重復上述3道步驟到全部工序的加工順序得以確定為止．由于其始終在約束條件下進行，從而保證每一個工件工序是按照先后關系來選擇的．

采用以上所述方法，可得到首層編碼在進行解碼之后的工序先后加工順序為：201-101-102-301-103-302-303-202-203．由解碼后的加工順序和第2層編碼進行對照，可得到加工這些工序的設備依次為：3-2-4-4-1-5-1-2-5．見表3．

表3 解碼后的調度安排

3.2 選擇操作

在元胞遺傳算法中，為了減少選擇壓力，一般將選擇操作限定在鄰居中施行．于是，引入一種方法，其能借由個體的適應度自適應選擇個體．

以Moore型鄰居結構[7]為例，每一個體相鄰的8個元胞為其鄰居，即左上、左下、右上、右下、上、下、左、右8個方向的個體．首先，通過一定的方式計算鄰居的適應度值，找到最差適應度、最優適應度及中心個體適應度，再經由適應度的大小，按照從小到大的次序依次將個體存入集合List．此外還需注意，通過比較相對適應度值更有說服力，因此歸一化處理中心個體的適應度值，其后就可得知此個體在鄰居中的相對適應度RF，即

然后，在集合List中選取List[round(RF×List.size)]和中心個體施行交叉變異操作，式中round()表示取整操作，List.size表示集合List的大小．

3.3 交叉操作

交叉操作就是通過交換父代之間的染色體，進而生成比父代更優秀的后代．交叉操作的優劣直接決定著子代解的優劣，同時對算法的性能亦會造成相應影響．對于第2層編碼，采用直接交叉法，即直接對交叉點間的片段互換．對于第1層編碼的交叉操作，則可采用較為傳統的線性次序交叉法．根據交叉概率，選出交叉的兩個父代染色體P1、P2，得到交叉得到的子代染色體為C1、C2．

1)隨機選擇交叉點e1，e2，其中1

2)把P1片段中的第e1→e2位與P2片段中的第e1→e2位進行交換，獲得子代C1，C2染色體的一部分基因．(此時C1，C2中只有e2-e1+1個基因)

3)從P1中剔除掉P2中對應的第e1→e2位基因，將P1中剔除之后的剩余基因按順序填充到C1的空位中．

4)從P2中剔除掉P1中對應的第e1→e2位基因，將P2中剔除之后的剩余基因按順序填充到C2的空位中．

圖2 交叉示意圖

3.4 變異操作

對于首層編碼，采取互換變異法，也就是隨機交換染色體中兩個不同基因的相互位置．對于第2層編碼，采用多位置替換式變異，首先確定變異位置，然后搜索“工序-設備”矩陣，找出可加工工序的設備．將基因值與上面設備的編號中的任意一個互換，這樣就保證了變異之后的基因是有效的．

3.5 PCGA算法流程圖

基于多色集合約束模型的元胞遺傳算法流程圖如圖3所示．

圖3 PCGA算法流程圖

將約束模型引入到遺傳算法的具體作用為：

1)去掉無意義的解、無效解，進而保證所得解均為有效解．欲限制非法解的產生，一般有兩種方法：①設計新的染色體編碼或遺傳算子，進而加強解的可行性判斷；②利用罰函數來削弱或者消除非法解．本文采用第1種方法，在模型約束下，所有遺傳操作之后的染色體個體都代表一個有效的調度方案；且由于約束模型的引入，遺傳編碼和遺傳算子的設計也都被簡化處理．

2)縮小解的空間，降低早熟收斂的可能性、改善收斂速度．

4 實例求解與分析

為了評估本文提出算法的性能，選取文獻[10]中3種標準測試案例對算法進行測試，分別是8×8，10×10和15×10三種車間調度問題，并與其它算法進行比較，如KACEM[10]、傳統GA等．

改進算法使用Java編程，其具體參數為：種群大小100，交叉概率0.5，變異概率0.01，選取Moore型鄰居結構．其他算法的參數配置與原文獻相同．每一個實例針對3個目標函數分別獨立運行10次．測試結果見表4．

表4 測試結果比較

從表4中能夠得出，基于多色集合約束模型的元胞遺傳算法所求得的結果均小于或等于其他算法求得的最優解，且經過10次運行后的均值亦相對接近最優解，表明本文所提出的PCGA算法在求解多目標柔性車間調度問題時具有一定的優勢．

圖4是本文算法在8×8問題上求得最大完工時間是14的甘特圖，圖5是本文算法在10×10問題上求得最大完工時間是7的甘特圖，圖6是本文算法在15×10問題上求得最大完工時間是11的甘特圖．

圖4 8×8問題Cm最小值為14的甘特圖

圖5 10×10問題Cm最小值為7的甘特圖

圖6 15×10問題Cm最小值為11的甘特圖

圖7為PCGA與經典GA及CGA之間的迭代對比圖，由圖7能夠看到PCGA的收斂速度相對較快，在50代左右就能夠找到最優值．

圖7 GA，CGA和PCGA的迭代對比圖

綜上所述，本文提出的基于多色集合約束模型的元胞遺傳算法在求解多目標柔性車間調度上行之有效，與其它算法相比，具有一定的競爭力．

5 結 語

本文針對FJSP展開相應研究，構建了FJSP的多目標優化模型，結合FJSP的特點，通過引入多色集合理論，建立了FJSP的多色集合約束模型，提出了基于多色集合約束模型的元胞遺傳算法．與其它算法經過相同的實例測試后，本文所提出的算法所得結果等于或小于其它算法所得結果，同時該算法收斂到最優解的速度更快，且計算過程相對穩定．相比于其它同等條件下的調度優化結果，本文所提出的算法在有效性得到驗證的同時具有一定的優勢．

[1] 王 凌．車間調度及其遺傳算法[M]．北京：清華大學出版社，2003．

[2] 王萬良，吳啟迪．生產調度智能算法及其應用[M]．北京：科學出版社，2007．

[3] 黎 冰，顧幸生．混合規劃處理流水車間調度問題[J]．華東理工大學學報：自然科學版，2006，32(1):98-102．

[4] 巴 黎，李 言，曹 源，等．考慮批量裝配的柔性作業車間調度問題研究[J]．中國機械工程，2015，26(23):3200-3207．

[5] 唐自玉．基于多色集合理論的柔性生產線及車間規劃方法研究[D]．合肥：合肥工業大學，2009．

[6] Nebro A J， Durillo J J, Luna F, et al． MOCell:Acellular genetic algorithm for multiobjectiveoptimization[J]．International Journal of Intelligent Systems,2009,24(7):726-746．

[7] 魯宇明．元胞遺傳算法研究及應用[D]．南京：南京航空航天大學, 2013．

[8] 郭冬芬，李鐵克．基于約束滿足的車間調度算法綜述[J]．計算機集成制造系統，2007，13(1):117-125．

[9] Alba E， Dorronsoro B．Computing nine new best-so-far solutions for Capacitated VRP with a cellular Genetic Algorithm[J]． Information Processing Letters,2006, 98(6):225-230．

[10] Kacem I, Hammadi S, Borne P． Approach by Localization and Genetic Manipulation Algorithm for Flexible Job-shop Scheduling Problem[C]//IEEE International Conference on Systems, Man, and Cybernetics． IEEE Xplore,2001(4)：2599-2604．