李佳路，*王 雷，王靜云

改進(jìn)遺傳蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題

李佳路，*王 雷，王靜云

（安徽工程大學(xué)機(jī)械工程學(xué)院，安徽，蕪湖 241000）

針對分布式柔性作業(yè)車間調(diào)度問題，提出一種改進(jìn)遺傳蜂群算法求解方案。算法采用基于機(jī)器編碼的編碼方案，根據(jù)編碼特點(diǎn)和分布式柔性作業(yè)車間的特點(diǎn)，設(shè)計了一種基于編碼相似度的交叉操作，可以避免在交叉過程中產(chǎn)生非法解，提高算法的運(yùn)行效率，并通過在不同的交叉操作后，以不同概率進(jìn)行兩種變異操作的方式改進(jìn)了雇傭蜂時期的搜索操作，改善了算法的迭代速度；采用排序選擇策略替代原來跟隨蜂時期的選擇策略；改進(jìn)偵查蜂的蜜源拋棄機(jī)制，通過對比已獲得的全局最優(yōu)解，對達(dá)到搜索上限的蜜源進(jìn)行部分拋棄，防止破壞優(yōu)質(zhì)解再次陷入隨機(jī)搜索。最后，通過對比不同算法對實例求解，驗證本文算法的有效性。

分布式調(diào)度；柔性作業(yè)車間；人工蜂群算法；遺傳算法

在經(jīng)濟(jì)全球化的背景下，傳統(tǒng)制造業(yè)受到了極大地沖擊，并且隨著企業(yè)規(guī)模的擴(kuò)大，企業(yè)生產(chǎn)制造模式逐漸由單工廠生產(chǎn)轉(zhuǎn)變?yōu)槎喙S生產(chǎn)，以提高競爭力[1]。分布式車間調(diào)度既需要考慮每個車間內(nèi)的工序調(diào)度還需要考慮多個車間的協(xié)作生產(chǎn)，是比單車間調(diào)度更加復(fù)雜的NP-hard問題，在這種多工廠生產(chǎn)模式下的調(diào)度問題也受到更多的學(xué)者關(guān)注與研究[2]。分布式柔性作業(yè)車間調(diào)度問題作為柔性作業(yè)車間調(diào)度問題的延伸，其中每一個工廠都可以看作是一個獨(dú)立的柔性作業(yè)車間，多個工廠可以根據(jù)實際的加工能力和資源配置協(xié)作完成一批加工任務(wù)，生產(chǎn)調(diào)度更加靈活，也更加符合當(dāng)前的生產(chǎn)模式[3]。

目前，分布式車間調(diào)度研究大部分集中在各類分布式流水車間調(diào)度[4-7]，而分布式柔性作業(yè)車間調(diào)度問題研究則相對較少。Felix T.S. Chan等[8]和L.De Giovanni等[9]采用遺傳算法對分布式柔性作業(yè)車間調(diào)度問題進(jìn)行了研究；楊江波等[10]根據(jù)車間實際生產(chǎn)過程，將生產(chǎn)調(diào)度過程劃分為生產(chǎn)計劃層、車間調(diào)度層和零件規(guī)劃層，提出一種基于目標(biāo)級聯(lián)法和遺傳算法的分級調(diào)度模型；Chang H C等[11]提出了一種混合遺傳算法，該算法采用了一種新的編碼機(jī)制和一些有效的交叉和變異算子提高搜索效率；Bilel Marzouki等[12]提出了一種化學(xué)反應(yīng)優(yōu)化的元啟發(fā)式算法來解決分布式柔性作業(yè)車間調(diào)度問題；Lu P H等[13]設(shè)計了一種具有一維到三維解碼方案的遺傳算法求解分布式柔性作業(yè)車間調(diào)度問題；吳銳等[14]根據(jù)問題特性設(shè)計了基于關(guān)鍵路徑思想的局部搜索算子；Meng L L等[15]為解決最大完工時間最小的分布式柔性作業(yè)車間調(diào)度問題，提出了四個基于不同建模思想的混合整數(shù)線性規(guī)劃(MILP)模型和一個基于區(qū)間決策變量和區(qū)域過濾算法的約束規(guī)劃(CP)模型。

綜上，分布式柔性作業(yè)車間調(diào)度問題是近年發(fā)展起來的更加符合生產(chǎn)實際的問題，但目前對其求解方法偏少，且已有研究大部分都采用遺傳算法求解，遺傳算法存在收斂慢和容易陷入局部最優(yōu)的缺點(diǎn)，在求解大規(guī)模問題時不具有優(yōu)勢；分布式柔性作業(yè)車間調(diào)度問題求解更為復(fù)雜，現(xiàn)有研究少有針對問題特點(diǎn)設(shè)計相應(yīng)編碼和進(jìn)化操作，導(dǎo)致編碼量大且易在進(jìn)化迭代時產(chǎn)生非法解，降低算法效率。人工蜂群算法（Artificial bee colony algorithm, ABC）于2005年由Karaboga[16]提出，是模擬自然界蜂群采蜜的行為的一種群體智能優(yōu)化算法，具有結(jié)構(gòu)簡單、參數(shù)較少、易于實現(xiàn)等特點(diǎn)，廣泛的應(yīng)用于生產(chǎn)調(diào)度領(lǐng)域[17-19]。因此，本研究利用人工蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題，并改進(jìn)算法的進(jìn)化搜索機(jī)制，提高其對分布式柔性作業(yè)車間調(diào)度問題的求解性能。

1 分布式柔性作業(yè)車間調(diào)度問題

1.1 符號定義

在對分布式柔性作業(yè)車間調(diào)度問題進(jìn)行描述前，先對本文所涉及相關(guān)符號說明如下：

表1 符號定義

1.2 問題描述

分布式柔性作業(yè)車間調(diào)度問題是多工廠調(diào)度問題，每個子工廠都可作為一個柔性作業(yè)車間對整個加工任務(wù)中的部分工件進(jìn)行加工，因此分布式柔性作業(yè)車間調(diào)度問題包含3個子問題：1）為待加工工件分配加工工廠；2）為每道工序分配加工機(jī)器；3）對每個工廠進(jìn)行工序調(diào)度。

1.3 建立問題模型

更快捷地完成生產(chǎn)任務(wù)是提升企業(yè)效益的有效途徑，因此本文以最小化最大完工時間為生產(chǎn)調(diào)度的優(yōu)化目標(biāo)，并以此建立調(diào)度優(yōu)化模型：

（1） （2） （3） （4） （5） （6） （7）

其中，式（1）是目標(biāo)函數(shù)，表示最大完工時間是所有工廠完工的最大值；式（2）表示工廠的完工時間是工廠內(nèi)加工的最后一道工序的結(jié)束時間；式（3）限制一個工件只能分配到一個工廠內(nèi)加工；式（4）為工序約束，表示同一工件的工序必須按照順序加工；式（5）為機(jī)器約束，保證同一機(jī)器同一時間只能加工一道工序；式（6）表示一道工序只能選擇一個機(jī)器進(jìn)行加工；式（7）表示工序開始后不能中斷。

2 改進(jìn)遺傳蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題

2.1 改進(jìn)遺傳蜂群算法流程

在標(biāo)準(zhǔn)的人工蜂群算法中，包括3種類型的蜜蜂：雇傭蜂、跟隨蜂和偵查蜂，蜜源代表問題的可行解，蜜源質(zhì)量為可行解的適應(yīng)度，其中每個蜜源對應(yīng)一個雇傭蜂，跟隨蜂數(shù)量與雇傭蜂數(shù)量相等，偵查蜂由蜜源搜索達(dá)到限制條件的雇傭蜂生成[20]。但標(biāo)準(zhǔn)人工蜂群算法只能對連續(xù)型問題進(jìn)行求解，無法對車間調(diào)度類等離散型問題進(jìn)行求解。故我們根據(jù)遺傳算法中染色體交叉變異的方法，對人工蜂群算法做離散化改進(jìn)，使其適用于求解分布式柔性作業(yè)車間調(diào)度問題，并通過設(shè)計多種蜜源初始化策略、改進(jìn)雇傭蜂交叉變異的搜索策略、跟隨蜂的選擇策略和偵查蜂的蜜源拋棄策略以提高算法求解性能。提改進(jìn)遺傳蜂群算法整體流程如圖1所示。

圖1 改進(jìn)遺傳蜂群算法整體流程圖

2.2 編碼和解碼

目前現(xiàn)有求解分布式柔性作業(yè)車間調(diào)度問題的相關(guān)文獻(xiàn)，在對問題編碼大多都采用基于工序的編碼、基于機(jī)器的編碼和選擇的工廠編碼的三層編碼方式[3,13-14]，在實際的分布式柔性作業(yè)車間調(diào)度問題中，加工規(guī)模都比較大，采用這種編碼方式往往面臨兩個問題：一是編碼量大，二是在交叉變異時極易產(chǎn)生非法解，影響算法的求解效率。因此，本文設(shè)計一種基于機(jī)器編碼的編碼方案，并根據(jù)編碼特點(diǎn)設(shè)計相應(yīng)的交叉變異操作，可以保證在不需要修補(bǔ)或重建的情況下，產(chǎn)生的新解為可行解，提高算法運(yùn)行效率。

圖2 編碼示意

此基于機(jī)器的編碼僅為待加工工件分配加工廠和為工序選擇加工機(jī)器，并沒有產(chǎn)生調(diào)度方案，需要對其進(jìn)行解碼來獲得調(diào)度方案。對上述編碼方案進(jìn)行解碼，根據(jù)分布式柔性作業(yè)車間調(diào)度問題的特性，解碼主要包括兩個部分，首先對可行解編碼進(jìn)行以加工工廠為單位的分解，然后分別對子碼進(jìn)行解碼。以圖2示例編碼為例，具體解碼過程如下：

1）編碼分解；根據(jù)編碼首列的加工工廠代碼，對編碼進(jìn)行分解，將主體編碼分解為以加工工廠為單位的子碼，同時也將對應(yīng)加工時間矩陣進(jìn)行相應(yīng)的分解，如圖3所示。

圖3 編碼分解示意圖

2）分別對子碼進(jìn)行解碼；按本文編碼方式，并未給出不同工件工序的加工順序，根據(jù)本文編碼方式設(shè)計一種基于剩余加工時間最長的MWKR法則和最早進(jìn)入最先加工的FCFS法則解碼方案，提高調(diào)度方案質(zhì)量。具體操作為：對同一工廠所有工件的每一道工序進(jìn)行調(diào)度，對于所有工件的同一道工序，若不同的工件都在不同的機(jī)器上加工，先判斷對應(yīng)機(jī)器上的加工空閑是否能將該道工序插入，若能，則插入；否則安排到之前機(jī)器加工的最后一道工序字后。若有工件在同一機(jī)器上加工，先對機(jī)器空閑進(jìn)行判斷，將可以進(jìn)行插入的工序插入；若都可以插入但又不能同時插入時，將加工時間長的工序優(yōu)先插入，以縮短機(jī)器空閑時間，提高加工效率；若不發(fā)生插入，則以MWKR法則優(yōu)先安排剩余加工時間最長的工件進(jìn)行加工，否則以FCFS法則進(jìn)行調(diào)度。

通過采用上述解碼方案對圖2的編碼進(jìn)行解碼，得到調(diào)度甘特圖如圖4所示。

圖4 調(diào)度甘特圖

2.3 蜂群初始化

在啟發(fā)式算法中，初始種群的質(zhì)量對算法收斂速度和求解結(jié)果有很大影響，一個高質(zhì)量的初始種群在算法求解中非常關(guān)鍵。本設(shè)計的種群初始化方法，在為工件選擇加工工廠時采用均衡原則，即加工機(jī)器多的工廠被選擇的概率大，以均衡各個工廠的負(fù)載。確定工件的加工工廠后，每個工廠中工件的工序選擇加工機(jī)器時按照以下策略生成：

1）隨機(jī)選擇加工機(jī)器，占初始種群的70%；

2）優(yōu)先選擇加工任務(wù)少的機(jī)器，當(dāng)存在多選時，在同級別內(nèi)進(jìn)行隨機(jī)選擇，占初始種群的20%；

3）按局部處理時間最小規(guī)則選擇，占初始種群的10%。

2.4 雇傭蜂搜索操作

由本文編碼方式和分布式柔性作業(yè)車間調(diào)度問題特性可知，在兩個父代發(fā)生交叉時，若交叉位置處兩個工件處于不同的加工工廠，由于不同工廠中進(jìn)行工序加工的可行機(jī)器和能力不同，此時交叉的意義不大，且極易產(chǎn)生非法解。因此本文根據(jù)編碼特點(diǎn)，設(shè)計一種交叉操作，可以避免非法解的產(chǎn)生；并且根據(jù)分布式柔性作業(yè)車間的特點(diǎn)設(shè)計了變異操作。

在交叉操作之前，首先引入編碼相似度，的計算方法如下：對比編碼中每個工件加工工廠代碼，若兩個編碼中同一工件的加工工廠相同，則為1，不同為0，對其求和即為。

交叉操作為隨機(jī)多點(diǎn)交叉，交叉父代之一為當(dāng)前蜜源，另一個父代在其他蜜源中隨機(jī)選取2個蜜源，以70%的概率選擇相似度高的蜜源作為交叉父代；以30%的概率，選擇另一個蜜源作為交叉父代。交叉的具體操作為：首先對比兩個父代第一件工件的加工工廠代碼，若加工工廠相同，則產(chǎn)生隨機(jī)位置，將兩個父代第一個工件的子代碼片段進(jìn)行互換；若加工工廠不同，第一個工件子代碼則不發(fā)生交叉操作。后續(xù)工件子代碼交叉操作以此類推；對兩個子代進(jìn)行貪婪選擇，較優(yōu)的作為交叉后的新蜜源。

變異操作設(shè)置兩種形式：

1）工序加工機(jī)器變異：隨機(jī)產(chǎn)生編碼矩陣位置（不包括加工工廠代碼列），在當(dāng)前位置隨機(jī)選擇一個可選機(jī)器進(jìn)行替換。此種變異方式產(chǎn)生新蜜源與原蜜源差異較小。

2）工件加工工廠變異：選擇當(dāng)前蜜源下的隨機(jī)一個工件進(jìn)行加工工廠替換變異，即將當(dāng)前工件所在加工工廠變換為另一個不同的可選工廠，由于工件在不同工廠中可用加工機(jī)器不同，當(dāng)發(fā)生工廠變異時，需要重新選擇加工機(jī)器。此種變異方式變異范圍更大，鄰域搜索范圍更大。

由于選擇交叉父代相似度的大小影響交叉時鄰域搜索范圍，在交叉產(chǎn)生的新蜜源不優(yōu)于原蜜源時，根據(jù)交叉父代的相似度大小，采用不同的變異操作。

雇傭蜂搜索操作具體流程如圖5所示，具體步驟如下：

圖5 雇傭蜂搜索操作流程

步驟1：取當(dāng)前位置蜜源作為交叉父代之一；

步驟2：隨機(jī)選取兩個不同于蜜源的蜜源1和2，并分別計算相似度1和2；

步驟3：判斷所選兩蜜源相似度1和2是否相等，不相等轉(zhuǎn)步驟6；

步驟4：隨機(jī)選取兩蜜源之一作為父代與蜜源X進(jìn)行交叉，選擇生成兩個子代適度值大的作為新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；

現(xiàn)有的小區(qū)治理結(jié)構(gòu)中存在著業(yè)主自治、居民自治和政府管理三種形式，但這些治理形式的邊界如何確定，不同物業(yè)類型的小區(qū)治理結(jié)構(gòu)又有著何種差異，是困擾當(dāng)前小區(qū)內(nèi)部治理的關(guān)鍵性難題。

步驟5：隨機(jī)采用加工工廠變異或加工機(jī)器變異方式產(chǎn)生新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；若不優(yōu)于，轉(zhuǎn)步驟12；

步驟6：產(chǎn)生隨機(jī)值，若0.7，進(jìn)行步驟7；否則轉(zhuǎn)步驟9；

步驟7：選擇兩蜜源中相似度大的蜜源作為父代與蜜源進(jìn)行交叉，選擇生成兩個子代適度值大的作為新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；

步驟8：產(chǎn)生隨機(jī)數(shù)，若<0.2，對蜜源進(jìn)行加工工廠變異；否則進(jìn)行加工機(jī)器變異，并產(chǎn)生新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；若不優(yōu)于，轉(zhuǎn)步驟12；

步驟9：選擇兩蜜源中相似度小的蜜源作為父代與蜜源進(jìn)行交叉，選擇生成兩個子代適度值大的作為新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；

步驟10：產(chǎn)生隨機(jī)數(shù)，若0.2，對蜜源進(jìn)行加工工廠變異；否則進(jìn)行加工機(jī)器變異，并產(chǎn)生新蜜源，若優(yōu)于，轉(zhuǎn)步驟11；若不優(yōu)于，轉(zhuǎn)步驟12；

步驟11：用新蜜源代替當(dāng)前蜜源，雇傭蜂結(jié)束對當(dāng)前蜜源搜索；

步驟12：當(dāng)前蜜源保持不變，蜜源搜索限制加1，雇傭蜂結(jié)束對當(dāng)前蜜源搜索。

2.5 跟隨蜂搜索操作

式中為雇傭蜂個數(shù)，(t)為自適應(yīng)參數(shù)，為當(dāng)前迭代次數(shù)，max為最大迭代次數(shù)。通過該選擇策略，在迭代初期，(t)較小，可以有效保持種群多樣性；隨迭代次數(shù)增加，(t)可以防止由于種群競爭減弱而出現(xiàn)搜尋停滯的趨勢。在確定跟隨的雇傭蜂后，將兩個個體進(jìn)行交叉并進(jìn)行貪婪選擇，若蜜源未更新，則蜜源搜索限制。

2.6 偵查蜂搜索操作

基本人工蜂群算法中，若蜜源搜索限制達(dá)到上限，則雇傭蜂放棄該蜜源，轉(zhuǎn)化為偵查蜂進(jìn)行隨機(jī)搜索，產(chǎn)生一個新蜜源，通過該操作使算法在一定程度上跳出局部最優(yōu)，但由于算法收斂性，若該解恰好為全局最優(yōu)解，拋棄該解會導(dǎo)致算法重新搜索最優(yōu)解，降低搜索效率。故本文提出以下改進(jìn)方法：

1）記錄當(dāng)前全局最優(yōu)蜜源；

2）搜索所有蜜源搜索次數(shù)達(dá)到上限的蜜源；

3）如果f=f，則保留當(dāng)前蜜源，清零蜜源搜索限制；若存在多個，則隨機(jī)拋棄其中的70%蜜源，隨機(jī)生成新蜜源，清零蜜源搜索限制。

4）如果f<f，隨機(jī)生成新蜜源，清零蜜源搜索限制。

在保留了可能的全局最優(yōu)解的同時，也保證了算法后期具有一定能力可以跳出局部最優(yōu)。

3 實例驗證

為測試GABC算法在求解分布式柔性作業(yè)車間調(diào)度問題的有效性，以10個工件在2個柔性工廠的調(diào)度模型實例進(jìn)行驗證，其加工時間如表2所示。通過遺傳算法（GA）作為對比算法驗證本文的改進(jìn)遺傳蜂群算法（GABC）的求解性能；并將標(biāo)準(zhǔn)人工蜂群算法的雇傭蜂和跟隨蜂搜索公式替換為交叉變異操作，命名為DABC，以其作為對比，驗證GABC在進(jìn)行局部搜索時的有效性。

算法通過MATLAB2019a編譯，運(yùn)行環(huán)境為Windows10 64位操作系統(tǒng)，Core i7-6700H 2.60Ghz CPU，12G RAM。

遺傳算法基本參數(shù)設(shè)置：最大迭代次數(shù)Max=500，個體數(shù)目N=100，交叉概率=0.9，變異概率=0.3。

人工蜂群算法參數(shù)設(shè)置：最大迭代次數(shù)Max=500，蜜源數(shù)量N=100，雇傭蜂和跟隨蜂數(shù)量都為=100，蜜源搜索次數(shù)上限=300。

表2 10個工件在2個工廠的加工時間表

三種算法分別運(yùn)行30次，實驗結(jié)果如表3所示，某次運(yùn)行得到的迭代曲線如圖6所示；改進(jìn)人工蜂群算法得到的調(diào)度結(jié)果如圖7所示，橫坐標(biāo)表示加工時間，縱坐標(biāo)表示工廠的加工機(jī)器，圖中小方塊表示各個工件的工序，其中數(shù)字如、“3-1”表示第3個工件的第1道工序。

表3 測試結(jié)果

圖6 迭代曲線

圖7 10個工件在2個工廠調(diào)度甘特圖

由表3數(shù)據(jù)和圖6可以看出，通過對比GA和DABC算法，兩種算法收斂速度相近，但DABC求得的最優(yōu)值明顯優(yōu)于GA，證明人工蜂群算法在求解分布式柔性作業(yè)車間調(diào)度問題的優(yōu)勢。對比DABC算法，本設(shè)計的GABC算法求解最優(yōu)值的平均值優(yōu)于DABC算法，說明GABC算法求解得最優(yōu)解比較穩(wěn)定；GABC算法在迭代速度上占較大優(yōu)勢，證明所設(shè)計的局部搜索操作的高效性。

4 結(jié)論

針對分布式柔性車間調(diào)度問題的特性，結(jié)合遺傳算法，改進(jìn)了人工蜂群算法的局部搜索階段，設(shè)計了一種基于機(jī)器編碼的交叉變異操作，改進(jìn)了偵查蜂拋棄蜜源的規(guī)則。通過仿真實驗和其他算法進(jìn)行對比，驗證了本文的改進(jìn)遺傳蜂群算法在保證算法求解精度的同時，能夠很好地縮短算法迭代次數(shù)，提高算法的求解效率，并且能有效地避免陷入局部最優(yōu)。本研究針對最小化最大完工時間的分布式柔性作業(yè)車間調(diào)度問題，接下來將繼續(xù)深入研究更加符合生產(chǎn)實際的多種加工約束和多優(yōu)化目標(biāo)的調(diào)度問題求解。

[1] 雷德明,蘇斌.基于多班教學(xué)優(yōu)化的多目標(biāo)分布式混合流水車間調(diào)度[J].控制與決策,2021,36(2):303-313.

[2] 王凌, 鄧瑾,王圣堯.分布式車間調(diào)度優(yōu)化算法研究綜述[J].控制與決策,2016,31(1):1-11.

[3] 吳秀麗,劉夏晶.差分進(jìn)化算法求解分布式柔性作業(yè)車間調(diào)度問題[J].計算機(jī)集成制造系統(tǒng),2019,25(10):2539-2558.

[4] Bargaoui H, Belkahla D O, GhediraK. A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion[J]. Computers & Industrial Engineering,2017,111(C):239-250.

[5] 楊曉林,胡蓉,錢斌,等.增強(qiáng)分布估計算法求解低碳分布式流水線調(diào)度[J].控制理論與應(yīng)用,2019,36(5):803-815.

[6] 張清勇,孫澤軒,雷德明.分布式兩階段混合流水車間調(diào)度[J]華中科技大學(xué)學(xué)報:自然科學(xué)版,2020,48(4):127-132.

[7] Li M,Su B,Lei D M. A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling[J]. Journal of Intelligent & Fuzzy Systems,2021,40(3):4545-4561.

[8] Chan FTS. Chung SH, Chan PLY. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems with Applications,2005,29(2):364-371.

[9] Giovanni L D,Pezzella F. An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem[J]. European Journal of Operational Research,2010,200(2):395-408.

[10] 楊江波,陳友玲,曹楠.面向柔性作業(yè)分布式車間的分層調(diào)度模型研究[J].計算機(jī)工程與應(yīng)用,2014,50(23):239-244.

[11] Chang H C, Liu TK. Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing,2017,28(8):1973-1986.

[12] Marzouki B, Driss O B, Ghedira K. Solving Distributed and Flexible Job shop Scheduling Problem using a Chemical Reaction Optimization metaheuristic[J]. Procedia Computer Science,2018,126:1424-1433.

[13] Lu P H,Wu M C,Tan H,et al. A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing,2018,29(1):19-34.

[14] 吳銳,郭順生,李益兵,等.改進(jìn)人工蜂群算法求解分布式柔性作業(yè)車間調(diào)度問題[J] .控制與決策,2019,34

(12):2527-2536.

[15] Meng L L,Zhang C Y, Ren Y P,et al. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[J].Computers & Industrial Engineering,2020,142:106347.

[16] Karaboga D.An idea based on honey bee swarm for numerical optimization[D]. Kayseri : Ereiyes University,2005.

[17] 易天,雷德明.基于人工蜂群算法的生產(chǎn)調(diào)度研究進(jìn)展[J].河北工業(yè)大學(xué)學(xué)報,2020,49(4): 24-32.

[18] 陳少,吉衛(wèi)喜,仇永濤,等.改進(jìn)人工蜂群算法求解柔性作業(yè)車間調(diào)度問題[J].組合機(jī)床與自動化加工技術(shù),2018(5):161-164.

[19] Zadeh M S, Katebi Y, Doniavi A. A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times[J]. International Journal of Production Research,2019,57(9-10):3020-3035.

[20] 李益兵,黃煒星,吳銳.基于改進(jìn)人工蜂群算法的多目標(biāo)綠色柔性作業(yè)車間調(diào)度研究[J]. 中國機(jī)械工程,2020,31(11):1344-1350,1385.

AN IMPROVED GENETIC BEE COLONY ALGORITHM FOR DISTRIBUTED FLEXIBLE JOB SHOP SCHEDULING PROBLEM

LI Jia-lu,*WANG Lei, WANG Jing-yun

（School of Mechanical Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China）

An improved genetic bee colony algorithm was proposed to solve the distributed flexible job-shop scheduling problem. The algorithm adopts A coding scheme based on machine coding was adopt, and according to the characteristics of the encoding characteristics and distributed flexible job shop, crossover operation based on the similarity was designed, which could avoid illegal solutions in the process of cross and improve the efficiency of the algorithm, and through different crossover operation, the search operation in the employ bees was improved, the iteration speed of the algorithm was also improved. The sequencing selection strategy was adopted to replace the original strategy of following bees. The nectar source abandonment mechanism of scout bees was improved. By comparing the obtained global optimal solution, the nectar sources that reached the search upper limit were partially abandoned to prevent the destruction of high-quality solution from being trapped in random search again. Finally, the effectiveness of the proposed algorithm was verified by comparing different algorithms to solve examples.

distributed scheduling; flexible job shop; artificial bee colony algorithm; genetic algorithm

10.3669/j.issn.1674-8085.2021.06.014

1674-8085（2021）06-0074-08

TH165

A

2021-05-24；

2021-07-19

安徽省自然科學(xué)基金項目(1708085ME129)，安徽工程大學(xué)“中青年拔尖人才”項目

李佳路(1996-)，男，河北唐山人，碩士生，主要從事生產(chǎn)調(diào)度和智能優(yōu)化算法研究(E-mail:986155622@qq.com)；

*王 雷(1982-)，男，安徽亳州人，教授，博士，主要從事智能車間調(diào)度及智能優(yōu)化算法機(jī)器人路徑規(guī)劃與控制等研究(E-mail:wangdalei2000@126.com)；

王靜云(1997-)，男，安徽銅陵人，碩士生，主要從事生產(chǎn)調(diào)度和智能優(yōu)化算法研究(E-mail:937102540@qq.com).