基于改進(jìn)離散人工蜂群算法的同類機(jī)調(diào)度優(yōu)化

張架鵬，倪志偉*，倪麗萍，朱旭輝，伍章俊

（1. 合肥工業(yè)大學(xué)管理學(xué)院，合肥230009； 2. 過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥230009）

（*通信作者電子郵箱:zhwnelson@163.com）

0 引言

調(diào)度問題是一類重要的組合優(yōu)化問題，根據(jù)現(xiàn)實(shí)生產(chǎn)的需要，通常包含具體的約束條件［1］。同類機(jī)調(diào)度問題是調(diào)度問題的一個(gè)分支，已被證明是NP-hard問題［2］。同類機(jī)一般描述為機(jī)器具有恒定的速度差異，這類機(jī)器產(chǎn)生的原因主要是機(jī)器的購(gòu)置批次差異導(dǎo)致不同批次的機(jī)器具有不同的處理速度、完成同類工作的操作人員的操作水平差異等，其主要存在于生產(chǎn)制造車間。除此之外，鋼材在多臺(tái)機(jī)器上的熱軋過程等也可以抽象成同類機(jī)問題。同類機(jī)調(diào)度問題是一類特殊的車間調(diào)度問題，是連接供應(yīng)鏈上下游重要的一環(huán)，在實(shí)際的生產(chǎn)調(diào)度中，運(yùn)用先進(jìn)的調(diào)度算法，制定科學(xué)合理的調(diào)度方案，可以有效地提高生產(chǎn)效率、節(jié)約資源，從而提升整個(gè)供應(yīng)鏈的效益。目前，沒有統(tǒng)一的方法解決同類機(jī)調(diào)度問題，因此，對(duì)此類問題的研究具有重要的實(shí)際意義。

目前，啟發(fā)式搜索算法是解決調(diào)度問題的一類重要可行方法，針對(duì)同類機(jī)調(diào)度問題，文獻(xiàn)［3］針對(duì)含作業(yè)到達(dá)時(shí)間的同類機(jī)調(diào)度問題，提出了一種改進(jìn)的啟發(fā)式算法；文獻(xiàn)［4］采用改進(jìn)的螢火蟲算法求解該問題，引入一種切實(shí)有效的針對(duì)同類機(jī)問題的離散編碼方式；文獻(xiàn)［5］提出一種采用最大調(diào)度時(shí)間（Largest Processing Time，LPT）算法進(jìn)行初始化，利用互換性質(zhì)進(jìn)行互換操作的啟發(fā)式算法求解該問題；文獻(xiàn)［6］設(shè)計(jì)了一種啟發(fā)式分治（Decompose-Compose，DC）算法，用于解決目標(biāo)解為最小完成時(shí)間和的同類機(jī)調(diào)度問題。上述方法在求解同類機(jī)調(diào)度問題時(shí)存在如下缺陷:改進(jìn)的啟發(fā)式算法的性能有待提高，無法適應(yīng)作業(yè)長(zhǎng)度差異較大且機(jī)器速度差異較小的情形；螢火蟲算法參數(shù)設(shè)置較多，迭代初期易陷入局部最優(yōu)；DC算法的運(yùn)行速度慢，通用性不強(qiáng)。

人工蜂群（Artificial Bee Colony，ABC）算法是一種較新的群智能優(yōu)化算法，由土耳其學(xué)者Karaboga［7］于2005年提出，以其實(shí)現(xiàn)簡(jiǎn)單、收斂速度快、求解精度高、魯棒性強(qiáng)［8］等特點(diǎn)受到學(xué)術(shù)界的廣泛關(guān)注，以后又有人提出了一系列改進(jìn)優(yōu)化策略［9］。目前，人工蜂群算法已成功應(yīng)用于人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練［10-11］、函數(shù)優(yōu)化［12］、機(jī)器人路徑規(guī)劃［13］、電力系統(tǒng)優(yōu)化［14］等領(lǐng)域，其中大多數(shù)的研究解決的是連續(xù)型問題。對(duì)于現(xiàn)實(shí)生活中存在的很多離散問題的研究相對(duì)較少，由于人工蜂群算法的參數(shù)少、操作簡(jiǎn)單，近年來很多學(xué)者開始將離散化的人工蜂群算法應(yīng)用到工業(yè)生產(chǎn)［15］、數(shù)據(jù)挖掘［16］等多個(gè)領(lǐng)域。

目前，對(duì)于離散人工蜂群算法的研究主要集中在解決調(diào)度問題上［17］。文獻(xiàn)［18］運(yùn)用離散人工蜂群算法進(jìn)行云任務(wù)調(diào)度優(yōu)化；文獻(xiàn)［19］將離散人工蜂群算法應(yīng)用到煉鋼連鑄的工業(yè)過程中；文獻(xiàn)［20］利用離散ABC 算法求解旅行商問題（Travelling Salesman Problem，TSP）；文獻(xiàn)［21］提出了一種求解混合流水線問題的離散人工蜂群算法；文獻(xiàn)［22］針對(duì)最小化完工時(shí)間為目標(biāo)的混合流水車間調(diào)度（Hybrid Flow Shop，HFS）問題，提出一種有效的離散人工蜂群算法，該算法利用混合表示以及前向解碼和后向解碼方法的組合來解決該問題；文獻(xiàn)［23］利用改進(jìn)的人工蜂群算法求解任務(wù)指派問題；文獻(xiàn)［24］和文獻(xiàn)［25］分別提出一種求解阻塞型流水車間調(diào)度的離散人工蜂群算法；文獻(xiàn)［26］提出一種改進(jìn)的離散人工蜂群算法求解批量流水線調(diào)度問題；文獻(xiàn)［27］提出一種用于優(yōu)化逆向物流網(wǎng)絡(luò)的混合人工蜂群算法，算法給出8 種性能良好的鄰域結(jié)構(gòu)，從而提高算法的開發(fā)能力；文獻(xiàn)［28］提出了一種改進(jìn)的離散人工蜂群算法來解決具有鐵水系統(tǒng)動(dòng)態(tài)跳躍特征的混合柔性流水車間調(diào)度問題。

以上方法運(yùn)用在不同的調(diào)度問題上，其算法性能均有一定提升，但是在協(xié)調(diào)算法的求解精度、收斂速度和穩(wěn)定性方面性能較差。因此，本文提出了一種改進(jìn)的離散型人工蜂群（Improved Discrete Artificial Bee Colony，IDABC）算法，并應(yīng)用于同類機(jī)調(diào)度問題。引入基于離散人工蜂群算法的同類機(jī)調(diào)度問題的十進(jìn)制編碼模型，在原始人工蜂群算法的基礎(chǔ)上改進(jìn)初始化策略，并針對(duì)實(shí)際問題，提出待優(yōu)參數(shù)的生成策略，借鑒差分進(jìn)化算法、模擬退火算法的思想改進(jìn)雇傭蜂和跟隨蜂的局部搜索策略，充分利用最優(yōu)解的優(yōu)質(zhì)信息改進(jìn)偵察蜂。通過15個(gè)算例，將本文改進(jìn)的ABC 算法與文獻(xiàn)［21］提出的混合離散人工蜂群（Hybrid Discrete Artificial Bee Colony，HDABC）算法、文獻(xiàn)［4］提出的解決該類同類機(jī)調(diào)度問題的改進(jìn)螢火蟲（Improved Glowworm Swarm Optimization，IGSO）算法、原始ABC算法以及遺傳算法（Genetic Algorithm，GA）和粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法等經(jīng)典智能優(yōu)化算法進(jìn)行了比較。

1 同類機(jī)調(diào)度問題的數(shù)學(xué)模型

1.1 模型假設(shè)

1）有若干臺(tái)機(jī)器同時(shí)加工若干件作業(yè)，且每件作業(yè)只能被其中一臺(tái)機(jī)器加工。

2）每臺(tái)機(jī)器的加工速度是任意的，同一臺(tái)機(jī)器的加工速度恒定。

3）每件作業(yè)的長(zhǎng)度是任意的。

4）作業(yè)到達(dá)機(jī)器的時(shí)間是任意的，且只有機(jī)器接收到作業(yè)后，才能進(jìn)行加工。

5）機(jī)器在運(yùn)行過程中不會(huì)出現(xiàn)故障，即作業(yè)的加工不會(huì)被中斷。

在實(shí)際的生產(chǎn)加工場(chǎng)景中，生產(chǎn)環(huán)境較為復(fù)雜，規(guī)模也較大，一般調(diào)度問題難以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行求解。調(diào)度問題可以用甘特圖描述，如圖1 所示，圖1 表示4 臺(tái)機(jī)器加工10 件作業(yè)一種情況的甘特圖。

圖1 4機(jī)器10作業(yè)加工示意圖Fig.1 Processing schematic diagram of 4 machines 10 jobs

1.2 問題描述

同類機(jī)調(diào)度問題的描述如下:假設(shè)有n個(gè)作業(yè)J={J1，J2，…，Jj，…，Jn}，其中作業(yè)Jj(j= 1，2，…，n)的長(zhǎng)度為pj。這n個(gè)作業(yè)需要用m臺(tái)機(jī)器M={M1，M2，…，Mn}進(jìn)行加工，其中機(jī)器Mi(i= 1，2，…，m)加工這n個(gè)作業(yè)的速度為vi(i=1，2，…，m)。 作 業(yè)Ji到 達(dá) 機(jī) 器Mi的 時(shí) 間 為rij(i=1，2，，…，m，j= 1，2，…，n)，每件作業(yè)的加工起點(diǎn)為機(jī)器接收到該作業(yè)。作業(yè)Ji在機(jī)器Mi的時(shí)間為pij(i= 1，2，…，m，j=1，2，…，n)，該作業(yè)的完工時(shí)間為Cj(j= 1，2，…，n)，且每件作業(yè)只能被其中一臺(tái)機(jī)器加工。本文研究的是Qm|rj|Cmax類型的同類機(jī)調(diào)度問題，考慮到機(jī)器的加工效率，其目標(biāo)函數(shù)minZ為最小化所有作業(yè)的最大完工時(shí)間，即使得最后完工的那臺(tái)機(jī)器的加工時(shí)間最小，縮短產(chǎn)品的交付時(shí)間。

1.3 數(shù)學(xué)模型及約束條件

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

約束條件:

式（1）若由第i臺(tái)機(jī)器加工第j件作業(yè)，則aij=1；否則aij=0。

式（2）表示每件作業(yè)只能被其中一臺(tái)機(jī)器加工。

式（3）表示機(jī)器i加工作業(yè)j所用的時(shí)間。

式（4）表示作業(yè)j的完工時(shí)間。

2 改進(jìn)離散型人工蜂群算法

在ABC 算法中，雇傭蜂和跟隨蜂負(fù)責(zé)鄰域搜索尋優(yōu)，代表算法的開發(fā)能力；偵查蜂負(fù)責(zé)對(duì)被遺棄的食物源進(jìn)行隨機(jī)初始化，代表算法的探索能力。為提高算法的性能，本文引入了種群初始化方法和搜索機(jī)制，既保證算法具有較高的收斂速度和求解精度，又防止算法陷入局部最優(yōu)。

2.1 基本人工蜂群算法

人工蜂群算法，是受自然界蜜蜂覓食行為的啟發(fā)而提出的一種群智能優(yōu)化算法。將蜜蜂采蜜的過程轉(zhuǎn)化為優(yōu)化問題的尋優(yōu)過程。蜜蜂群體分為3 類:雇傭蜂、跟隨蜂和偵察蜂，雇傭蜂和跟隨蜂負(fù)責(zé)鄰域?qū)?yōu)，偵查蜂負(fù)責(zé)隨機(jī)初始化被遺棄食物源。

人工蜂群算法需要初始化設(shè)置的參數(shù)有3 個(gè):蜂群規(guī)模2SN，其中雇傭蜂和跟隨蜂的規(guī)模各為SN；算法的最大迭代次數(shù)MaxCycle；食物源經(jīng)多次迭代而未發(fā)生改變的最大保留次數(shù)limit。

ABC算法的主要步驟如下:

1）初始化解。根據(jù)式（5）隨機(jī)生成SN個(gè)D維初始可行解{X1，X2，…，XSN}。其中，i∈{1，2，…，SN}，j∈{1，2，…，D}，D代表食物源的屬性數(shù)，uj、lj代表xij取值的最大、最小值，rand［0，1］產(chǎn)生0～1的隨機(jī)數(shù)。式（5）如下:

2）記錄最優(yōu)解。計(jì)算SN個(gè)可行解的適應(yīng)度值fiti，根據(jù)適應(yīng)度值確定并記錄最優(yōu)解。

循環(huán)開始:

3）雇傭蜂階段。雇傭蜂根據(jù)式（6）對(duì)可行解Xi進(jìn)行鄰域搜索，隨機(jī)選擇Xi的一維xij轉(zhuǎn)化為vij，產(chǎn)生新的可行解Vi，計(jì)算新可行解的目標(biāo)函數(shù)值和適應(yīng)度值并比較Xi和Vi的適應(yīng)度值的大小:若fit(Vi)＞fit(Xi)，則用Vi替換Xi；否則，保持Xi的位置不變。式（6）如下:

5）計(jì)算SN個(gè)可行解的適應(yīng)度值fiti，根據(jù)適應(yīng)度值確定并記錄最優(yōu)解。

6）偵察蜂階段。記錄食物源Xi的開采次數(shù)trial，若trial＞limit，則放棄該食物源，利用式（5）隨機(jī)生成新的食物源Xi，加入雇傭蜂和跟隨蜂的搜索隊(duì)列。該過程主要是避免解陷入局部最優(yōu)。

7）循環(huán)。判斷循環(huán)終止條件是否成立，若成立，結(jié)束循環(huán)，算法結(jié)束；否則跳轉(zhuǎn)到步驟2），進(jìn)入下一次循環(huán)。

2.2 問題的編碼設(shè)計(jì)

同類機(jī)調(diào)度問題是一類組合優(yōu)化問題，需要將實(shí)數(shù)轉(zhuǎn)化為整數(shù)，即將人工蜂群算法進(jìn)行離散化處理。假設(shè)在該同類機(jī)調(diào)度問題中包含U臺(tái)機(jī)器和D件作業(yè)，雇傭蜂和偵察蜂的種群規(guī)模均為SN，目標(biāo)函數(shù)為最小化最大完工時(shí)間。對(duì)于該問題，需考慮作業(yè)的到達(dá)時(shí)間，每臺(tái)機(jī)器上的作業(yè)按照先到達(dá)先加工的原則進(jìn)行加工即可。

根據(jù)該類同類機(jī)調(diào)度問題的特點(diǎn)，本文給出一種離散化的編碼策略。該問題解的具體編碼設(shè)計(jì)如下列矩陣所示，Z是一個(gè)SN×D的十進(jìn)制矩陣，Z={X1，X2，…，XSN}表示SN個(gè)加工方案，對(duì)應(yīng)初始的SN個(gè)食物源。每一個(gè)加工方案用Z的一個(gè)行向量Xi=(xi1，xi2，…，xiD)表示，xij的值表示第j件作業(yè)對(duì)應(yīng)的加工機(jī)器，其中i={1，2，…，SN}，j={1，2，…，D}，xij={1，2，…，U}。食物源的屬性與作業(yè)對(duì)應(yīng)，屬性值與作業(yè)的加工機(jī)器對(duì)應(yīng)，如編碼（2，1，3，2，1，2）表示，作業(yè)2、5 在第一臺(tái)機(jī)器上加工，作業(yè)1、4、6 在第二臺(tái)機(jī)器上加工，作業(yè)3 在第三臺(tái)機(jī)器上加工。

2.3 初始化策略

群智能優(yōu)化算法的初始化，對(duì)解的質(zhì)量和算法的收斂速度具有直接影響。在ABC 算法中，考慮使初始解均勻分布在可行解空間上（可行域內(nèi)），可以加強(qiáng)解的質(zhì)量和算法的全局收斂性。在ABC 算法的初始化過程中，一般采用隨機(jī)方法初始化蜂群，對(duì)于離散人工蜂群算法，食物源各參數(shù)的可行域是有限個(gè)整數(shù)集合，因此，在算法的初始化階段，需要保證食物源各參數(shù)在可行域上均勻取值。

本文給出了一種初始化策略，采用實(shí)數(shù)向上取整的方式，實(shí)現(xiàn)浮點(diǎn)數(shù)到整數(shù)間的轉(zhuǎn)換。將初始化方程（5）更新為:

其中:ceil()是向上取整函數(shù)，經(jīng)此方法處理，初始化xij的取值范圍是[1，2，…，uj]，理論上該uj個(gè)整數(shù)的取值概率相同，均為1/uj。這里需要說明的是，在該類同類機(jī)調(diào)度問題中，食物源參數(shù)的取值下限lj= 1，與最小的機(jī)器編號(hào)相對(duì)應(yīng)，所以式（9）不考慮lj的取值情況。

通過這種初始化方法，既實(shí)現(xiàn)了離散化，又保證了食物源的各參數(shù)在可行域內(nèi)具有相同的取值概率，提高了算法的性能。算法中的雇傭蜂、跟隨蜂、偵察蜂階段均采用ceil()函數(shù)實(shí)現(xiàn)離散化。

2.4 局部搜索策略

2.4.1 待優(yōu)參數(shù)的生成策略

在原始的人工蜂群算法中，雇傭蜂和跟隨蜂根據(jù)式（6）開發(fā)更優(yōu)的食物源，其中參數(shù)j表示食物源中待優(yōu)化的屬性，在值域內(nèi)隨機(jī)生成。本文根據(jù)同類機(jī)調(diào)度問題的編碼方式，以平衡機(jī)器的負(fù)載為目標(biāo)，在雇傭蜂階段，針對(duì)待優(yōu)參數(shù)j提出新的生成策略，提升算法的收斂速度。具體步驟如下:

步驟1 尋找目標(biāo)食物源中出現(xiàn)次數(shù)最多的屬性值，即加工作業(yè)最多的機(jī)器，若滿足條件的屬性值有多個(gè)，選擇值最小的屬性值記為MostValue。

步驟2 記錄該屬性值的出現(xiàn)次數(shù)n以及在食物源中的位置locations。

步驟3 在locations中隨機(jī)選取一個(gè)作為待優(yōu)化參數(shù)j。

其 中，mostValue={1，2，…，uj}，locations為1×n的 行向量。

2.4.2 基于差分算法的局部搜索策略

差分進(jìn)化（Differential Evolution，DE）算法是一種基于群體差異的啟發(fā)式并行搜索方法，其本質(zhì)上是一種函數(shù)優(yōu)化算法。DE算法具有良好的尋優(yōu)能力，已成功應(yīng)用于很多優(yōu)化問題中。DE 算法的思想上其他進(jìn)化算法類似，其核心是變異、交叉和選擇操作，不同在于，DE 算法通過種群中多個(gè)個(gè)體的差分信息實(shí)現(xiàn)進(jìn)化。DE 算法有多種變異策略，其中DE/rand/1 策略用來維持種群的多樣性，避免陷入局部最優(yōu)，DE/best/1策略可以加快算法的收斂速度，二者的公式如下:

其中:i={1，2，…，SN}，p1、p2、p3是{1，2，…，SN}中隨機(jī)選取的不與i相等的參數(shù)，xbest為當(dāng)前全局最優(yōu)解，F(xiàn)∈[0.5，1]。

受差分進(jìn)化算法的變異策略的啟發(fā)，結(jié)合人工蜂群算法的特點(diǎn)，本文提出了新的局部搜索策略。通過對(duì)差分進(jìn)化算法的DE/rand/1變異策略和DE/best/1變異策略的變動(dòng)，將雇傭蜂和偵查蜂的局部搜索式（6）更新為以下3 種，并用ceil()函數(shù)進(jìn)行離散化處理。

其中:i={1，2，…，SN}，k是{1，2，…，SN}中隨機(jī)選取的參數(shù)，且k≠i，J={1，2，…，D}，由上文的生成策略生成。best 表示當(dāng)前全局最優(yōu)解，即最佳食物源，φij∈[0，1]，隨機(jī)取值。

2.5 雇傭蜂階段

雇傭蜂的任務(wù)是在初始的食物源的鄰域內(nèi)搜索更優(yōu)的解，該過程需要綜合考慮種群的多樣性和收斂速度。本文借鑒差分進(jìn)化算法的進(jìn)化策略，進(jìn)化初期在較大范圍內(nèi)搜索最優(yōu)解，保持種群的多樣性，進(jìn)化后期，種群以收斂到較小的范圍內(nèi)，縮小搜索范圍以增加搜索精度。本文以可行解的平均適應(yīng)度值為標(biāo)準(zhǔn)，區(qū)分食物源的優(yōu)劣，并針對(duì)較優(yōu)和較劣的食物源分別給出不同的搜索策略，雇傭蜂搜索過程如下:

步驟1 為當(dāng)前解集中每個(gè)可行解對(duì)應(yīng)的食物源分配一只雇傭蜂。

步驟3 計(jì)算指定解Xi的適應(yīng)度值fit(Xi)。

步驟6 計(jì)算新解適應(yīng)度值fit(Vi)并與原解適應(yīng)度值fit(Xi)比較:若fit(Vi)＞fit(Xi)則更新食物源；否則保留原食物源。

2.6 跟隨蜂階段

雇傭蜂尋優(yōu)過程結(jié)束，跟隨蜂開始工作，在原始的人工蜂群算法中，跟隨蜂采用輪盤賭的方式選擇目標(biāo)食物源，并進(jìn)行進(jìn)一步搜索，從而加快算法的收斂速度。在跟隨蜂尋優(yōu)的過程中，為了防止陷入局部最優(yōu)，本文通過借鑒模擬退火算法中“以一定的概率接受較差解”的思想，給出了一種新的食物源更新策略，從而更新了跟隨蜂的搜索過程。定義如下概率因子:

在模擬退火算法中，接受較差解的概率會(huì)隨著時(shí)間的推移溫度的降低而不斷減少。在本文中，將接受較差解的概率與解的質(zhì)量相關(guān)聯(lián)，如果較差解與原解的適應(yīng)度值差距越小，則接受該較差解的概率越大；反之概率越小，概率因子pi的取值范圍是(0，e-1)。

跟隨蜂搜索策略如下:

步驟1 跟隨蜂以輪盤賭的方式隨機(jī)選擇食物源Xi。

步驟2 選擇式（14）進(jìn)行局部搜索，得到新食物源Vi。

步 驟3 計(jì) 算Xi、Vi的 適 應(yīng) 度 值fit(Vi)、fit(Xi)，如 果fit(Vi)＞fit(Xi)，更新食物源；否則執(zhí)行步驟4。

步驟4 根據(jù)式（15）計(jì)算跟隨蜂選擇較差解Vi的概率pi，如果pi＞rand，更新食物源；否則保留原食物源進(jìn)入下一次迭代。

2.7 偵查蜂階段

在原始人工蜂群算法中，食物源經(jīng)limit次迭代未更新就會(huì)被舍棄，偵查蜂隨機(jī)初始化生成一個(gè)新的食物源，但此食物源的質(zhì)量一般不高，且理論上擁有更少的迭代更新的次數(shù)，因此對(duì)全局最優(yōu)解的貢獻(xiàn)有限。為提高偵查蜂初始化食物源Xi的質(zhì)量，本文充分利用最佳食物源Xs攜帶優(yōu)質(zhì)信息，讓Xs的參數(shù)從第二位起間隔插入Xi中并取代Xi中原有參數(shù)，生成新的食物源Xj。比較食物源Xi與食物源Xj的適應(yīng)度值，取適應(yīng)度值較優(yōu)的作為新的食物源。過程如下:

2.8 改進(jìn)離散型人工蜂群算法的步驟

步驟1 初始化參數(shù)。最大迭代次數(shù)MaxCycle和食物源多次迭代未更新的保留次數(shù)limit，根據(jù)式（9）初始化雇傭蜂種群Xi（i={1，2，…，SN}）。

步驟2 計(jì)算種群中各食物源的適應(yīng)度值fit(Xi)。

步驟3 根據(jù)3.4 節(jié)給出的待優(yōu)參數(shù)選擇策略確定優(yōu)化參數(shù)j（j={1，2，…，D}）。

步驟4 記錄當(dāng)前全局最優(yōu)解best，賦值cycle= 1，開始

因此，理論上，在求解Qm|rj|Cmax類型的同類機(jī)調(diào)度問題上，IDABC算法的較原始人工蜂群算法更優(yōu)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

本文所有程序代碼均采用Matlab R2016a 軟件編寫，使用的PC 配置如下，操作系統(tǒng):64 位Windows 10，處理器:Intel Core i7-7700 CPU 3.60 GHz 3.60 GHz，內(nèi)存:8 GB。

本文ABC 算法的參數(shù)設(shè)置如下，雇傭蜂規(guī)模SN= 90，最大迭代次數(shù)MaxCycle= 700，食物源經(jīng)多次迭代未更新的最大保留次數(shù)limit= 50。為保證對(duì)比的公平性，將對(duì)比算法的參數(shù)設(shè)置如下:原始離散人工蜂群算法參數(shù)設(shè)置同上；文獻(xiàn)［21］改進(jìn)的離散人工蜂群算法的種群規(guī)模和最大迭代次數(shù)設(shè)置同上；文獻(xiàn)［4］改進(jìn)離散螢火蟲算法的最大迭代次數(shù)設(shè)為700，種群規(guī)模設(shè)為90，其余參數(shù)保持原有的設(shè)置不變；遺傳算法（GA）種群規(guī)模為90，交叉概率為1，變異概率為0.01，迭代次數(shù)為700；粒子群優(yōu)化算法（PSO）的種群規(guī)模為90，迭代次數(shù)為700，學(xué)習(xí)因子為1.494 45，慣性權(quán)重為0.729。

3.2 結(jié)果分析

3.2.1 實(shí)驗(yàn)結(jié)果分析

針對(duì)Qm|rj|Cmax型同類機(jī)調(diào)度問題，本文設(shè)計(jì)的算例為JiMj，其中Ji表示作業(yè)數(shù)量，i={50，80，100，150，200}，Mj表示加工機(jī)器數(shù)量，j={6，8，10}，如J50M6表示50 件作業(yè)在6 臺(tái)機(jī)器上進(jìn)行加工。每件作業(yè)長(zhǎng)度取1～100 的隨機(jī)數(shù)，每臺(tái)機(jī)器的運(yùn)行速度取1～10的隨機(jī)數(shù)，作業(yè)按照先到達(dá)先加工的順序在各臺(tái)機(jī)器上加工。

本文考慮了該類同類機(jī)調(diào)度問題的15 種不同規(guī)模的應(yīng)用場(chǎng)景，給出15 個(gè)算例，對(duì)于每一種應(yīng)用場(chǎng)景，用IDABC、HDABC、IGSO、原始人工蜂群（ABC）算法、遺傳算法（GA）和粒子群優(yōu)化（PSO）算法進(jìn)行求解。為防止偶然性干擾，每組實(shí)驗(yàn)運(yùn)行100 次求平均值，并用平均值（ave）、最優(yōu)值（min）、最劣值（max）和方差（var）等4個(gè)指標(biāo)衡量各種算法的優(yōu)劣。

表1 給出了算法IDABC、HDABC、IGSO、ABC、GA 和PSO分別求解上述15 個(gè)算例的結(jié)果，圖2（a）～（d）為IDABC 與ABC、HDABC、IGSO 等算法針對(duì)不同算例的求解曲線，其中，每個(gè)算法的迭代次數(shù)均取為700。4 個(gè)子圖選取的算例分別為J50M8、J80M6、J100M10和J200M8，代表了從小到大的不同規(guī)模的應(yīng)用場(chǎng)景。通過比較分析表1結(jié)果和圖2（a）～（d）可以得出以下結(jié)論。

首先，在收斂速度方面，由圖2（a）～（d）的4種算例的求解曲線可以看出，IDABC 算法的收斂速度要明顯快于其他3 種算法；其次，在求解精度方面，由表1 實(shí)驗(yàn)數(shù)據(jù)可知，對(duì)于所有15 個(gè)算例的求解結(jié)果，IDABC 算法求解的平均值、最優(yōu)值和最劣值均優(yōu)于其他5 種算法，與5 種算法中表現(xiàn)最好的HDABC 算法相比，求解精度平均提高了4.1%，且實(shí)驗(yàn)規(guī)模越大，IDABC 算法的優(yōu)越性越明顯，表明IDABC 算法在求解精度上是6種算法中最好的；最后，在算法的穩(wěn)定性方面，由表1實(shí)驗(yàn)數(shù)據(jù)可知，除了算例J80M10和J200M6，IDABC 對(duì)其求解的方差略差于HDABC 的求解結(jié)果外，對(duì)其余13 個(gè)算例的求解結(jié)果，IDABC算法求解的方差均為最優(yōu)，與HDABC算法相比，穩(wěn)定性平均提高了26.9%，且對(duì)于大規(guī)模的問題IDABC 算法也能保證平均誤差很小，表明IDABC 算法在求解的穩(wěn)定性方面總體上優(yōu)于其他5種算法。綜上所述，在以上6種算法解決Qm|rj|Cmax型同類機(jī)調(diào)度問題中，本文改進(jìn)的離散人工蜂群算法在算法的求解質(zhì)量方面和求解的穩(wěn)定性方面均為最優(yōu)，且明顯優(yōu)于IGSO、GA 和PSO 算法，在收斂速度方面優(yōu)于HDABC、IGSO和ABC等算法。

3.2.2 參數(shù)分析

群智能算法初始化參數(shù)的選取對(duì)算法的性能有一定的影響，同一算法在解決不同領(lǐng)域的問題時(shí)，其參數(shù)的設(shè)置存在差異。原始的ABC 算法采用的是針對(duì)連續(xù)型問題的編碼方式，本文利用改進(jìn)的離散型人工蜂群算法求解Qm|rj|Cmax類型的同類機(jī)調(diào)度問題，采用的編碼方式是離散的，為達(dá)到最佳實(shí)驗(yàn)效果，需要對(duì)ABC 算法的參數(shù)進(jìn)行分析。本文實(shí)驗(yàn)討論的參數(shù)有3個(gè):初始食物源數(shù)量（雇傭蜂規(guī)模）SN、算法最大迭代次數(shù)MaxCycle和食物源經(jīng)多次迭代未更新的最大保留次數(shù)

limit。

以下3 組實(shí)驗(yàn)分別分析SN、MaxCycle和limit對(duì)算法性能的影響，采用的同類機(jī)調(diào)度問題的算例均J100M10，每組實(shí)驗(yàn)算法運(yùn)行100 次，取平均值作為最終結(jié)果，并以目標(biāo)函數(shù)的平均值作為評(píng)價(jià)函數(shù)值評(píng)價(jià)算法的性能。

圖2 四種算例的算法求解曲線Fig.2 Algorithmic solution of curves for four examples

圖3（a）顯示的是雇傭蜂規(guī)模SN對(duì)本文算法性能的影響（MaxCycle=1 000，limit=80），如圖3（a）所示，算法的評(píng)價(jià)函數(shù)值與雇傭蜂規(guī)模整體上呈現(xiàn)負(fù)相關(guān)，且在一定范圍內(nèi)，算法的評(píng)價(jià)函數(shù)值隨雇傭蜂規(guī)模的增加而快速減小，當(dāng)雇傭蜂規(guī)模超過一定值后，算法性能逐漸趨于穩(wěn)定。由圖3（a）可知，算法的最佳雇傭蜂規(guī)模為90。

圖3（b）分析的是最大迭代次數(shù)MaxCycle對(duì)本文算法性能的影響（SN=90，limit=80），迭代次數(shù)對(duì)群智能算法的影響巨大，本文取（100，300，500，600，700，800，900，1 000，1 100，1 200）10 組最大迭代次數(shù)進(jìn)行分析。由圖3（b）可以看出，在MaxCycle∈[0，700]范圍內(nèi)，評(píng)價(jià)函數(shù)值隨最大迭代次數(shù)的增加越來越優(yōu)，當(dāng)MaxCycle＞700，最大迭代次數(shù)的改變對(duì)評(píng)價(jià)函數(shù)值的影響相對(duì)平緩，即不能較大程度上影響算法性能。因此，針對(duì)該類同類機(jī)調(diào)度問題的人工蜂群算法的最大迭代次數(shù)取為700。

圖3（c）描述的是食物源經(jīng)多次迭代未更新的最大保留次數(shù)limit對(duì)本文算法性能的影響（SN=90，MaxCycle=700），本文limit的值?。?0，20，30，40，50，60，70，80，90，100）10 組，通過實(shí)驗(yàn)分析其優(yōu)劣。理論上，如果limit的值太小，則食物源更新的速度過快，無法達(dá)到最優(yōu)解，如果limit的值太大，則會(huì)降低種群的多樣性，算法易陷入局部最優(yōu)，因此這兩種情況都會(huì)降低算法的性能。如圖3（c）所示，在limit∈[0，50]范圍內(nèi)，算法的評(píng)價(jià)函數(shù)值隨limit值的遞增而減小，此時(shí)算法性能逐漸提升，當(dāng)limit= 50 時(shí)，算法的性能在實(shí)驗(yàn)組中達(dá)到最優(yōu)，當(dāng)limit＞50時(shí)，評(píng)價(jià)函數(shù)值整體上隨limit值的遞增而增大，算法性能逐漸下降。因此，針對(duì)該類同類機(jī)調(diào)度問題的參數(shù)limit的最佳取值為50。

圖3 參數(shù)SN、MaxCycle和limit對(duì)本文算法性能的影響Fig.3 Effect of parameters SN、MaxCycle and limit on performance of the proposed algorithm

4 結(jié)語(yǔ)

針對(duì)同類機(jī)調(diào)度領(lǐng)域存在的問題和不足，本文提出了一種改進(jìn)的離散型人工蜂群（IDABC）算法求解同類機(jī)調(diào)度問題。首先，引入了同類機(jī)調(diào)度問題的數(shù)學(xué)模型；其次，引入了種群初始化策略，獲得均勻分布的種群，通過改進(jìn)雇傭蜂和跟隨蜂的局部搜索策略，提高了算法的種群多樣性和防止算法陷入局部最優(yōu)，通過提出帶優(yōu)參數(shù)的生成策略和改進(jìn)偵察蜂的全局搜索過程，提高了算法的收斂速度；最后，分析了本文改進(jìn)算法的整體性能，并利用15 個(gè)算例的仿真對(duì)比實(shí)驗(yàn)，證明了本文算法具有良好的收斂速度、求解精度以及求解穩(wěn)定性，可以有效地求解同類機(jī)調(diào)度問題。

本研究只考慮了最小化最大加工時(shí)間一種類型的同類機(jī)調(diào)度問題，在后續(xù)的研究工作中，應(yīng)考慮更多應(yīng)用場(chǎng)景，同時(shí)，進(jìn)一步優(yōu)化人工蜂群算法，提升算法的尋優(yōu)性能。