張維存，左天帥，張博涵

（河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401）

0 引言

在Job Shop環(huán)境下，搬運(yùn)設(shè)備的調(diào)度和緩存區(qū)容量的設(shè)置是影響車間調(diào)度優(yōu)化方案的兩個重要因素，將搬運(yùn)設(shè)備和有限緩存區(qū)在Job Shop調(diào)度問題中集成考慮可以減少生產(chǎn)總成本，縮短產(chǎn)品生產(chǎn)周期，提高資源利用率。因此，如何將兩方面同時考慮，將成為本文研究的重點(diǎn)。

近年來，國內(nèi)外很多學(xué)習(xí)者在兩方面分別做了大量研究。在僅考慮搬運(yùn)設(shè)備的情況下，Egbelu［1］等首次提出了在Job Shop環(huán)境下，搬運(yùn)設(shè)備調(diào)度的一些啟發(fā)式規(guī)則。Hurink［2］等將單搬運(yùn)設(shè)備調(diào)度問題看作具有時間窗的旅行推銷員問題，通過禁忌搜索算法解決了 Job Shop排產(chǎn)問題。之后，Hurink［3］等又針對單搬運(yùn)設(shè)備，同時考慮了工件運(yùn)輸時間和空載時間，提出了基于鄰域結(jié)構(gòu)的局部搜索算法。何之洲［4］等同樣僅針對帶單搬運(yùn)設(shè)備的Job Shop調(diào)度問題，提出了一種并行禁忌搜索算法，其優(yōu)點(diǎn)在于調(diào)度任務(wù)中包括了加工工序的排序和搬運(yùn)工序的指派。不同于前人，Deroussi［5］等提出了基于搬運(yùn)設(shè)備而非加工設(shè)備的解決方案，雖有創(chuàng)新但針對對象仍局限于單搬運(yùn)設(shè)備。

區(qū)別于單搬運(yùn)設(shè)備，多個搬運(yùn)設(shè)備的Job Shop問題則不僅需要為各加工工序指派加工設(shè)備，同時還需指派搬運(yùn)設(shè)備。如：Driss［6］等首先應(yīng)用基于鄰域搜索的遺傳算法進(jìn)行搜索，其次使用禁忌搜索算法進(jìn)行工序排序。Lacomme［7］等采用析取圖求解多搬運(yùn)設(shè)備的Job Shop問題。Zheng［8］等提出了針對同時調(diào)度加工設(shè)備和搬運(yùn)設(shè)備的混合整數(shù)線性規(guī)劃模型，該模型由加工設(shè)備調(diào)度和搬運(yùn)設(shè)備調(diào)度子問題組成，采用禁忌搜索算法求解近似最優(yōu)解。Umar［9］等提出使用模糊專家系統(tǒng)控制遺傳算子的混合遺傳算法求解加工和搬運(yùn)調(diào)度問題。此外，孔繼利［10］等研究了加工與搬運(yùn)時間、搬運(yùn)車輛調(diào)度和工件移動方式?jīng)Q策等問題，Bekkar［11］等、Karimi［12］等考慮了加工設(shè)備間的搬運(yùn)時間，采用迭代插入操作精確的解決工序排序問題。也有學(xué)者綜合考慮了多個方面的內(nèi)容，如：搬運(yùn)設(shè)備和搬運(yùn)時間［13］、加工與搬運(yùn)集成調(diào)度［14］。以上研究都是在Job Shop調(diào)度問題基礎(chǔ)上考慮了搬運(yùn)設(shè)備。將搬運(yùn)設(shè)備引入生產(chǎn)系統(tǒng)中，提高生產(chǎn)效率的同時，也產(chǎn)生了更多的瓶頸資源。

另一方面，在Job Shop調(diào)度問題中，僅考慮有限緩存區(qū)的研究也有很多。如：Rer M［15］等研究了在運(yùn)輸約束和加工設(shè)備前后存在緩存區(qū)的條件下Job Shop調(diào)度問題，Escamilla［16］研究了在非瓶頸區(qū)的加工設(shè)備存在有限緩存區(qū)的Job Shop調(diào)度問題，Zhang［17］研究了加工設(shè)備可能存在的輸入/輸出有限緩存區(qū)的Job Shop調(diào)度問題。除此之外，也有學(xué)者對緩存區(qū)容量優(yōu)化問題進(jìn)行了研究。如：王政球［18］等研究了基于生產(chǎn)調(diào)度方案下的緩存區(qū)容量優(yōu)化問題。曹振新［19］等研究了緩存區(qū)容量參數(shù)，搬運(yùn)設(shè)備數(shù)量等性能指標(biāo)。呂潔［20］等考慮面向多個加工任務(wù)同時進(jìn)行加工時瓶頸資源問題，以減少生產(chǎn)波動對瓶頸資源的影響來針對緩沖區(qū)容量問題進(jìn)行研究，以最優(yōu)緩沖區(qū)容量為目標(biāo)建立目標(biāo)函數(shù)模型。陳冠中［21］等對智能制造系統(tǒng)中的緩存區(qū)最大容量進(jìn)行配置優(yōu)化。郭麗［22］等提出了在工件排序方案既定情況下，所優(yōu)化的目標(biāo)值與緩存區(qū)容量增長不成正比。任曉莉［23］等在考慮調(diào)度總時間的同時將庫存容量目標(biāo)進(jìn)行優(yōu)化。

綜上，國內(nèi)外學(xué)者既對考慮單搬運(yùn)設(shè)備和多搬運(yùn)設(shè)備的Job Shop調(diào)度問題進(jìn)行了深入研究，又對Job Shop制造環(huán)境下，緩存區(qū)容量優(yōu)化配置問題進(jìn)行了廣泛研究。然而，作業(yè)車間環(huán)境下同時考慮搬運(yùn)設(shè)備和有限緩存區(qū)的作業(yè)排序優(yōu)化問題卻未得到充分研究。該問題的研究，可以同時提高緩存區(qū)、搬運(yùn)設(shè)備以及加工設(shè)備的資源利用效率，使各類資源進(jìn)行更好的匹配。此外，由于搬運(yùn)設(shè)備數(shù)量和緩存區(qū)容量影響著調(diào)度方案的效率及可行性，該問題較相應(yīng)的JSP更具復(fù)雜性，所需要搜索的解空間更大。為了解決在緩存容量受限的情況下，加工設(shè)備和搬運(yùn)設(shè)備的作業(yè)排序問題，本文以最小化最大完工時間為優(yōu)化目標(biāo)，設(shè)計(jì)了一種帶啟發(fā)式信息的具有角色互換機(jī)制的人工蜂群算法（G-ABC），求解有限緩存區(qū)下Job Shop加工與搬運(yùn)集成調(diào)度問題。

1 考慮有限緩存區(qū)的Job Shop加工與搬運(yùn)集成調(diào)度問題的數(shù)學(xué)模型

1.1 問題描述

帶有限緩存區(qū)的Job Shop加工與搬運(yùn)集成調(diào)度問題可描述為：n個工件｛J1，J2，…，Jn｝在m臺加工設(shè)備M∈｛M1，M2，…，Mm｝上加工，調(diào)度開始前所有工件均在裝載區(qū)M0處，每臺加工設(shè)備Mb（b∈［1，m］）都有一個輸入緩存區(qū)IBb（b∈［1，m］）和一個輸出緩存區(qū)OBb（b∈［1，m］），且所有輸入／輸出緩存區(qū)容量均為K。每個工件Ji包括ni道工序Oij（i∈［1，n］，j∈［1，ni］），每道工序Oij僅對應(yīng)一臺加工設(shè)備Mb。工序Oij作為加工任務(wù)，在加工前需由1臺搬運(yùn)設(shè)備Hc（c∈［1，h］）將工件Ji從上工序Oi（j-1）對應(yīng)的加工設(shè)備Mb′的輸出緩存區(qū)OBb′搬運(yùn)到加工設(shè)備Mb的輸入緩存區(qū)IBb中，工序Oij加工完成后工件Ji進(jìn)入到加工設(shè)備Mb的輸出緩存區(qū)OBb中，等待下次搬運(yùn)和加工。因此，考慮搬運(yùn)環(huán)節(jié)后，工序Oij既是加工任務(wù)也是搬運(yùn)任務(wù)。當(dāng)所有工件｛J1，J2，…，Jn｝都加工完成且被搬運(yùn)到卸載區(qū)Mm+1時，調(diào)度過程結(jié)束。調(diào)度目標(biāo)是求出最大完工時間Cmax最小的調(diào)度方案。

假設(shè)條件：（1）同一時刻一臺加工設(shè)備只能加工一個工件，每個工件在某一時刻只能在一臺加工設(shè)備上加工，且操作不可中斷；（2）同一時刻一臺搬運(yùn)設(shè)備只能搬運(yùn)一個工件，每個工件在某一時刻只能由一臺搬運(yùn)設(shè)備搬運(yùn)，且搬運(yùn)不可中斷；（3）同一工件工序之間有先后約束，不同工件工序之間沒有先后約束，且不同工件具有相同的優(yōu)先級；（4）零時刻，所有工件放在裝載區(qū)M0，所有加工／搬運(yùn)設(shè)備可用；（5）不考慮搬運(yùn)設(shè)備的裝卸時間和工件在加工設(shè)備上的切換時間；（6）所有工件的搬運(yùn)時間只與加工設(shè)備間距離有關(guān)。

1.2 數(shù)學(xué)模型

（1）表示優(yōu)化目標(biāo)為最大完工時間最小化。（2）表示最小化最大完工時間大于等于各工件尾工序搬運(yùn)到卸載區(qū)時的結(jié)束時間。（3）表示工件搬運(yùn)之后需進(jìn)入加工設(shè)備的輸入緩存區(qū)，且不允許工件在搬運(yùn)設(shè)備上等待。（4）表示工件進(jìn)入加工設(shè)備的輸入緩存區(qū)之后才能加工。（5）表示工件加工完成后需進(jìn)入加工設(shè)備的輸出緩存區(qū)。（6）表示工件進(jìn)入加工設(shè)備的輸出緩存區(qū)之后才可搬運(yùn)。（7）表示一個加工設(shè)備一次只能加工一個工件。（8）表示一個搬運(yùn)設(shè)備一次只能搬運(yùn)一個工件。（9）和（10）分別表示同一加工設(shè)備上的兩個工序之間滿足先后順序關(guān)系。（11）和（12）分別表示由同一搬運(yùn)設(shè)備完成的兩個工序之間滿足先后順序關(guān)系。（13）表示一個工件一次只能分配到一臺加工設(shè)備加工。（14）表示一個工件一次只能由一臺搬運(yùn)設(shè)備搬運(yùn)。（15）和（16）分別表示輸入／輸出緩存區(qū)內(nèi)存在的工件數(shù)量不可以超過最大容量。

2 改進(jìn)人工蜂群算法及啟發(fā)式信息設(shè)計(jì)

2.1 算法改進(jìn)設(shè)計(jì)

標(biāo)準(zhǔn)人工蜂群算法將蜜源位置作為可行解，跟隨蜂在引領(lǐng)蜂附近進(jìn)行局部搜索，偵察蜂可以跳出局部最優(yōu)進(jìn)行全局搜索，因此，標(biāo)準(zhǔn)人工蜂群算法在求解問題時存在兩個問題：（1）引領(lǐng)蜂與跟隨蜂之間如何更加高效的進(jìn)行位置共享及種群更新；（2）人工蜂群算法在求解問題時容易陷入局部最優(yōu)解，如何跳出局部最優(yōu)解，更加充分有效地搜索解空間中的可行解。

由于標(biāo)準(zhǔn)人工蜂群算法的不足，本文既要改進(jìn)引領(lǐng)蜂與跟隨蜂的協(xié)作方式，同時也要改進(jìn)跟隨蜂的局部尋優(yōu)方式，使其隨優(yōu)化問題的尋優(yōu)狀態(tài)自適應(yīng)調(diào)整尋優(yōu)方向。改進(jìn)思路：首先，由于引領(lǐng)蜂側(cè)重全局搜索，跟隨蜂側(cè)重局部搜索，故令兩者根據(jù)尋優(yōu)狀態(tài)可互換角色，以便充分且精細(xì)地搜索解空間；其次，以引領(lǐng)蜂位置為中心跟隨蜂進(jìn)行局部搜索，且搜索結(jié)果作為引領(lǐng)蜂尋優(yōu)（覓食）的依據(jù)，指引其更好地全局搜索；最后，跟隨蜂應(yīng)根據(jù)優(yōu)化問題的尋優(yōu)狀態(tài)，既能高效地局部搜索，又能照顧到更大范圍，跳出局部最優(yōu)。

本文問題不同于傳統(tǒng)的JSP，其特殊性在于工序Oij既是加工任務(wù)又是搬運(yùn)任務(wù)，且在此調(diào)度過程中還需考慮是否超出輸入／出緩存區(qū)的容量；其復(fù)雜性在于不僅需要對加工任務(wù)排序，還需為搬運(yùn)任務(wù)分配搬運(yùn)設(shè)備后再對搬運(yùn)任務(wù)排序?；诖藛栴}的特殊性和復(fù)雜性，算法的設(shè)計(jì)思路如圖1所示，具體體現(xiàn)為如下四點(diǎn)：（1）算法采用基于工序的編碼方式（詳見2.2小節(jié)）。（2）基于工序的解碼狀態(tài)，設(shè)計(jì)了工序作為加工任務(wù)或搬運(yùn)任務(wù)被選為可解碼對象的啟發(fā)式信息（詳見2.3小節(jié)）。（3）在解空間中，引領(lǐng)蜂對全局解空間廣泛搜索，跟隨蜂以其引領(lǐng)蜂位置為中心對局部解空間精細(xì)搜索。每只引領(lǐng)蜂和跟隨蜂的位置信息都是一個調(diào)度方案，調(diào)度方案的解碼過程詳見2.4小節(jié)。（4）引領(lǐng)蜂和跟隨蜂可根據(jù)尋優(yōu)的具體情況，判斷引領(lǐng)蜂位置是否更新以及角色是否轉(zhuǎn)換，以便于自適應(yīng)調(diào)整尋優(yōu)方向，直到引領(lǐng)蜂數(shù)量為1時，尋優(yōu)過程結(jié)束，輸出最優(yōu)調(diào)度方案，算法的詳細(xì)改進(jìn)步驟見2.5小節(jié)。

圖1 算法設(shè)計(jì)思路

2.2 編碼設(shè)計(jì)

算法采用基于工序的編碼方式，這種編碼方式的好處在于，便于算法運(yùn)行過程中的進(jìn)化計(jì)算，更好的處理離散組合優(yōu)化問題，進(jìn)而提高搜索效率。個體中的每個基因位代表工序Oij，包含了工件編號i、工序編號j、加工設(shè)備編號b、搬運(yùn)設(shè)備編號c、加工時間、加工優(yōu)先權(quán)值qij、搬運(yùn)優(yōu)先權(quán)值pij等與工序有關(guān)的信息。每一個基因位既包含了加工信息也包含了搬運(yùn)信息，如圖2所示：

圖2 基因編碼設(shè)計(jì)

其中，工件編號i和工序編號j共同作為標(biāo)識來確定基因位Oij。加工開始時間和搬運(yùn)開始時間在解碼過程中得出，加工優(yōu)先權(quán)值qij和搬運(yùn)優(yōu)先權(quán)值pij隨機(jī)賦值，加工優(yōu)先權(quán)值qij作為解碼過程中判斷工序Oij是否優(yōu)先加工的依據(jù)，同樣，搬運(yùn)優(yōu)先權(quán)值pij作為解碼過程中判斷工序Oij是否優(yōu)先搬運(yùn)的依據(jù)。同時，加工優(yōu)先權(quán)值qij和搬運(yùn)優(yōu)先權(quán)值pij也是蜂群操作的對象，個體通過進(jìn)化獲得新的加工、搬運(yùn)優(yōu)先權(quán)值后再次進(jìn)入解碼過程。

2.3 啟發(fā)式信息設(shè)計(jì)

為提高算法運(yùn)行效率，并使最大完工時間最小化，在解碼過程中設(shè)計(jì)了工序Oij進(jìn)入輸入緩存區(qū)時間、加工優(yōu)先權(quán)值qij、工序Oij進(jìn)入輸出緩存區(qū)時間、搬運(yùn)優(yōu)先權(quán)值pij作為可參照的局部啟發(fā)式信息。

（1）工序Oij作為加工任務(wù)被選為解碼對象的依據(jù)是，首先按照公式（17）選擇進(jìn)入輸入緩存區(qū)IBb時間最早的工序，在此基礎(chǔ)上按公式（18）選擇加工優(yōu)先權(quán)值qij最小的工序。

（2）工序Oij作為搬運(yùn)任務(wù)被選為解碼對象的依據(jù)是，首先按照公式（19）選擇進(jìn)入輸出緩存區(qū)OBb時間最早的工序，在此基礎(chǔ)上按公式（20）選擇搬運(yùn)優(yōu)先權(quán)值pij最小的工序。

2.4 解碼過程

解碼過程依據(jù)工序的加工和搬運(yùn)約束條件、加工優(yōu)先權(quán)值qij、搬運(yùn)優(yōu)先權(quán)值pij，在滿足資源約束的條件下，逐步安排各工件工序Oij加工和搬運(yùn)的先后次序，依次得到工序Oij的開始加工時間、開始搬運(yùn)時間、進(jìn)入輸入緩存區(qū)時間、進(jìn)入輸出緩存區(qū)時間、結(jié)束加工時間、結(jié)束搬運(yùn)時間，最終得到加工時間最小的排序方案。

本文研究的問題考慮了裝載區(qū)M0和卸載區(qū)Mm+1，假設(shè)裝載區(qū)M0和卸載區(qū)Mm+1的容量無限大，并將裝載區(qū)M0對應(yīng)的虛擬工序Oi1設(shè)為所有工件的首工序，將卸載區(qū)Mm+1對應(yīng)的虛擬工序設(shè)為所有工件的尾工序。因此，所有工件的首序Oi1不需要加工只需要搬運(yùn)，尾工序既不需要加工也不需要搬運(yùn)。零時刻，所有工件的首工序Oi1可搬運(yùn)，所有搬運(yùn)設(shè)備H和加工設(shè)備M可用，且所有搬運(yùn)設(shè)備H位于裝載區(qū)M0處。

工序Oij作為加工任務(wù)被選為解碼對象，需要滿足四個條件：（1）工序Oij未被加工（2）上工序Oi（j-1）已被解碼；（3）工序Oij已放于對應(yīng)加工設(shè)備Mb的輸入緩存區(qū)IBb中（4）對應(yīng)的加工設(shè)備Mb空閑。滿足以上條件的工序Oij構(gòu)成可解碼加工集合Φ。

工序Oij作為搬運(yùn)任務(wù)被選為解碼對象，需要滿足四個條件：（1）工序Oij已被加工；（2）工序Oij未被搬運(yùn)；（3）工序Oij已放于對應(yīng)加工設(shè)備Mb的輸出緩存區(qū)OBb中；（4）下工序Oi（j+1）對應(yīng)加工設(shè)備Mb′的輸入緩存區(qū)IBb′有空位。滿足以上條件的工序Oij和所有工件的首工序構(gòu)成可解碼搬運(yùn)集合Ω。具體解碼步驟如下：

步驟1逐步遍歷各個工序Oij，依據(jù)上述條件確定可解碼加工集合Φ 和可解碼搬運(yùn)集合Ω。判斷集合Φ 和Ω是否均為空，若均為空，則轉(zhuǎn)入步驟5；否則，轉(zhuǎn)入步驟2。

步驟2首先，依據(jù)啟發(fā)式信息，分別選出作為加工任務(wù)優(yōu)先解碼的工序和作為搬運(yùn)任務(wù)優(yōu)先解碼的工序，再比較工序的加工優(yōu)先權(quán)值qij和工序的搬運(yùn)優(yōu)先權(quán)值pij，選出兩者優(yōu)先權(quán)值中最小的工序Oij作為當(dāng)下唯一解碼對象。若選中加工優(yōu)先權(quán)值qij最小的工序Oij解碼，則令Φ＝Φ-｛Oij｝，并轉(zhuǎn)入步驟3；若選中搬運(yùn)優(yōu)先權(quán)值pij最小的工序Oij解碼，則令Ω ＝Ω-｛Oij｝，并轉(zhuǎn)入步驟4。

步驟3將加工任務(wù)Oij對應(yīng)的工件Ji從輸入緩存區(qū)IBb中取出，令輸入緩存區(qū)IBb的計(jì)數(shù)器ub＝ub-1，根據(jù)公式（21）計(jì)算工序Oij的開始加工時間并判斷此時ub是否為K-1，若ub＝K-1，根據(jù)公式（22）更新輸入緩存區(qū)IBb最早有空位的時間，否則不變。根據(jù)公式（23）計(jì)算工序Oij的結(jié)束加工時間。判斷加工設(shè)備Mb的輸出緩存區(qū)OBb是否有空位，若輸出緩存區(qū)OBb的計(jì)數(shù)器vb＜K，則將工件Ji放入輸出緩存區(qū)OBb，令輸出緩存區(qū)OBb的計(jì)數(shù)器vb＝vb+1，根據(jù)公式（24）更新工序Oij進(jìn)入輸出緩存區(qū)OBb的時間，根據(jù)公式（25）更新加工設(shè)備Mb的最早可用時間；否則，加工設(shè)備Mb被占用，即不變，直到輸出緩存區(qū)OBb有空位，即vb＝K-1時，再根據(jù)公式（28）、公式（29）更新根據(jù)可解碼條件更新可解碼搬運(yùn)集合Ω，轉(zhuǎn)入步驟1。

其中，加工設(shè)備Mb的最早可用時間，根據(jù)緊前先于工序Oij在加工設(shè)備Mb上加工的工序的具體完工情況，選擇公式（2.9）或者公式（2.13）計(jì)算得出。

步驟4將搬運(yùn)任務(wù)Oij對應(yīng)的工件Ji從輸出緩存區(qū)OBb中取出，輸出緩存區(qū)OBb的計(jì)數(shù)器vb＝vb-1，依據(jù)公式（26）計(jì)算可最早到達(dá)輸出緩存區(qū)OBb搬運(yùn)設(shè)備Hc的到達(dá)時間并由搬運(yùn)設(shè)備Hc承擔(dān)此項(xiàng)搬運(yùn)任務(wù)Oij，再根據(jù)公式（27）計(jì)算工序Oij開始搬運(yùn)時間。若此時vb≤K且其加工設(shè)備Mb上有工件Ji′等待進(jìn)入輸出緩存區(qū)OBb，則根據(jù)公式（28）和公式（29）更新該工序Oi′j′進(jìn)入輸出緩存區(qū)OBb的時間和加工設(shè)備Mb的最早可用時間；否則不變。根據(jù)公式（30）計(jì)算工序Oij結(jié)束搬運(yùn)時間，同時更新下工序Oi（j+1）對應(yīng)加工設(shè)備Mb′輸入緩存區(qū)IBb′的計(jì)數(shù)器＝，根據(jù)公式（31）更新工序Oi（j+1）進(jìn)入輸入緩存區(qū)IBb′的時間，根據(jù)公式（32）更新搬運(yùn)設(shè)備Hc的最早可用時間及當(dāng)前位置。根據(jù)可解碼條件更新可解碼加工集合Φ，轉(zhuǎn)入步驟1。

步驟5若集合Φ 和Ω均為空，表示所有工序Oij均已解碼，即解碼過程結(jié)束，根據(jù)公式（1）和（2）計(jì)算最小完工時間，否則，轉(zhuǎn)入步驟1。

2.5 算法步驟

算法運(yùn)行前，只需要設(shè)定唯一的參數(shù)種群規(guī)模N，并令引領(lǐng)蜂規(guī)模Ne和跟隨蜂規(guī)模Nu均為N／2。之后進(jìn)入以下過程：

步驟2初始化蜂群。采用二維蜂群數(shù)組，第一維數(shù)組作為種群規(guī)模，第二維數(shù)組存儲工序節(jié)點(diǎn)。對每個引領(lǐng)蜂個體中工序Oij的加工優(yōu)先權(quán)值qij、搬運(yùn)優(yōu)先權(quán)值pij隨機(jī)賦值。

步驟2對每只引領(lǐng)蜂個體位置進(jìn)行解碼，根據(jù)解碼結(jié)果得出對應(yīng)的目標(biāo)函數(shù)值fe，并由公式（33）計(jì)算出每只引領(lǐng)蜂對應(yīng)的適應(yīng)值fite。

步驟3由公式（34）計(jì)算每只引領(lǐng)蜂可分配跟隨蜂規(guī)模的概率pe，進(jìn)而由公式（35）計(jì)算其跟隨蜂數(shù)量，其中，fite表示每只引領(lǐng)蜂的適應(yīng)值。

步驟4通過對相應(yīng)的跟隨蜂種群尋優(yōu)，更新相應(yīng)的引領(lǐng)蜂適應(yīng)值。具體過程如下：

步驟4.1選定一只引領(lǐng)蜂xe，將位置信息共享給其跟隨蜂，即第e只引領(lǐng)蜂的第u只跟隨蜂按照公式（36）在其周圍搜索更新位置信息。

步驟4.2對跟隨蜂位置進(jìn)行解碼，得出適應(yīng)值fitu，若適應(yīng)值fitu優(yōu)于引領(lǐng)蜂xe的當(dāng)前適應(yīng)值fite，即fitu＞fite，則令fite＝fitu，引領(lǐng)蜂xe位置得到更新；否則，引領(lǐng)蜂xe適應(yīng)值不變。

步驟4.3若u＝，即引領(lǐng)蜂xe的跟隨蜂全部搜索完成，轉(zhuǎn)入步驟4.4；否則，u＝u+1，轉(zhuǎn)入步驟4.1。

步驟4.4若e＝Ne，即引領(lǐng)蜂全部更新完成，轉(zhuǎn)入步驟5；否則，e＝e+1，轉(zhuǎn)入步驟4.1。

步驟5通過引領(lǐng)蜂種群尋優(yōu)進(jìn)化，得出最優(yōu)解，具體過程如下：

步驟5.1Ne只引領(lǐng)蜂的位置以及適應(yīng)值都得到更新后，將所有引領(lǐng)蜂適應(yīng)值進(jìn)行排序，得出最優(yōu)適應(yīng)值f′；

步驟5.2根據(jù)公式（37）、公式（38），將當(dāng)前引領(lǐng)蜂位置與最優(yōu)引領(lǐng)蜂位置進(jìn)行差分計(jì)算，調(diào)整當(dāng)前引領(lǐng)蜂向最優(yōu)引領(lǐng)蜂位置靠近。其中，pij：當(dāng)前引領(lǐng)蜂的搬運(yùn)優(yōu)先權(quán)值：最優(yōu)引領(lǐng)蜂的搬運(yùn)優(yōu)先權(quán)值；qij：當(dāng)前引領(lǐng)蜂的加工優(yōu)先權(quán)值：最優(yōu)引領(lǐng)蜂的加工優(yōu)先權(quán)值。

步驟5.3比較最優(yōu)適應(yīng)值f′與全局最優(yōu)適應(yīng)值f。若f′＞f，將適應(yīng)值最差的引領(lǐng)蜂轉(zhuǎn)化為跟隨蜂，即Ne＝Ne-1，并令Nu＝Nu+1，轉(zhuǎn)入步驟5.4；若f′＜f，令f＝f′，引領(lǐng)蜂、跟隨蜂分別恢復(fù)為原來的規(guī)模Ne＝Nu＝N／2，轉(zhuǎn)入步驟2。

步驟5.4若Ne＝1，則算法結(jié)束，得出最優(yōu)結(jié)果和最優(yōu)調(diào)度方案；否則，轉(zhuǎn)入步驟2。

3 實(shí)驗(yàn)分析

3.1 G-ABC算法主要參數(shù)實(shí)驗(yàn)分析

為提高算法搜索效率，在改進(jìn)人工蜂群算法中加入啟發(fā)式信息，形成帶啟發(fā)式信息的具有角色互換的人工蜂群算法（G-ABC）。在G-ABC中，唯一需要確定的只有種群規(guī)模。因此，在Windows 10 64操作系統(tǒng)，處理器2.5GHz，內(nèi)存8GB的計(jì)算機(jī)上以Visualstudio 2010為實(shí)驗(yàn)環(huán)境，以EX94測例為例，固定緩存區(qū)容量K＝1，搬運(yùn)設(shè)備數(shù)h＝2不變，在不同種群規(guī)模N（N＝“50”，“100”，“150”，…，1000）下進(jìn)行求解，每一種群規(guī)模均運(yùn)行20次計(jì)算最優(yōu)均值，得出不同種群規(guī)模N下最優(yōu)均值及最優(yōu)值的方差，并繪制出隨種群規(guī)模N變化的最優(yōu)均值變化圖及方差變化圖。

圖3 最優(yōu)均值變化

圖4 方差變化過程

從圖3可知，種群規(guī)模N達(dá)到900時，G-ABC求解出的最優(yōu)均值曲線趨于平緩，說明當(dāng)種群規(guī)模N達(dá)到900時，G-ABC算法的尋優(yōu)能力接近最大極限；從圖4可知，種群規(guī)模N達(dá)到850時，算法每次運(yùn)行的結(jié)果趨于穩(wěn)定。結(jié)合圖3、圖4可知，種群規(guī)模建議設(shè)置在900～1000之間較為合理。

3.2 G-ABC算法有效性實(shí)驗(yàn)分析

為驗(yàn)證G-ABC算法的尋優(yōu)能力，引入Bilige等人［24］提出的40個標(biāo)準(zhǔn)EX測例，每個EX測例由工件加工要求（Jobset）和車間布局（layout）兩部分組成。例如，測例“EX23”，2表示Jobset 2，3表示layout3。表1中，MAS列表示文獻(xiàn)［25］在緩存區(qū)容量無限、搬運(yùn)設(shè)備為2的情況下，提出的算法運(yùn)行結(jié)果；GAHA表示文獻(xiàn)［26］在緩存區(qū)容量無限、搬運(yùn)設(shè)備為2的情況下，提出的算法運(yùn)行結(jié)果。本文考慮了緩存區(qū)容量限制條件，所以將G-ABC算法種群規(guī)模N設(shè)為1000，搬運(yùn)設(shè)備數(shù)量h設(shè)為2，分別將緩存區(qū)容量K設(shè)為1，2，3，每種情況均運(yùn)行20次，取最優(yōu)值記入A列、B列、C列。GAP1列表示G-ABC算法和文獻(xiàn)［25］中MAS的差值比，計(jì)算方式：GAP1＝（MAS-C）/MAS*100%，若GAP1＞0，說明G-ABC優(yōu)于文獻(xiàn)［25］的MAS運(yùn)行結(jié)果。GAP2列表示G-ABC算法和文獻(xiàn)［26］中GAHA運(yùn)行結(jié)果的差值比，計(jì)算方式：GAP2＝（GAHA-C）/GAHA*100%，若GAP2＞0，說明G-ABC算法優(yōu)于文獻(xiàn)［26］的GAHA運(yùn)行結(jié)果。

表2中結(jié)果的得出方法與表1相同，不同之處在于搬運(yùn)設(shè)備數(shù)量h設(shè)為3，其中，GAHA3列表示文獻(xiàn)［26］中GAHA3的運(yùn)行結(jié)果，GAP3的計(jì)算方式：GAP3＝（GAHA3-D）/GAHA3*100%，若GAP3＞0，說明G-ABC優(yōu)于文獻(xiàn)［26］的GAHA3的運(yùn)行結(jié)果。

表1 實(shí)驗(yàn)及對比結(jié)果（h=2）

從表1中的數(shù)據(jù)可知，G-ABC算法90%的運(yùn)行結(jié)果優(yōu)于MAS的最優(yōu)解，最大差值比為32.9%，平均差值比為13.54%，G-ABC算法92.5%的運(yùn)行結(jié)果不差于GAHA 的最優(yōu)解，最大差值比為11.18%，平均差值比為4.43%，可見G-ABC算法的尋優(yōu)能力更強(qiáng)，優(yōu)于MAS和GAHA的尋優(yōu)能力。

表2 實(shí)驗(yàn)及對比結(jié)果（h=3）

從表2中的數(shù)據(jù)可知，G-ABC算法100%的運(yùn)行結(jié)果不差于GAHA3的最優(yōu)解，85%的運(yùn)行結(jié)果優(yōu)于GAHA3的最優(yōu)解，由此進(jìn)一步說明了G-ABC算法的有效性。綜合表1和表2的運(yùn)行結(jié)果，分析其產(chǎn)生原因如下：

（1）G-ABC算法在選擇搬運(yùn)設(shè)備時，選擇最早可到達(dá)的搬運(yùn)設(shè)備，這有利于已加工完成的工件盡早被搬運(yùn)，緩存區(qū)和加工設(shè)備盡早可用，提高了加工與搬運(yùn)效率。

（2）啟發(fā)式信息的設(shè)計(jì)，避免了G-ABC算法在增加輸入/輸出緩存區(qū)容量時，因解空間的擴(kuò)大導(dǎo)致算法在解碼過程中盲目搜索而降低運(yùn)行效率的問題。

（3）采用角色互換機(jī)制的人工蜂群算法，在搜索過程中，將當(dāng)前搜索結(jié)果最差的引領(lǐng)蜂轉(zhuǎn)換為跟隨蜂，加強(qiáng)了局部搜索能力。當(dāng)有優(yōu)于當(dāng)前全局最優(yōu)的結(jié)果出現(xiàn)時，恢復(fù)初始引領(lǐng)蜂的設(shè)置數(shù)量，可避免陷入局部最優(yōu)。這不僅克服了標(biāo)準(zhǔn)人工蜂群算法中參數(shù)設(shè)置過多和搜索效果差的問題，而且兼顧了全局廣泛尋優(yōu)和局部精確尋優(yōu)。

3.3 緩存區(qū)靈敏度分析

從表1和表2中，不難發(fā)現(xiàn)，部分測例隨著緩存區(qū)容量增大，最優(yōu)值減小。以EX74測例為例，為了排除種群規(guī)模N設(shè)置過小，而導(dǎo)致未能全局充分搜索的影響，進(jìn)一步將種群規(guī)模N 增大為5000，重復(fù)表2的實(shí)驗(yàn)過程，發(fā)現(xiàn)EX74測例的運(yùn)行結(jié)果仍為表2中所示，并以此繪制出如圖5所示的隨緩存區(qū)容量K變化的最優(yōu)值變化圖。

圖5 不同K值下的最優(yōu)值變化

從圖5中可以看出，隨著緩存區(qū)容量的增大，最優(yōu)值在逐步減小，在緩存區(qū)容量為從1逐漸變?yōu)?的過程中，最優(yōu)值在逐漸減小，當(dāng)緩存區(qū)容量設(shè)為4和5時最優(yōu)值不再減小。這說明緩存區(qū)容量在一定范圍內(nèi)影響調(diào)度過程，當(dāng)緩存區(qū)容量達(dá)到一定數(shù)量時，不再是調(diào)度過程的制約因素。對于工序數(shù)量多的測例，緩存區(qū)的容量在調(diào)度過程中的影響更為明顯。

3.4 啟發(fā)式信息有效性分析

為驗(yàn)證啟發(fā)式信息的有效性，設(shè)計(jì)了去掉啟發(fā)式信息的具有角色互換的人工蜂群算法（P-ABC）。以EX14等5個測例為例，將搬運(yùn)設(shè)備設(shè)置h＝2，緩存區(qū)設(shè)置h＝1，每組測例運(yùn)行20次，取其結(jié)果平均值，比較P-ABC和G-ABC的運(yùn)行結(jié)果。算法運(yùn)行環(huán)境參照3.1節(jié)，種群規(guī)模N均為1000，運(yùn)行結(jié)果見表3。其中，A列和B列分別表示P-ABC和G-ABC20次運(yùn)行結(jié)果的平均值；GAP4列表示P-ABC和G-ABC的差值比，計(jì)算方式：GAP4＝（A-B）/A*100%，若GAP4＞0，說明G-ABC優(yōu)于P-ABC。

表3 啟發(fā)式信息對運(yùn)行結(jié)果影響對比

從表3中可以看出，5個測例的差值比最大為1.65%，最小為0.43%，平均差值比為1.04%，說明G-ABC的平均運(yùn)行結(jié)果優(yōu)于P-ABC，即說明了啟發(fā)式信息的有效性。

4 結(jié)束語

考慮有限緩存區(qū)的Job Shop加工與搬運(yùn)集成調(diào)度問題是對傳統(tǒng)作業(yè)車間調(diào)度問題（JSP）的擴(kuò)充，更是對僅考慮搬運(yùn)設(shè)備和僅考慮有限緩存區(qū)JSP的完善，并且更具復(fù)雜性和實(shí)踐應(yīng)用性。本文的研究表明：

（1）采用角色互換的人工蜂群算法，克服了標(biāo)準(zhǔn)人工蜂群算法中參數(shù)設(shè)置過多和搜索效果差的問題，引入引領(lǐng)蜂和跟隨蜂角色互換機(jī)制可以更好的兼顧全局廣泛搜索和局部精確搜索。

（2）在一定范圍內(nèi)，緩存區(qū)容量設(shè)置在調(diào)度過程中會影響調(diào)度結(jié)果，尤其對于工序數(shù)多的測例影響更為明顯。

（3）在緩存區(qū)容量一定的條件下，如何優(yōu)先解碼加工任務(wù)和搬運(yùn)任務(wù)是優(yōu)化該問題的關(guān)鍵。而針對此設(shè)計(jì)的啟發(fā)式信息，可以提高算法的尋優(yōu)效率。

（4）通過仿真實(shí)驗(yàn)，算法參數(shù)取值具有一定范圍。進(jìn)一步，通過與其他算法比較，驗(yàn)證了該算法有較好的求解能力。

這類問題的解決能夠?yàn)槠髽I(yè)提供更多靈活實(shí)用的調(diào)度方案，進(jìn)而提高企業(yè)生產(chǎn)力。