顧文斌，李育鑫，錢煜暉，肖紫涵，秦展鵬

(河海大學(xué) 機(jī)電工程學(xué)院，江蘇 常州 213022)

0 引言

混合流水車間調(diào)度問(wèn)題(Hybrid Flow-shop Scheduling Problem, HFSP)又被稱為柔性流水車間調(diào)度問(wèn)題，是傳統(tǒng)流水車間調(diào)度問(wèn)題和并行機(jī)調(diào)度問(wèn)題的綜合。SALVADOR[1]基于石油工業(yè)中的調(diào)度問(wèn)題，于1973年首次提出了混合流水車間調(diào)度問(wèn)題。在HFSP中，所有工件都以相同的順序流經(jīng)各個(gè)加工階段，每個(gè)階段都有一臺(tái)或多臺(tái)加工機(jī)器，且至少有一個(gè)階段的并行機(jī)器數(shù)大于1。問(wèn)題的研究目標(biāo)是如何安排所有工件在各個(gè)階段的加工順序以及加工機(jī)器，以改善企業(yè)生產(chǎn)的一些性能指標(biāo)，如最小化最大完工時(shí)間、最小化生產(chǎn)能耗、最小化關(guān)鍵機(jī)器負(fù)載率等。海量的工件，以及繁多的加工階段和加工機(jī)器使得HFSP具有很高的復(fù)雜性，它已被證明是NP-Hard問(wèn)題。HFSP具有很強(qiáng)的工程背景，尤其是流程工業(yè)和離散制造工業(yè)，現(xiàn)已廣泛應(yīng)用于機(jī)械、鋼鐵、化工、物流、食品、紡織和半導(dǎo)體等領(lǐng)域，因此研究HFSP具有重要的實(shí)際意義。

HFSP通常被分為相同并行機(jī)、均勻并行機(jī)和不相關(guān)并行機(jī)3類[2]。相同并行機(jī)HFSP是指同一工件在一個(gè)階段的加工時(shí)間是固定的，與機(jī)器無(wú)關(guān)；均勻并行機(jī)HFSP是指同一工件在一個(gè)階段的加工時(shí)間與所選擇機(jī)器的加工速度成反比；不相關(guān)并行機(jī)HFSP是指同一工件在一個(gè)階段的加工時(shí)間取決于工件與加工機(jī)器的匹配程度。本文研究相同并行機(jī)HFSP(HFSP with Identical Parallel Machine, HFSP-IPM)。

目前求解HFSP-IPM的方法通常分為精確方法、啟發(fā)式方法和元啟發(fā)式方法3類。精確方法包括數(shù)學(xué)規(guī)劃法、分支定界法和拉式松弛算法等，能夠解決小規(guī)模的簡(jiǎn)單問(wèn)題，但實(shí)際問(wèn)題的解空間通常很大，其計(jì)算時(shí)間令人難以接受;啟發(fā)式方法包括NEH(Nawaz-Enscore-Ham)算法、Palmer算法和CDS(Campbell-Duder-Simth)算法等，雖然能夠在短時(shí)間內(nèi)獲得問(wèn)題的解，但往往容易陷入局部最優(yōu)，解的質(zhì)量得不到保證;元啟發(fā)式方法通過(guò)模擬自然界的規(guī)則和現(xiàn)象，能夠很好地求解HFSP，近年來(lái)相關(guān)算法不斷出現(xiàn)，如遺傳算法(Genetic Algorithm, GA)[3]、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法[4]、人工蜂群(Artificial Bee Colony, ABC)算法[5]、分布估計(jì)算法(Estimation of Distribution Algorithm, EDA)[6]、候鳥優(yōu)化(Migrating Birds Optimization, MBO)算法[7]等。元啟發(fā)式方法通過(guò)構(gòu)造一系列初始排列，經(jīng)過(guò)一定數(shù)量的循環(huán)迭代從而得到問(wèn)題的最優(yōu)解，是一種智能優(yōu)化算法。例如，王圣堯等[8]提出一種基于概率模型的分布估計(jì)算法來(lái)求解HFSP;崔琪等[9]針對(duì)混合流水車間調(diào)度問(wèn)題提出一種改進(jìn)的混合變鄰域搜索的遺傳算法，該算法融入變鄰域搜索的思想，以增強(qiáng)局部搜索能力;軒華等[10]針對(duì)以最小化總加權(quán)完成時(shí)間為目標(biāo)的可重入HFSP，提出一種自適應(yīng)的改進(jìn)遺傳算法;PAN等[11]提出24種啟發(fā)式規(guī)則，將其與離散人工蜂群算法混合，從而求解混合流水車間調(diào)度問(wèn)題;CAI等[12]針對(duì)分布式HFSP提出一種動(dòng)態(tài)混合蛙跳算法，該算法采用全局搜索和動(dòng)態(tài)多鄰域搜索，有效提高了搜索質(zhì)量;OZTOP等[13]針對(duì)HFSP提出一種雙目標(biāo)混合整數(shù)線性規(guī)劃模型和一種雙目標(biāo)約束規(guī)劃模型，并設(shè)計(jì)了7種雙目標(biāo)元啟發(fā)式算法來(lái)解決該問(wèn)題。

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法最早由KENNEDY等[14]于1995年提出，其基本思想是模擬鳥群隨機(jī)搜尋食物的捕食行為。PSO算法具有實(shí)現(xiàn)容易、搜索能力較強(qiáng)、控制參數(shù)少、收斂快等優(yōu)點(diǎn)，因此受到研究人員的廣泛關(guān)注，常用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制等領(lǐng)域。

近年來(lái)，PSO算法在生產(chǎn)調(diào)度領(lǐng)域被廣泛運(yùn)用，尤其是求解HFSP。張其亮等[15]將PSO算法應(yīng)用于雙向無(wú)等待混合流水車間調(diào)度問(wèn)題，該算法融合工件沖突的檢測(cè)和化解方法，高效地求解了高速磁浮列車調(diào)度問(wèn)題;張志鵬等[16]提出一種遺傳粒子群混合算法，用于求解多目標(biāo)混合流水車間調(diào)度問(wèn)題，該算法將兩個(gè)分支算法產(chǎn)生的最優(yōu)解分別作為彼此的初始因子，增強(qiáng)了算法的進(jìn)化速度;MARICHELVAM等[17]針對(duì)多階段HFSP提出一種改進(jìn)的粒子群算法，該算法引入調(diào)度規(guī)則、構(gòu)造式啟發(fā)式算法以改進(jìn)初始解，同時(shí)結(jié)合變鄰域搜索算法縮短了收斂時(shí)間;ZHOU等[18]針對(duì)兩階段混合流水車間調(diào)度問(wèn)題提出了混合差分進(jìn)化粒子群算法，該算法創(chuàng)造性地融入卡爾曼濾波算法和多級(jí)學(xué)習(xí)策略，以增強(qiáng)全局搜索能力;GOLNESHINI等[19]針對(duì)具有模糊加工時(shí)間和模糊交貨期的不相關(guān)并行機(jī)HFSP提出一種基于聚類的混合遺傳粒子群算法;ROOEINFAR等[20]針對(duì)具有有限緩沖區(qū)和固定間隔預(yù)防性維修的HFSP提出一種混合方法，該方法融合了計(jì)算機(jī)仿真模型、遺傳算法、模擬退火算法和粒子群優(yōu)化算法，以提高搜索質(zhì)量。同其他智能優(yōu)化算法一樣，粒子群算法存在易早熟、容易陷入局部收斂的缺點(diǎn)，因此研究人員常將該算法與其他優(yōu)化算法進(jìn)行混合，以提高其全局搜索能力。

FARHY[21]確立了激素分泌的基本原理，該原理描述了生物體內(nèi)激素的調(diào)節(jié)規(guī)律。激素調(diào)節(jié)規(guī)律具有單調(diào)性和很好的收斂性，但鮮有研究人員嘗試將其與優(yōu)化算法相結(jié)合來(lái)解決調(diào)度問(wèn)題，目前僅找到兩篇相關(guān)文獻(xiàn)。顧文斌等[22]針對(duì)置換流水車間調(diào)度問(wèn)題提出了基于激素調(diào)節(jié)機(jī)制的改進(jìn)型自適應(yīng)粒子群算法，該算法引入了貪婪隨機(jī)自適應(yīng)算法和激素調(diào)節(jié)因子以提高搜索效率;GU等[23]針對(duì)具有運(yùn)輸約束的作業(yè)車間實(shí)時(shí)調(diào)度問(wèn)題提出一種基于生物啟發(fā)的動(dòng)態(tài)調(diào)度優(yōu)化方法。

本文對(duì)PSO算法的改進(jìn)主要體現(xiàn)在以下幾個(gè)方面：①基于NEH啟發(fā)式算法提出了NNEH(new NEH)啟發(fā)式算法，在保證初始種群多樣性的同時(shí)提高了個(gè)體的質(zhì)量；②基于激素調(diào)節(jié)函數(shù)的特性創(chuàng)造性地將其融入慣性因子中，使算法不易早熟，同時(shí)提出相關(guān)系數(shù)法改變了速度更新公式的自身認(rèn)知項(xiàng)和社會(huì)認(rèn)知項(xiàng)，提高了算法的搜索質(zhì)量；③提出一種隨機(jī)拓補(bǔ)結(jié)構(gòu)，將每次迭代過(guò)程的種群最優(yōu)位置改為可變的鄰域最優(yōu)位置，同時(shí)融入GA的基于兩點(diǎn)和位置的兩種交叉操作，以及插入、反轉(zhuǎn)逆序、打亂互換3種變異操作，使算法不易陷入局部最優(yōu)。

針對(duì)以最小化完工時(shí)間為目標(biāo)的HFSP-IPM，本文提出一種改進(jìn)粒子群優(yōu)化(Improved Particle Swarm Optimization, IPSO)算法。首先，設(shè)計(jì)了基于排列的編碼解碼方法；然后，提出了NNEH啟發(fā)式算法用于產(chǎn)生初始種群；接著，基于激素調(diào)節(jié)機(jī)制和相關(guān)系數(shù)法設(shè)計(jì)了一種新的粒子群速度更新改進(jìn)公式；最后，結(jié)合隨機(jī)拓?fù)浣Y(jié)構(gòu)、交叉和變異3種方法，擴(kuò)大了算法的搜索空間。本文應(yīng)用IPSO算法求解CARLIER等[24]提出的經(jīng)典算例，獲得了良好的可行解，驗(yàn)證了所提算法的有效性和優(yōu)越性能。

1 混合流水車間調(diào)度問(wèn)題

1.1 符號(hào)定義

記n為工件總數(shù)，i為工件序號(hào)(i=1,…,n)，s為階段總數(shù)，k為階段序號(hào)(k=1,…,s)，mk為階段k上的并行機(jī)器總數(shù)(mk≥1)，j為機(jī)器序號(hào)，Pik為工件i在階段k的加工時(shí)間，Sik為工件i在階段k的開始加工時(shí)間，Cik為工件i在階段k的加工完成時(shí)間，Mi為工件i的完工時(shí)間，Mmax={M1,M2,…,Mn}為加工任務(wù)的最大完工時(shí)間。

1.2 問(wèn)題描述

HFSP-IPM可描述為：現(xiàn)有n個(gè)工件，s個(gè)加工階段，每個(gè)加工階段有mk臺(tái)并行機(jī)器。要求滿足以下約束條件：①每個(gè)工件在流水線上要以相同的順序依次進(jìn)行各個(gè)階段的加工；②至少有一個(gè)加工階段的并行機(jī)器數(shù)量大于1；③同一工件在同一階段的加工時(shí)間是固定的；④每個(gè)工件在每一階段只能選擇一臺(tái)機(jī)器進(jìn)行加工；⑤一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件。

HFSP-IPM通常有如下假設(shè)：①機(jī)器一旦進(jìn)行加工便不可中斷；②機(jī)器和工件在0時(shí)刻都可被獲得；③所有工件在各個(gè)階段的加工時(shí)間已知；④任意兩個(gè)相鄰加工階段之間的緩沖區(qū)無(wú)限大；⑤不考慮工件在相鄰階段之間的運(yùn)輸時(shí)間以及機(jī)器轉(zhuǎn)換工件的時(shí)間。本文求解以最小化完工時(shí)間為目標(biāo)的HFSP-IPM，即確定各階段的工件加工順序以及對(duì)應(yīng)的機(jī)器分配方案，從而使整個(gè)任務(wù)的最大完工時(shí)間(Mmax)最小。HFSP-IPM的示意圖如圖1所示。

1.3 HFSP-IPM數(shù)學(xué)模型

HFSP-IPM的數(shù)學(xué)模型表述如下：

T=minMmax,

(1)

Mmax≥Cis,i=1,…,n。

(2)

(3)

Yki1i2=

(4)

Cik=Sik+Pik,i=1,…,n;k=1,…,s；

(5)

(6)

Si(k+1)-Sik≥Pik,i=1,…,n;k=1,…,s；

(7)

Yki1i2+Yki2i1≤1,i=1,…,n;k=1,…,s；

(8)

Si1k-Ci2k+L*(3-Yki2i1-Xi1kj-Xi2kj)≥0,

i=1,…,n;i1≠i2;k=1,…,s;j=1,…,mk;

L是一個(gè)足夠大的常數(shù)。

(9)

其中：式(1)是調(diào)度性能指標(biāo)，即本文的適應(yīng)度函數(shù)；式(2)代表整個(gè)加工任務(wù)的總完工時(shí)間大于等于在最后階段任意工件的加工完成時(shí)間；式(3)和式(4)是兩個(gè)變量的0-1變量約束；式(5)是任意工件在任意階段的加工完成時(shí)間表達(dá)式；式(6)代表每個(gè)工件在任意階段均只能在該階段的一臺(tái)機(jī)器上加工；式(7)代表任意工件需完成上一階段的加工才能開始下一階段的加工；式(8)和式(9)代表一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件。

2 粒子群算法

在PSO算法中，優(yōu)化問(wèn)題在D維空間里的每一個(gè)D維解稱為“粒子”[25]，每個(gè)粒子具有位置和速度兩個(gè)屬性，位置代表粒子在搜索空間里的位置，速度代表粒子移動(dòng)的方向和快慢程度。在每次迭代過(guò)程中，粒子根據(jù)速度更新公式和位置更新公式不斷調(diào)整自身的搜索路徑。粒子每完成一次迭代，便根據(jù)適應(yīng)度函數(shù)評(píng)估自身的適應(yīng)度，以此更新個(gè)體最優(yōu)位置pbest和種群最優(yōu)位置gbest。一次次迭代后，便能很快找到問(wèn)題的最優(yōu)解。其中，粒子的速度更新公式和位置更新公式如式(10)和式(11)所示：

Vid(k+1)=w×Vid(k)+c1×r1×(Pid(k)-

Xid(k))+c2×r2×(Pgd(k)-Xid(k))，

(10)

Xid(k+1)=Xid(k)+Vid(k+1)。

(11)

其中：k表示當(dāng)前迭代次數(shù);w表示慣性因子;Vid(k)表示經(jīng)過(guò)k次迭代后第i個(gè)粒子的第d個(gè)變量的速度;c1、c2表示學(xué)習(xí)因子或加速因子;r1、r2表示[0,1]內(nèi)均勻分布的隨機(jī)數(shù);Pid(k)表示經(jīng)過(guò)k次迭代后第i個(gè)粒子自身搜索到的最優(yōu)位置的第d個(gè)變量;Xid(k)表示經(jīng)過(guò)k次迭代后第i個(gè)粒子的第d個(gè)變量的位置;Pgd(k)表示經(jīng)過(guò)k次迭代后種群搜索到的最優(yōu)位置的第d個(gè)變量。

標(biāo)準(zhǔn)PSO算法流程如下：

步驟1初始化粒子群。

步驟2根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)初始粒子的適應(yīng)度,對(duì)每個(gè)粒子的pbest和種群的gbest進(jìn)行初始化。

步驟3根據(jù)速度更新式(10)和位置更新式(11)更新每個(gè)粒子。

步驟4根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度。

步驟5更新pbest。判斷粒子當(dāng)前位置的適應(yīng)度是否優(yōu)于個(gè)體最優(yōu)位置pbest的適應(yīng)度，是則將當(dāng)前位置賦給pbest，否則pbest保持不變。

步驟6更新gbest。判斷粒子當(dāng)前位置的適應(yīng)度是否優(yōu)于種群最優(yōu)位置gbest的適應(yīng)度，是則將當(dāng)前位置賦給gbest，否則gbest保持不變。

步驟7判斷是否滿足迭代終止條件，是則結(jié)束迭代，否則迭代次數(shù)加1，轉(zhuǎn)步驟3。

步驟8輸出種群最優(yōu)位置gbest。

3 基于激素調(diào)節(jié)機(jī)制的IPSO算法

3.1 編碼和解碼

3.1.1 編碼方式

HFSP通常有矩陣編碼[26]和排列編碼兩種編碼方式。矩陣編碼雖然詳細(xì)地列出了每一階段各個(gè)工件對(duì)應(yīng)的加工機(jī)器和工件之間的先后加工順序，但表達(dá)方式太過(guò)繁瑣，不易對(duì)其進(jìn)行操作。相比之下，排列編碼簡(jiǎn)單易行，容易處理，因此本文采用排列編碼作為HFSP-IPM的編碼方法。排列編碼是一種基于操作的編碼方式，即取所有工件序號(hào)進(jìn)行隨機(jī)排列，從而形成一個(gè)個(gè)體，個(gè)體的長(zhǎng)度等于待加工的工件數(shù)n，工件在個(gè)體中的位置代表工件在第一階段的加工順序。例如，對(duì)于具有6個(gè)待加工工件的HFSP-IPM，取P1={3,1,5,4,2,6}，則個(gè)體P1表示在第一階段先加工工件3，然后依次對(duì)工件1,5,4,2,6進(jìn)行加工。

3.1.2 解碼方式

HFSP通常有兩種置換解碼和排列解碼解碼方式。本文基于排列解碼提出以下解碼方法來(lái)構(gòu)造HFSP-IPM的調(diào)度方案：

(1)在工件排序方面，在第一階段按照給定的加工序列對(duì)工件進(jìn)行加工，在后續(xù)階段里，按照先到先加工的原則對(duì)工件進(jìn)行加工，即在階段k(k>1)，先按照階段k-1的完工時(shí)間進(jìn)行升序排列，得到階段k的加工序列，然后按照新的加工序列對(duì)各個(gè)工件進(jìn)行加工。研究發(fā)現(xiàn)，工件需要完成所有工序的剩余時(shí)間越多，該工件對(duì)整個(gè)任務(wù)完工的影響越大，對(duì)其進(jìn)行先加工能夠減小任務(wù)的總完工時(shí)間。因此，若存在多個(gè)工件在上階段的完工時(shí)間相同，則計(jì)算其剩余完工時(shí)間，將剩余完工時(shí)間進(jìn)行降序排列，得到這些工件的加工序列。若剩余完工時(shí)間仍然一樣，則這些工件之間進(jìn)行隨機(jī)排列。

3.2 種群初始化

初始化種群時(shí)既要考慮到種群內(nèi)個(gè)體的質(zhì)量，又要考慮到種群的多樣性。NAWAZ等[27]提出的NEH啟發(fā)式算法被認(rèn)為是解決以最小化完工時(shí)間為目標(biāo)的流水車間排序問(wèn)題的最好的啟發(fā)式算法，近些年，研究人員嘗試將NEH啟發(fā)式算法用于HFSP并取得了良好的效果[10]。NEH啟發(fā)式算法的提出基于以下假設(shè)：對(duì)于完成所有工序的加工，具有更多總加工時(shí)間的工件應(yīng)被賦予比具有較少總加工時(shí)間的工件更高的加工優(yōu)先級(jí)。因此，本文提出一種NNEH啟發(fā)式算法用以生成HFSP-IPM的初始種群，具體步驟如下：

步驟1計(jì)算所有工件完成各自所有工序加工所需要的總加工時(shí)間，然后根據(jù)總加工時(shí)間對(duì)工件進(jìn)行降序排列，對(duì)于部分總加工時(shí)間相同的工件，它們之間進(jìn)行隨機(jī)排列，從而得到工件序列W。

步驟2從工件序列W中選擇前兩個(gè)工件，通過(guò)計(jì)算兩個(gè)可能序列的完工時(shí)間來(lái)找到這兩個(gè)工件的最佳序列，即完工時(shí)間較小的序列，將其加入到加工序列P中，并將這兩個(gè)工件從工件序列W中刪除。

步驟3隨機(jī)選取工件序列W中的一個(gè)工件，然后遍歷加工序列P中的每一個(gè)可插入位置，找到最佳插入位置，即計(jì)算工件插入每一個(gè)可插入位置時(shí)加工序列P的完工時(shí)間，選擇完工時(shí)間最小的位置，并將該工件從工件序列W中刪除。

步驟4從工件序列W中選擇第一個(gè)工件，將其隨機(jī)插入到當(dāng)前加工序列P中，并將其從工件序列W中刪除。

步驟5重復(fù)步驟3和步驟4，直至所有工件插入完成，形成一個(gè)個(gè)體。

步驟6重復(fù)執(zhí)行以上步驟n遍，形成規(guī)模為n的初始種群。

上述步驟中，步驟1和步驟2保證個(gè)體的質(zhì)量，步驟3和步驟4保證種群的多樣性，然后NNEH啟發(fā)式算法通過(guò)多次循環(huán)從而產(chǎn)生HFSP-IPM的初始種群。

3.3 速度更新公式的改進(jìn)

3.3.1 基于激素調(diào)節(jié)機(jī)制的慣性因子設(shè)計(jì)

生物的體液環(huán)境中存在許多腺體，這些腺體可以分泌和擴(kuò)散激素，并且它們會(huì)與相應(yīng)的激素發(fā)生化學(xué)反應(yīng)。如圖2所示，腺體“A”在外界刺激下分泌激素“a”，并向外部體液環(huán)境釋放，在激素“a”的刺激下，腺體“B”分泌激素“ab”和自分泌激素“b”，然后，腺體“B”將它們反饋給腺體“A”，形成一個(gè)循環(huán)過(guò)程。

激素調(diào)節(jié)機(jī)制符合Hill函數(shù)，Hill函數(shù)由上升函數(shù)(Fup)和下降函數(shù)(Fdown)組成，如式(12)所示。

(12)

式中：X為激素濃度變量，即自變量；n為Hill系數(shù)，n≥1；T為激素濃度閾值，T>0，n和T決定函數(shù)曲線的斜率。Hill函數(shù)的變化曲線如圖3所示。

生物體內(nèi)的激素分泌有如下4個(gè)特點(diǎn)：①微量高效；②通過(guò)體液運(yùn)輸；③特異性；④協(xié)同與拮抗作用。第④點(diǎn)尤其重要，在內(nèi)分泌系統(tǒng)中，不同激素對(duì)同一腺體有協(xié)同和拮抗作用。例如，胰腺可以分泌胰高血糖素和胰島素，胰高血糖素能夠提高人體血糖濃度，胰島素能夠降低人體血糖濃度。當(dāng)人體血糖水平較低時(shí)，胰高血糖素的分泌量增加，以提高人體血糖濃度。但隨著人體血糖濃度的升高，胰島素的分泌量會(huì)逐漸增加，使人體血糖濃度不會(huì)提升過(guò)高。以此種方式，人體的血糖濃度始終維持在正常的水準(zhǔn)。由此可以看出，激素的分泌具有維持生物機(jī)體內(nèi)外環(huán)境穩(wěn)定的功能，激素調(diào)節(jié)機(jī)制即Hill函數(shù)具有單調(diào)性和非負(fù)性，并且能夠很好地收斂。

在PSO算法的設(shè)計(jì)中，慣性因子w一般取線性函數(shù)或常函數(shù)，但這種設(shè)計(jì)通常會(huì)使PSO算法陷入局部最優(yōu)。根據(jù)對(duì)標(biāo)準(zhǔn)PSO算法的描述，慣性因子w是繼承原來(lái)速度的系數(shù)，決定著粒子的步長(zhǎng)，一般在算法運(yùn)行前期，設(shè)置較大的w使粒子具有較強(qiáng)的全局尋優(yōu)能力，到算法運(yùn)行后期，使w逐漸減小，加快算法的收斂速度，因此設(shè)置慣性因子w為減函數(shù)。關(guān)于將慣性因子w設(shè)為何種減函數(shù)，從而使PSO算法能夠獲得更好的解，有學(xué)者做了專門的研究，研究結(jié)果如圖4所示。

由圖4可知，當(dāng)慣性因子w為凹型減函數(shù)時(shí)，PSO算法能夠在更短的時(shí)間內(nèi)獲得更好的解。而根據(jù)對(duì)生物體內(nèi)的激素調(diào)節(jié)機(jī)制的描述可知，生物體內(nèi)的激素調(diào)節(jié)機(jī)制即Hill函數(shù)是一種凹函數(shù)且在正數(shù)區(qū)域內(nèi)呈遞減趨勢(shì)，具有單調(diào)性和非負(fù)性，有著很好的收斂性質(zhì)。因此，將Hill函數(shù)用于式(10)中的慣性因子w上，粒子在解空間的探索過(guò)程便能夠得到很好的控制。由此得出，基于生物體內(nèi)的激素調(diào)節(jié)機(jī)制的慣性因子w如下：

(13)

式中：k表示當(dāng)前迭代次數(shù)；w(k)表示第k次迭代的慣性因子；wmax表示慣性因子的最大值；wmin表示慣性因子的最小值；T表示閾值(T>0)；n表示Hill系數(shù)(n≥1)；w0表示慣性因子的初始值。

3.3.2 相關(guān)系數(shù)法

HO等[28]指出PSO算法在自身認(rèn)知項(xiàng)(即c1×r1)和社會(huì)認(rèn)知項(xiàng)(即c2×r2)是隨機(jī)而又獨(dú)立存在的，自身認(rèn)知項(xiàng)調(diào)節(jié)粒子向個(gè)體最優(yōu)粒子飛行的步長(zhǎng)，社會(huì)認(rèn)知項(xiàng)調(diào)節(jié)粒子向全局最優(yōu)粒子飛行的步長(zhǎng)，這兩項(xiàng)對(duì)PSO算法的搜索能力具有重要影響?；谠撍枷耄疚牟捎孟嚓P(guān)系數(shù)法，將原來(lái)式(10)中的c1×r1變?yōu)?1-r2)×c1×r1，c2×r2變?yōu)?1-r2)×c2×(1-r1)，以提高PSO算法的搜索質(zhì)量。

3.3.3 改進(jìn)的速度更新公式

綜合基于激素調(diào)節(jié)機(jī)制的慣性因子設(shè)計(jì)和相關(guān)系數(shù)法，改進(jìn)的速度更新公式如式(14)所示：

Vid(k)+(1-r2)×c1×r1×(Pid(k)-Xid(k))+

(1-r2)×c2×(1-r1)×(Pgd(k)-Xid(k))。

(14)

3.4 隨機(jī)拓?fù)浣Y(jié)構(gòu)

PSO算法有全局版本(Global version PSO, GPSO)和局部版本(Local version PSO, LPSO)兩個(gè)范式。這兩個(gè)范式的區(qū)別在于粒子所處的“社會(huì)”不同。在GPSO中，粒子所處的“社會(huì)”是整個(gè)種群，即粒子在每次迭代過(guò)程中所涉及的種群最優(yōu)位置gbest是整個(gè)種群的最優(yōu)位置。而在LPSO中，粒子所處的“社會(huì)”僅是一個(gè)鄰域，即粒子在每次迭代過(guò)程中會(huì)用個(gè)體最優(yōu)位置pbest和鄰域最優(yōu)位置lbest(粒子所處鄰域中最好的位置)作為更新的向?qū)?。由此可?jiàn)，LPSO每次迭代所用作更新向?qū)У奈恢靡菺PSO多。因此，LPSO跳出局部極值的可能性更大，在處理復(fù)雜問(wèn)題上往往能夠表現(xiàn)出比GPSO更好的性能?？紤]到HFSP-IPM是復(fù)雜的NP-Hard問(wèn)題，因此本文基于LPSO提出一種隨機(jī)拓?fù)浣Y(jié)構(gòu)。

隨機(jī)拓?fù)浣Y(jié)構(gòu)為每個(gè)粒子定義一個(gè)規(guī)模為Z的鄰域，該鄰域是由從整個(gè)種群中隨機(jī)挑選出的Z個(gè)粒子(包括粒子本身)所組成的。在每次迭代過(guò)程中，粒子根據(jù)個(gè)體最優(yōu)位置pbest和鄰域最優(yōu)位置lbest進(jìn)行更新。若迭代過(guò)后，鄰域最優(yōu)位置lbest得到了改善，則粒子的鄰域不會(huì)發(fā)生改變，并在下一次迭代中繼續(xù)沿用；若迭代過(guò)后，鄰域最優(yōu)位置lbest沒(méi)有得到改善，則粒子的鄰域?qū)⒃谙乱淮蔚羞M(jìn)行重新構(gòu)造。因此，式(14)中的Pgd(k)變成表示經(jīng)過(guò)k次迭代后鄰域搜索到的最優(yōu)位置的第d個(gè)變量。以此種隨機(jī)拓?fù)浣Y(jié)構(gòu)來(lái)增強(qiáng)PSO算法的全局尋優(yōu)能力，提高算法的性能。

3.5 交叉和變異

3.5.1 交叉算子

在IPSO算法中，交叉算子的作用在于通過(guò)對(duì)兩個(gè)粒子進(jìn)行交叉操作，可能得到更為優(yōu)異的兩個(gè)粒子，增大算法的搜索空間，提高算法的全局尋優(yōu)能力。本文采用基于兩點(diǎn)的交叉和基于位置的交叉兩種交叉算子。

(1)基于兩點(diǎn)的交叉

基于兩點(diǎn)的交叉具體步驟如下：

步驟1隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，將兩個(gè)交叉點(diǎn)之間的片段稱為“交叉片段”，然后將兩個(gè)父代粒子(P1,P2)的交叉片段復(fù)制到子代粒子(C2,C1)中。

步驟2刪除父代粒子(P1,P2)與子代粒子(C1,C2)維度值相同的維度

步驟3根據(jù)從左到右的順序?qū)⒏复Ｗ?P1,P2)剩余維度上的維度值依次填入子代粒子(C1,C2)余下的空位里。

以8個(gè)待加工工件為例，父代粒子(P1,P2)分別為{14576283}和{54786231}，選中交叉點(diǎn)為3和6，則復(fù)制過(guò)后子代粒子(C1,C2)分別為{XX7862XX}和{XX5762XX}，刪除過(guò)后父代粒子(P1,P2)分別為{145XXXX3}和{X4X8XX31}，填入過(guò)后子代粒子(C1,C2)最終分別為{14786253}和{48576231}。

(2)基于位置的交叉

基于位置的交叉具體步驟如下：

步驟1隨機(jī)產(chǎn)生一些交叉點(diǎn)，將父代粒子(P1,P2)在交叉點(diǎn)上的維度值復(fù)制到子代粒子(C2,C1)對(duì)應(yīng)的維度上。

步驟2刪除父代粒子(P1,P2)與子代粒子(C1,C2)維度值相同的維度。

步驟3根據(jù)從左到右的順序?qū)⒏复Ｗ?P1,P2)剩余維度上的維度值依次填入子代粒子(C1,C2)余下的空位里。

以8個(gè)待加工工件為例，父代粒子(P1,P2)分別為{14576283}和{54786231}，選中交叉點(diǎn)為1、3、6、7，則復(fù)制過(guò)后子代粒子(C1,C2)分別為{5X7XX23X}和{1X5XX28X}，刪除過(guò)后父代粒子(P1,P2)分別為{14XX6X8X}和{X47X6X3X}，填入過(guò)后子代粒子(C1,C2)最終分別為{51746238}和{14576283}。

進(jìn)行交叉操作時(shí)，IPSO算法隨機(jī)采用上述兩種交叉算子，即生成一個(gè)值為0或1的隨機(jī)數(shù)Cr。當(dāng)Cr=0時(shí)，采用基于兩點(diǎn)的交叉；當(dāng)Cr=1時(shí)，采用基于位置的交叉。

3.5.2 變異算子

在IPSO算法中，變異算子的作用在于通過(guò)變異操作打亂舊粒子，產(chǎn)生新粒子，從而改善算法局部的隨機(jī)搜索能力。本文采用插入、反轉(zhuǎn)逆序和打亂互換3種變異算子。

(1)插入

基于插入的變異方法是首先隨機(jī)選中一個(gè)維度，然后將其隨機(jī)插入到另一個(gè)維度的前面，從而形成新的粒子。例如，父代粒子P1為{14576283}，首先選中維度5，將其插入到維度2前面，則子代粒子C1為{16457283}。

(2)反轉(zhuǎn)逆序

反轉(zhuǎn)逆序方法是首先選中兩個(gè)維度，然后對(duì)兩個(gè)維度間的片段進(jìn)行反轉(zhuǎn)逆序。例如，父代粒子P1為{14576283}，選中維度2和5，則子代粒子C1為{16754283}。

(3)打亂互換

打亂互換方法是首先隨機(jī)選中一些維度，然后將這些維度打亂互換。例如，父代粒子P1為{14576283}，首先選中維度1、3、5、8，此時(shí)維度值的順序是“1563”，打亂后的順序是“6351”，則子代粒子C1為{64375281}。

進(jìn)行變異操作時(shí)，IPSO算法隨機(jī)采用上述3種變異算子，即生成一個(gè)在[1,3]的隨機(jī)整數(shù)Mu。當(dāng)Mu=1時(shí)，采用基于插入的變異；當(dāng)Mu=2時(shí)，采用反轉(zhuǎn)逆序；當(dāng)Mu為3時(shí)，采用打亂互換。

3.6 算法流程

根據(jù)上述設(shè)計(jì)，給出求解HFSP-IPM的IPSO算法的流程圖，如圖5所示。

本文解決以最小化總完工時(shí)間為目標(biāo)的HFSP-IPM的IPSO算法的具體步驟如下：

步驟1確定各種參數(shù)、編碼解碼方式和適應(yīng)度函數(shù)。預(yù)先設(shè)定種群規(guī)模、迭代次數(shù)、改進(jìn)的速度更新公式參數(shù)、鄰域規(guī)模Z、交叉概率Pc、變異概率Pm、編碼解碼方式和適應(yīng)度函數(shù)。

步驟2初始化種群。利用NNEH啟發(fā)式算法生成初始粒子群。

步驟3定義每個(gè)粒子的鄰域，初始化pbest和lbest。構(gòu)造每個(gè)粒子的鄰域，并根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度，從而對(duì)每個(gè)粒子的個(gè)體最優(yōu)位置pbest和鄰域最優(yōu)位置lbest進(jìn)行初始化。

步驟4根據(jù)改進(jìn)的速度更新公式(14)和位置更新公式(11)更新每個(gè)粒子。

步驟5交叉操作。給每個(gè)粒子一個(gè)隨機(jī)數(shù)，將隨機(jī)數(shù)與交叉概率Pc進(jìn)行比較，若隨機(jī)數(shù)小于Pc，則鎖定粒子；若隨機(jī)數(shù)大于等于Pc，則保留粒子。待掃描完整個(gè)種群，對(duì)鎖定的粒子進(jìn)行基于兩種交叉算子的交叉操作，即生成一個(gè)值為0或1的隨機(jī)數(shù)Cr，當(dāng)Cr=0時(shí)，采用基于兩點(diǎn)的交叉，當(dāng)Cr=1時(shí)，采用基于位置的交叉。

步驟6變異操作。給每個(gè)粒子一個(gè)隨機(jī)數(shù)，將隨機(jī)數(shù)與變異概率Pm進(jìn)行比較，若隨機(jī)數(shù)小于Pm，則鎖定粒子；若隨機(jī)數(shù)大于等于Pm，則保留粒子。待掃描完整個(gè)種群，對(duì)鎖定的粒子進(jìn)行基于三種變異算子的變異操作，即生成一個(gè)在[1,3]的隨機(jī)整數(shù)Mu，當(dāng)Mu=1時(shí)，采用基于插入的變異，當(dāng)Mu=2時(shí)，采用反轉(zhuǎn)逆序，當(dāng)Mu=3時(shí)，采用打亂互換。

步驟7根據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度。

步驟8更新pbest、lbest和判斷是否重新構(gòu)造鄰域。逐個(gè)掃描每個(gè)粒子，若粒子當(dāng)前適應(yīng)度優(yōu)于pbest的適應(yīng)度，則將粒子當(dāng)前位置賦給pbest，否則pbest不變；若粒子當(dāng)前適應(yīng)度優(yōu)于lbest的適應(yīng)度，則將粒子當(dāng)前位置賦給lbest，否則重新構(gòu)造該粒子的鄰域，更新lbest。

步驟9判斷是否滿足迭代終止條件，是則結(jié)束迭代，否則轉(zhuǎn)步驟4，進(jìn)行新一輪的迭代。

步驟10對(duì)各個(gè)粒子的lbest進(jìn)行比較，從而確定種群最優(yōu)位置gbest，并輸出對(duì)應(yīng)的調(diào)度方案。

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

以Visual Studio 2015為開發(fā)環(huán)境，以C++為編程語(yǔ)言，算法在Intel Core i5-6200U、內(nèi)存為8 GB的筆記本電腦上運(yùn)行。IPSO算法的實(shí)驗(yàn)參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)

為驗(yàn)證本文所提出的IPSO算法的性能，開展以下對(duì)比實(shí)驗(yàn)：

(1)NNEH啟發(fā)式算法對(duì)比實(shí)驗(yàn)。對(duì)比采用NNEH啟發(fā)式算法產(chǎn)生初始種群和采用隨機(jī)策略產(chǎn)生初始種群所得到的解的質(zhì)量，為客觀評(píng)價(jià)NNEH啟發(fā)式算法產(chǎn)生的初始種群的質(zhì)量提供依據(jù)。

(2)速度更新公式對(duì)比實(shí)驗(yàn)。對(duì)比PSO算法通過(guò)采用改進(jìn)的速度更新公式和采用原始的速度更新公式分別得到的解的質(zhì)量，為客觀評(píng)價(jià)改進(jìn)的速度更新公式對(duì)算法整體性能的提升提供依據(jù)。

(3)標(biāo)準(zhǔn)算例對(duì)比實(shí)驗(yàn)。選取CARLIER等[24]提出的經(jīng)典算例進(jìn)行測(cè)試，將IPSO算法與其他幾種算法進(jìn)行比較，為客觀評(píng)價(jià)IPSO算法的性能提供依據(jù)。

在4.3節(jié)和4.4節(jié)中，對(duì)每次實(shí)驗(yàn)均測(cè)試5次，所涉及的數(shù)據(jù)均取5次結(jié)果中的最優(yōu)值。

4.2 NNEH啟發(fā)式算法對(duì)比實(shí)驗(yàn)

為驗(yàn)證NNEH啟發(fā)式算法對(duì)初始種群的質(zhì)量的影響，本文進(jìn)行了NNEH啟發(fā)式算法對(duì)比實(shí)驗(yàn)。選取CARLIER等[24]提出的經(jīng)典算例中的j10c5c1問(wèn)題進(jìn)行實(shí)驗(yàn)，其中第1個(gè)字母“j”代表工件，第2個(gè)字母“c”代表階段，第3個(gè)字母“c”代表并行機(jī)的布局方式，通常還有“a”、“b”、“d”、“e”等。因此，“j10c5c1”代表有10個(gè)待加工工件，5個(gè)加工階段，中間階段有兩臺(tái)可選機(jī)器，其余階段各有3臺(tái)可選機(jī)器的第一個(gè)問(wèn)題。將NNEH啟發(fā)式算法和隨機(jī)策略兩種產(chǎn)生初始種群的方法進(jìn)行對(duì)比，以j10c5c1問(wèn)題為例進(jìn)行20次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 NNEH啟發(fā)式算法對(duì)比實(shí)驗(yàn)

在表2中：X表示NNEH啟發(fā)式算法產(chǎn)生的初始種群的最小完工時(shí)間，Y表示隨機(jī)策略產(chǎn)生的初始種群的最小完工時(shí)間，Xa表示NNEH啟發(fā)式算法產(chǎn)生的初始種群的平均完工時(shí)間，Ya表示隨機(jī)策略產(chǎn)生的初始種群的平均完工時(shí)間。通過(guò)表2可以看出，在20次實(shí)驗(yàn)中，X的平均值為69.25，Y的平均值為75.05，因此NNEH啟發(fā)式算法產(chǎn)生的初始種群最優(yōu)解的平均質(zhì)量?jī)?yōu)于隨機(jī)策略產(chǎn)生的初始種群最優(yōu)解的平均質(zhì)量；Xa的平均值為73.20，Ya的平均值為83.32，因此NNEH啟發(fā)式算法產(chǎn)生的初始種群的平均質(zhì)量?jī)?yōu)于隨機(jī)策略產(chǎn)生的初始種群的平均質(zhì)量。由NNEH啟發(fā)式算法對(duì)比實(shí)驗(yàn)可以證明，在產(chǎn)生初始種群方面，NNEH啟發(fā)式算法的性能優(yōu)于隨機(jī)策略。

4.3 速度更新公式對(duì)比實(shí)驗(yàn)

為驗(yàn)證改進(jìn)的速度更新公式對(duì)算法性能的影響，本文進(jìn)行了速度更新公式對(duì)比實(shí)驗(yàn)。選取CARLIER等[24]提出的經(jīng)典算例中的j10c5c1問(wèn)題進(jìn)行實(shí)驗(yàn)，將PSO算法通過(guò)采用改進(jìn)的速度更新公式和采用原始的速度更新公式分別得到的解進(jìn)行對(duì)比，進(jìn)行20次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 速度更新公式對(duì)比實(shí)驗(yàn)

在表3中：Sg表示采用改進(jìn)的速度更新公式的PSO算法得到的最優(yōu)解，Sy表示采用原始的速度更新公式的PSO算法得到的最優(yōu)解。通過(guò)表3可以看出，在20次實(shí)驗(yàn)中，Sg的平均值為69.1，Sy的平均值為70.25，采用改進(jìn)的速度更新公式的PSO算法得到的最優(yōu)解的平均質(zhì)量?jī)?yōu)于采用原始的速度更新公式的PSO算法得到的最優(yōu)解的平均質(zhì)量。由速度更新公式對(duì)比實(shí)驗(yàn)可以證明，采用改進(jìn)的速度更新公式能夠提高算法的搜索質(zhì)量。

4.4 標(biāo)準(zhǔn)算例實(shí)驗(yàn)

為驗(yàn)證本文所提IPSO算法在解決HFSP-IPM上的優(yōu)越性能，下面采用IPSO算法在CARLIER等[24]提出的經(jīng)典算例中的36個(gè)算例上進(jìn)行測(cè)試，并與遺傳算法(GA)[29]、PSO[30]和人工免疫系統(tǒng)(Artificial Immune System, AIS)[31]三種算法進(jìn)行比較。對(duì)比結(jié)果如表4～表6所示。

表4 基于j10c5-算例的4種算法對(duì)比結(jié)果

續(xù)表4

表5 基于j10c10-算例的4種算法對(duì)比結(jié)果

表6 基于j15c5-算例的4種算法對(duì)比結(jié)果

由表4～表6可以看出，IPSO算法在求解HFSP-IPM上優(yōu)于其余3種算法。在表4中，GA、PSO、IPSO求出了12個(gè)目前最好的最優(yōu)解，AIS求出了11個(gè)目前最好的最優(yōu)解，因此在12個(gè)j10c5-算例上，GA、PSO、IPSO的性能相當(dāng)，且都優(yōu)于AIS；在表5中，IPSO求出了7個(gè)目前最好的最優(yōu)解，GA、PSO、AIS求出了6個(gè)目前最好的最優(yōu)解，且對(duì)于12個(gè)j10c10-算例，GA的平均偏差為4.17%，PSO的平均偏差為4.17%，AIS的平均偏差為4.39%，IPSO的平均偏差為4.03%，因此在12個(gè)j10c10-算例上，IPSO性能最優(yōu)，其次是GA和PSO，AIS性能最劣；在表6中，IPSO求出了7個(gè)目前最好的最優(yōu)解，PSO求出了6個(gè)目前最好的最優(yōu)解，GA、AIS求出了5個(gè)目前最好的最優(yōu)解，且對(duì)于12個(gè)j15c5-算例，GA的平均偏差為6.25%，PSO的平均偏差為5.70%，AIS的平均偏差為6.13%，IPSO的平均偏差為5.59%，因此在12個(gè)j15c5-算例上，IPSO性能最優(yōu)，其次是PSO，然后是AIS，GA性能最劣。由此可知，IPSO算法求出的目前最好的最優(yōu)解多于其他3種算法，證明了本文提出的IPSO算法在求解HFSP-IPM上具有良好的性能。如圖6所示為算例j15c5c2的甘特圖。

綜上所述，本文所提IPSO算法在解決HFSP-IPM上具有良好的效果，首先NNEH啟發(fā)式算法提供了高質(zhì)量且多樣化的初始種群，然后對(duì)速度更新公式進(jìn)行改進(jìn)，使算法具有良好的收斂性質(zhì)，最后將隨機(jī)拓?fù)浣Y(jié)構(gòu)、交叉和變異三者結(jié)合，擴(kuò)大算法的搜索空間，使算法不易陷入局部收斂，從而提高算法在解空間的搜索性能。

5 結(jié)束語(yǔ)

本文提出了一種基于激素調(diào)節(jié)機(jī)制的改進(jìn)粒子群(IPSO)算法，用于求解以最小化完工時(shí)間為目標(biāo)的相同并行機(jī)HFSP。根據(jù)混合流水車間調(diào)度問(wèn)題的特點(diǎn)，提出了基于排列的編碼解碼方式，然后設(shè)計(jì)了NNEH啟發(fā)式算法用于產(chǎn)生高質(zhì)量的初始種群。在IPSO算法中，首先基于激素調(diào)節(jié)機(jī)制和相關(guān)系數(shù)法對(duì)速度更新公式進(jìn)行了改進(jìn)，提高了算法的搜索質(zhì)量，然后提出了隨機(jī)拓?fù)浣Y(jié)構(gòu)將迭代過(guò)程中的種群最優(yōu)位置換為可變的鄰域最優(yōu)位置，使得算法不易陷入局部最優(yōu)，最后隨機(jī)采用基于兩點(diǎn)和位置的兩種交叉算子，以及插入、反轉(zhuǎn)逆序、打亂互換3種變異算子產(chǎn)生新粒子，擴(kuò)大了算法的搜索范圍。通過(guò)兩項(xiàng)對(duì)比實(shí)驗(yàn)，證明了NNEH啟發(fā)式算法和改進(jìn)的速度更新公式均能夠改善算法的搜索性能。通過(guò)標(biāo)準(zhǔn)算例對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文所提改進(jìn)粒子群算法的優(yōu)越性。未來(lái)將繼續(xù)優(yōu)化該算法，嘗試獲得更好的最優(yōu)解，或?qū)⒃撍惴ㄓ糜诙嗄繕?biāo)混合流水車間調(diào)度問(wèn)題上。