考慮有限緩存區(qū)的Job Shop加工與搬運集成調度

張維存，左天帥，張博涵

（河北工業(yè)大學 經濟管理學院，天津 300401）

0 引言

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

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

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

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

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

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

1.1 問題描述

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

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

1.2 數(shù)學模型

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

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

2.1 算法改進設計

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

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

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

圖1 算法設計思路

2.2 編碼設計

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

圖2 基因編碼設計

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

2.3 啟發(fā)式信息設計

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

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

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

2.4 解碼過程

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

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

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

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

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

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

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

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

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

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

2.5 算法步驟

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

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

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

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

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

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

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

步驟4.3若u＝，即引領蜂xe的跟隨蜂全部搜索完成，轉入步驟4.4；否則，u＝u+1，轉入步驟4.1。

步驟4.4若e＝Ne，即引領蜂全部更新完成，轉入步驟5；否則，e＝e+1，轉入步驟4.1。

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

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

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

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

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

3 實驗分析

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

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

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

圖4 方差變化過程

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

3.2 G-ABC算法有效性實驗分析

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

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

表1 實驗及對比結果（h=2）

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

表2 實驗及對比結果（h=3）

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

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

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

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

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

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

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

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

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

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

表3 啟發(fā)式信息對運行結果影響對比

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

4 結束語

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

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

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

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

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

這類問題的解決能夠為企業(yè)提供更多靈活實用的調度方案，進而提高企業(yè)生產力。