羅亞波， 余晗琳

(武漢理工大學機電工程學院，湖北 武漢 430070)

作為一種需滿足設備和工藝復雜約束條件的組合優(yōu)化問題，作業(yè)車間調(diào)度問題(job shop scheduling problem，JSSP)是典型的NP-hard問題，難以用傳統(tǒng)優(yōu)化方法求解。如何可靠、高效地求解JSSP已成為組合優(yōu)化領(lǐng)域的研究重點和熱點[1-3]，并已取得較多成果[4-7]。

目前作業(yè)車間調(diào)度常用的方法有基于規(guī)則的啟發(fā)式算法[5]、遺傳算法[6]、蟻群算法[7]、粒子群算法[8]、蜂群算法[9]以及將各種算法機制相結(jié)合形成的混合算法。其中，遺傳算法與蟻群算法是應用較多的2種算法。遺傳算法主要通過改進編碼方式或改進適應度設置方法來進行優(yōu)化[10-12]，如 DRISS等[13]提出一種采用新的染色體表達方式的遺傳算法，并在一系列基準數(shù)據(jù)集的基礎(chǔ)上進行了驗證。蟻群算法主要有一階變量和二階變量2類或衍生改進的算法。如ZHAO等[14]提出了用于處理路線決策和任務排序的兩代帕雷托蟻群算法?；旌纤惴ㄍǔＪ菍⒘硪粋€算法的機制融合到主算法中[15]，并對主算法進行改進[16]，如混合遺傳算法[17-18]。雖然這些算法在求解 JSSP方面有較多成果，但也存在一定的局限，如調(diào)度規(guī)模較小[19]、工序關(guān)系主要以串行為主等，對存在并行、甚至嵌套關(guān)系的復雜關(guān)聯(lián)約束調(diào)度問題，研究還比較少。

當 JSSP規(guī)模較大且存在復雜關(guān)聯(lián)約束時，解空間的復雜度呈幾何級數(shù)上升，這種情況下，即使尋找可行解也有較大的困難。為此，依據(jù) JSSP包含“設備分配”和“工序排序” 2個相互耦合的子問題的特征，本研究構(gòu)造將遺傳算法與蟻群算法集成到一個完整循環(huán)體的二級嵌套混合算法，以在可接受的迭代次數(shù)內(nèi)求得比較滿意的調(diào)度方案，增加搜索效率和收斂可靠性。

1 二級嵌套模型及其基本思路

為了能采用混合算法求解復雜關(guān)聯(lián)約束問題，首先，從二級嵌套的角度構(gòu)造包含復雜關(guān)聯(lián)約束的JSSP的數(shù)學模型。

以任務工序與設備的關(guān)聯(lián)關(guān)系的圖1為例，共有4項獨立的任務，每項任務均包含串行和并行的工序關(guān)系，共 33道工序，調(diào)度的目標是：將這些工序合理地分配到A (A1，A2)，B (B1，B2，B3)，C (C1，C2) 3類共7臺設備上，使得總加工時間最短。與每一道工序相關(guān)聯(lián)的有：前序工序、工序所需設備、工序時間。需要滿足的約束包括：

(1) 前序工序約束。某工序啟動前必須完成其他工序，且必須完成的工序完成后就一定能啟動某工序，將必須預先完成的工序稱為某工序的前序工序。如工序309，其前序工序為307和308，即：307和 308都完成了，就(才)可以啟動工序309。

圖1 任務工序與設備的關(guān)聯(lián)關(guān)系示例圖

(2) 設備匹配約束。工序必須分配到與之對應的加工類型的設備上，如各式機床、熱處理設備等。在圖中用字母A，B，C表示3類不同的設備，如工序401必須分配至B類設備上，即B1，B2，或者B3上。

(3) 工件獨占約束。在同一時間，單一工件只能有一道工序處于加工狀態(tài)。

(4) 設備獨占約束。在同一時間，單一設備上只能有一道工序處于加工狀態(tài)。

二級嵌套模型，即將問題分解為2個互有信息交換的子優(yōu)化模型，分別求解工序的設備分配與工序在設備上的排序。假設作業(yè)車間系統(tǒng)中，有m臺設備，n道工序，則優(yōu)化模型如下：

一級：設備分配

求En(En表示各工序的設備分配方案)

MinC=Min{max(Bj+Tj)}

(j=1,2,···,m)

s.t

Ei=Ri(i=1,2,···,n)BE(i+1)j-BEij≥SEij

(i=1,2,···,n；j=1,2,···,m)

其中，C為第j臺設備后道工序啟動時間；Bj為第j臺設備啟動時間；Tj為第j臺設備從啟動到關(guān)停的時間；Ei為第i項工序的設備分配方案；Ri為第i項工序所需的設備類型；BE(i+1)j為第j臺設備上排列的第i+1項工序的開始時間；BEij為第j臺設備上排列的第i項工序的開始時間；SEij為第j臺設備上排列的第i項工序的標準工時。

二級：工序排序

求Pn(Pn表示各工序在所分配設備上的排序)MinCEn= Min{max(BEnj+TEnj)}

(j=1,2,···,m)

s.t

Bik-Bi≥Sik

(i=1,2,···,n；k=1,2,···,i)BE(i+1)j-BEij≥SEij

(i=1,2,···,n；j=1,2,···,m)

Bi(qr)+Si(qr)≤Bi(q(r+u))

其中，CEn為En各設備分配方案的完工時間；BEnj為在En各設備分配方案中的第j臺設備啟動時間；TEnj為在En各設備分配方案中第j臺設備從啟動到關(guān)停的時間；Bik為第i項工序的第k項前序工序的開始時間；Bi為第i項工序的開始啟動時間；Sik為第i項工序的第k項前道工序的標準工時；BE(i+1)j為第j臺設備上排列的第i+1項工序的開始時間；BEij為第j臺設備上排列的第i項工序的開始時間；SEij為第j臺設備上排列的第i項工序的標準工時；Bi(qr)為第q個工件的第r項工序的開始時間；Si(qr)為第q個工件的第r項工序的標準工時；Bi(q(r+u))為q個工件的第r+u項工序的開始時間。

二級嵌套混合算法流程如圖2所示，其基本思路是：發(fā)揮遺傳算法求解“分配問題”和蟻群算法求解“排序問題”的優(yōu)勢。一級優(yōu)化采用遺傳算法求解工序的設備分配方案，二級優(yōu)化采用蟻群算法求解與設備分配方案對應的工序最優(yōu)排序，將一級優(yōu)化結(jié)果作為螞蟻的約束條件輸入到二級迭代過程，將二級優(yōu)化結(jié)果作為適應度信息反饋給一級迭代過程，從而形成完整的二級嵌套循環(huán)迭代過程。

圖2 二級嵌套混合算法流程圖

2 面向設備分配的改進遺傳算法

2.1 改進的編碼策略：基于工序的整數(shù)編碼策略

采用遺傳算法求解作業(yè)調(diào)度問題，如何將問題的方案轉(zhuǎn)換為按一定規(guī)則編碼表達的染色體是關(guān)鍵，好的編碼方式既可以完整表達方案，又可避免信息冗余，從而降低時間復雜度和空間復雜度。以圖 1為例，若使用傳統(tǒng)的二進制編碼，個體的編碼長度為 7×33位的染色體，見表 1。表1存在大量編碼資源冗余，如：與 A類設備不匹配的工序所對應的“基因位”數(shù)值必須為0，該基因位的存在，占用了信息資源，但在迭代過程中并沒有作用，造成了編碼資源冗余，可導致搜索效率大幅度下降。

表1 一種傳統(tǒng)的表達設備分配的編碼方式

根據(jù)設備匹配約束，對編碼方式進行改進，可大幅度節(jié)省編碼資源。其改進方式如下：

首先，根據(jù)圖 1，建立各類設備的工序集合，見表2，其中，設備號中ε是一個符號變量，表示該類設備編號：εa?{ε|ε=0,1}，εb?{ε|ε=0,1,2}，εc?{ε|ε=0,1}。

例如：當εa=0，表示選擇設備A1；當εb=2，表示選擇設備 B3。當要求在該類設備上進行加工的工序時，常規(guī)數(shù)字為工件號，下角標數(shù)字為工件相應的加工序號。例如 11表示工序 101，210表示工序210。

表2 設備工序集

其次，將上述待加工的工序按表中 A，B，C 3類設備的順序排列成一個 33位的編碼序列，如圖3所示，編碼的設計變量X={X1,X2,···,X33}，表示設備分配方案，Xi為第i個基因位上的值。

Xi? {Xi|X1～9=εa, X10～23=εb, X24～33=εc}

圖3 染色體編碼源基因位

例如：X1～90 1 1 0 0 0 0 1 1，X10～231 0 1 2 2 2 0 1 2 0 0 1 1 2，X24～330 1 1 0 0 1 1 0 0 1，是一個根據(jù)上述編碼策略進行編碼的染色體，X3=1表示工序 109分配至 A2；X14=2表示工序 203分配至B3；X32=0表示工序403分配至C1。該個體解碼得到的局部分配方案見表3。

表3 局部設備分配方案

以這種改進的編碼方式，可以得到一個僅有33位的編碼方案，相比傳統(tǒng)二進制編碼方式，使染色體長度縮短至原來的 1/7，避免了編碼串中因無用基因位的占用導致的編碼資源浪費問題，使搜索過程更有效率。

2.2 改進的交叉策略：基于設備類型的多節(jié)點交叉策略

交叉操作是產(chǎn)生新性狀的主要途徑，編碼策略是否可行，取決于該編碼策略對應的交叉操作是否可行，或者是否有基于該編碼策略的可行的交叉策略。在本編碼策略中，由于每一個基因位均有確定的取值范圍，如圖3所示，在設備上分配的工序數(shù)并沒有限制，交叉運算本質(zhì)上是等位基因值的互換，經(jīng)過交叉運算之后，得到的新個體一定滿足約束條件。

例如，有2條染色體：

P1：[101100111 00210110010022 0011101001]

P2：[101000100 10221100110112 1000101011]

由于染色體中X10～23的取值可為 0，1，2，X1～9和X24～33的取值可為0，1，所以，在任意對等位置互換后，依然滿足以上取值條件，得到的新個體依然是可行解。然而，該交叉方法存在交叉不充分的問題：任選一個節(jié)點進行分段交叉，實際上只有一類設備上可能產(chǎn)生新的分配方案，另2類設備的方案未有變化，如：P1和P2在第12個基因位進行交叉，得到：

可以看出，新產(chǎn)生的個體O1和O2中，在A類和C類設備上的分配方案并沒有改變，這使得交叉產(chǎn)生新性狀的效率很低，本研究采用多點交叉，以避免這一問題，即：對3類設備均選擇交叉點，分別在設備類別對應的3個區(qū)間進行交叉運算。具體方法是：分別產(chǎn)生3個[0，1]區(qū)間的隨機數(shù)，將[0，1]分為段數(shù)等于可交叉位置數(shù)量的等步長區(qū)間，在隨機數(shù)出現(xiàn)的區(qū)間對應的位置進行交叉互換，例如：3個隨機數(shù)為0.42，0.78，0.28，第一類設備有8個交叉節(jié)點，0.42∈[3×1/8，4×1/8]，即處于第 4區(qū)間，則將前9位基因在第4個節(jié)點進行截斷交叉；0.78∈[10×1/13, 11×1/13]，則將 10～23 位基因在第11個節(jié)點進行截斷交叉；0.28∈[2×1/9，3×1/9]，則將24～33位基因在第3個節(jié)點進行截斷交叉，得到新的個體：

可以看出，2個新個體在 3類設備的分配上均產(chǎn)生了新性狀，即，產(chǎn)生了3類設備分配方案的新的可行解，從而擴展了搜索空間，提升了搜索效率。

2.3 改進的變異策略：設備類別區(qū)間內(nèi)基因互換

變異策略是否可行，同樣取決于變異后的個體是否可行。由于不同類別的設備數(shù)量可能不同，因此，在不同的基因段，取值范圍也不同，常規(guī)的變異操作可能導致出現(xiàn)不可行解。為避免這一問題，本研究采用設備類別區(qū)間內(nèi)小概率基因互換策略。

首先產(chǎn)生3個[0，1]范圍內(nèi)的隨機數(shù)，第一個隨機數(shù)用于確定選擇哪一個個體進行變異操作；然后將[0，1]分為等步長的33個區(qū)間，采用與交叉策略同樣的方法，確定2個隨機數(shù)分別落在 1～9，10～23，24～33哪個區(qū)間段。如果 2個隨機數(shù)落在同一區(qū)間段，則需對2個基因位的值進行互換，如果落在不同的區(qū)間段，則不進行變異操作。由于變異操作是小概率操作，所以在有的迭代過程中不進行變異操作，并不影響搜索的收斂性。

3 面向工序排序的基于逆向遍歷的蟻群算法

3.1 逆向遍歷形成可行路徑的方法

采用蟻群算法求解工序排序問題，每一個個體即為工序可行路徑。對于主工序圖，每一個螞蟻個體可逆向?qū)⑺泄ば虮闅v一次后再倒序排序，得到一條相應的滿足先后關(guān)系的工序路徑。由于工序有串行、并行和嵌套關(guān)系，所以螞蟻個體在逆向遍歷時會有多種選擇方案，這就形成了初始蟻群。例如：對于圖1中工件1的工序圖，在其中一種路徑選擇完成逆向遍歷：109→107→108→106→103→105→104→102→101，再倒序排序：101→102→104→105→103→106→108→107→109，這就形成了一只螞蟻個體的完整路徑。

3.2 路徑確定的前提下單個螞蟻最優(yōu)解的求解方法

遺傳算法所得到的設備分配方案，作為初始條件傳遞給蟻群算法，通過逆向遍歷再倒序排序的方式，可以確定設備上工序加工的先后順序。只要工序啟動加工的時間，滿足作業(yè)調(diào)度問題的各種約束條件，則其解就是一個可行解，即在設備上的工序分配方案以及加工順序確定的情況下，依然可以得到很多可行解，因此，需要從所有可行解中找出最優(yōu)解，作為螞蟻播灑信息素的依據(jù)。

在逆向遍歷中產(chǎn)生滿足以上條件的眾多加工路徑中，一定可以確定一個使設備利用率最高的最優(yōu)排序，在甘特圖中表現(xiàn)為設備等待時間最短，該排序就是這一加工路徑的最優(yōu)排序。換言之，逆向遍歷產(chǎn)生蟻群，其中每一個個體一定有一個使總完工時間最短的最優(yōu)解，其對應的總完工時間就可以作為此螞蟻路徑上的信息素分配依據(jù)。以工件1為例，如果遺傳算法的設備分配方案是 3類，加工工序分別分配在 A1，A2，B1，B2，B3，C1，C2上，根據(jù) 3.1節(jié)中形成的螞蟻路徑，可以得到設備上分配的工序排序，見表4。并通過調(diào)整工序啟動時間回避工件獨占約束、前序工序約束等約束，得到唯一的最短加工時間的調(diào)度方案，圖4為甘特圖，其最短加工時間為 95，即作為該螞蟻路徑的信息素播灑依據(jù)。

表4 設備上的工序排序

圖4 表4條件下工件1的唯一最短加工時間對應的調(diào)度方案的甘特圖

3.3 信息素播灑與更新策略

信息素分配有多種方法，對任意螞蟻αμ(μ= 1 ,2,… ,?)，有對應的最優(yōu)解(最優(yōu)排序)和與其對應總完工時間cμ，則該螞蟻相應的每段路徑上分配的信息素濃度τμ=1/cμ。因此，單個螞蟻完成對應最優(yōu)路徑全程的時間越短，其每段路徑上分配到的信息素濃度越高，對于2個節(jié)點i和j之間有

其中，為初始蟻群完成第一次遍歷后節(jié)點i與j之間的信息素濃度。當初始蟻群中所有螞蟻都完成了各自對應的路徑，就可以計算出與初始種群對應的各路徑上的信息素濃度。各條路徑上的信息素可更新為

其中，Δτij=；ρ為信息素揮發(fā)系數(shù)；τij(t+1)為更新后的節(jié)點i與j之間的信息素濃度；Δτij為節(jié)點i與j之間的信息素濃度增量。

此時，產(chǎn)生新螞蟻，并根據(jù)信息素濃度來選擇路徑，螞蟻aμ可根據(jù)的大小，確定移動方向

當絕大部分螞蟻都選擇同一條路徑時，即得到了最優(yōu)路徑，輸出對應的最短完工時間，作為個體的適應度傳遞到遺傳算法模塊，從而形成了由遺傳算法與蟻群算法相互嵌套的循環(huán)迭代過程。

4 對比試驗研究

雖然目前有較多關(guān)于作業(yè)車間調(diào)度問題的研究，但研究仍集中于中、小規(guī)模、以串行工序為主的問題[20-21]。對于有一定規(guī)模的存在包括嵌套關(guān)系的調(diào)度問題，研究還較少，目前還沒有公認的標桿問題。在前期的研究中[22]，采用二級嵌套蟻群算法(二級求解均采用蟻群算法)，對包含主要以串聯(lián)關(guān)系組成的19個工序的案例進行了研究，該案例僅包含少量的嵌套工序。本文主要針對規(guī)模更大、關(guān)聯(lián)約束更復雜的情況(包含較多的二級嵌套關(guān)聯(lián)關(guān)系)。圖 1包含 4個工件、33道存在串行、并行、嵌套關(guān)系的工序、3類共7 臺設備(A1，A2，B1，B2，B3，C1，C2)，以圖 1為研究案例，分別采用遺傳算法、蟻群算法、二級嵌套蟻群算法、遺傳算法與蟻群算法相結(jié)合的二級嵌套混合仿生算法，進行對比試驗研究。

單獨采用遺傳算法：

采用遺傳算法求解案例，經(jīng)過20 000次迭代，迭代過程無收斂特征，在迭代中，最優(yōu)解的目標函數(shù)值在245附近，工時利用率僅為30.95%，最優(yōu)解如圖5所示。

(1) 單獨采用蟻群算法。采用蟻群算法進行多次求解試驗，偶爾會出現(xiàn)收斂特征，但出現(xiàn)收斂特征的幾次試驗中，所得到的解有較大差異，說明搜索過程陷入了局部最優(yōu)。設置停機準則：①無收斂特征，則進行20 000次迭代后停機，并輸出迭代中的最優(yōu)解；②有收斂特征，輸出停機時所得到的解。經(jīng)過50次算法試驗，所得到的最優(yōu)解的目標函數(shù)值為 240，工時利用率僅為31.52%，最優(yōu)解如圖6所示。

圖5 單獨采用遺傳算法所得最優(yōu)解的甘特圖

圖6 單獨采用蟻群算法所得最優(yōu)解的甘特圖

(2) 采用二級嵌套蟻群算法[22]求解。迭代1 800次左右，即滿足停機準則，求解有比較高的搜索效率，但優(yōu)化程度較低，如圖7所示。最優(yōu)解的目標函數(shù)值為220，工時利用率僅為34.17%。

(3) 采用遺傳算法與蟻群算法相結(jié)合的二級嵌套混合仿生算法。經(jīng)過約1 000次迭代后，即出現(xiàn)收斂特征，經(jīng)過約5 000次迭代，得到最優(yōu)解，如圖8所示。最優(yōu)方案所對應的總加工時間為155，設備工時利用率為 53.79%，對于復雜調(diào)度問題而言，該工時利用率較高。

表5為4種算法的對比試驗結(jié)果，表明了本文方法的有效性和優(yōu)越性。

圖7 二級嵌套蟻群算法所得最優(yōu)解的甘特圖

圖8 二級嵌套混合算法所得最優(yōu)解的甘特圖

表5 算法對比試驗結(jié)果

5 結(jié) 論

求解包含復雜關(guān)聯(lián)約束的JSSP，目前依然是難點問題，相關(guān)研究成果還比較少。本研究將該難點問題分解為：“設備分配”和“工序排序” 2個相互耦合的子問題，分別發(fā)揮遺傳算法和蟻群算法各自的優(yōu)勢來求解這2個問題，并通過一系列改進策略，構(gòu)造了集成遺傳算法與蟻群算法于一體的二級嵌套混合算法。對于有一定規(guī)模、包含嵌套復雜關(guān)聯(lián)約束的JSSP研究案例，采用二級嵌套混合算法得到的解，工時利用率為53.79%，是一個比較滿意的解，與單獨的遺傳算法、蟻群算法、或二級嵌套蟻群算法相比，有更高的可靠性和優(yōu)化程度。

當然，由于對于包含復雜關(guān)聯(lián)約束的 JSSP的研究還非常少，目前還沒有公認的標桿問題，也沒有公認的較成熟的算法。本文通過理論分析和案例研究表明：針對包含復雜關(guān)聯(lián)約束的JSSP，所提出的方法具有有效性和相對的優(yōu)越性，為該類問題的進一步研究提供了新思路和新方法。