羅亞波， 余晗琳

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

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

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

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

1 二級(jí)嵌套模型及其基本思路

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

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

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

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

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

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

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

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

一級(jí)：設(shè)備分配

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

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臺(tái)設(shè)備后道工序啟動(dòng)時(shí)間；Bj為第j臺(tái)設(shè)備啟動(dòng)時(shí)間；Tj為第j臺(tái)設(shè)備從啟動(dòng)到關(guān)停的時(shí)間；Ei為第i項(xiàng)工序的設(shè)備分配方案；Ri為第i項(xiàng)工序所需的設(shè)備類型；BE(i+1)j為第j臺(tái)設(shè)備上排列的第i+1項(xiàng)工序的開(kāi)始時(shí)間；BEij為第j臺(tái)設(shè)備上排列的第i項(xiàng)工序的開(kāi)始時(shí)間；SEij為第j臺(tái)設(shè)備上排列的第i項(xiàng)工序的標(biāo)準(zhǔn)工時(shí)。

二級(jí)：工序排序

求Pn(Pn表示各工序在所分配設(shè)備上的排序)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各設(shè)備分配方案的完工時(shí)間；BEnj為在En各設(shè)備分配方案中的第j臺(tái)設(shè)備啟動(dòng)時(shí)間；TEnj為在En各設(shè)備分配方案中第j臺(tái)設(shè)備從啟動(dòng)到關(guān)停的時(shí)間；Bik為第i項(xiàng)工序的第k項(xiàng)前序工序的開(kāi)始時(shí)間；Bi為第i項(xiàng)工序的開(kāi)始啟動(dòng)時(shí)間；Sik為第i項(xiàng)工序的第k項(xiàng)前道工序的標(biāo)準(zhǔn)工時(shí)；BE(i+1)j為第j臺(tái)設(shè)備上排列的第i+1項(xiàng)工序的開(kāi)始時(shí)間；BEij為第j臺(tái)設(shè)備上排列的第i項(xiàng)工序的開(kāi)始時(shí)間；SEij為第j臺(tái)設(shè)備上排列的第i項(xiàng)工序的標(biāo)準(zhǔn)工時(shí)；Bi(qr)為第q個(gè)工件的第r項(xiàng)工序的開(kāi)始時(shí)間；Si(qr)為第q個(gè)工件的第r項(xiàng)工序的標(biāo)準(zhǔn)工時(shí)；Bi(q(r+u))為q個(gè)工件的第r+u項(xiàng)工序的開(kāi)始時(shí)間。

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

圖2 二級(jí)嵌套混合算法流程圖

2 面向設(shè)備分配的改進(jìn)遺傳算法

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

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

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

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

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

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

表2 設(shè)備工序集

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

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，是一個(gè)根據(jù)上述編碼策略進(jìn)行編碼的染色體，X3=1表示工序 109分配至 A2；X14=2表示工序 203分配至B3；X32=0表示工序403分配至C1。該個(gè)體解碼得到的局部分配方案見(jiàn)表3。

表3 局部設(shè)備分配方案

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

2.2 改進(jìn)的交叉策略：基于設(shè)備類型的多節(jié)點(diǎn)交叉策略

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

例如，有2條染色體：

P1：[101100111 00210110010022 0011101001]

P2：[101000100 10221100110112 1000101011]

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

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

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

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

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

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

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

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

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

3.2 路徑確定的前提下單個(gè)螞蟻?zhàn)顑?yōu)解的求解方法

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

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

表4 設(shè)備上的工序排序

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

3.3 信息素播灑與更新策略

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

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

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

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

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

4 對(duì)比試驗(yàn)研究

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

單獨(dú)采用遺傳算法：

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

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

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

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

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

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

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

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

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

表5 算法對(duì)比試驗(yàn)結(jié)果

5 結(jié) 論

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

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