羅函明，羅天洪，吳曉東，陳科百

1.重慶交通大學(xué) 機(jī)電與車(chē)輛工程學(xué)院，重慶400074

2.重慶文理學(xué)院 智能制造工程學(xué)院，重慶402160

1 引言

車(chē)間調(diào)度問(wèn)題是指在有限的資源條件下，如何合理地安排車(chē)間生產(chǎn)任務(wù)，以滿足或優(yōu)化一個(gè)或多個(gè)性能指標(biāo)。該問(wèn)題的性能指標(biāo)種類繁多，如常用的生產(chǎn)效率指標(biāo)[1]和近年來(lái)提出的綠色化指標(biāo)[2]。混合流水車(chē)間是一種常見(jiàn)的流水作業(yè)生產(chǎn)車(chē)間，具備一般流水車(chē)間和并行機(jī)車(chē)間的特點(diǎn)，生產(chǎn)過(guò)程柔性化，更符合生產(chǎn)實(shí)際情況?；旌狭魉?chē)間調(diào)度問(wèn)題（Hybrid Flow-shop Scheduling Problem，HFSP），也稱為柔性流水車(chē)間調(diào)度問(wèn)題（Flexible Flow-shop Scheduling Problem，F(xiàn)FSP），在電子、物流及互聯(lián)網(wǎng)服務(wù)等現(xiàn)代行業(yè)都有著十分廣泛的應(yīng)用，可追溯到機(jī)械、化工、紡織、制藥等傳統(tǒng)行業(yè)。HFSP是一種NP-hard 組合優(yōu)化問(wèn)題[3]，不可能在多項(xiàng)式時(shí)間內(nèi)精確求得最優(yōu)解，解決該問(wèn)題的最佳方法是采用元啟發(fā)式算法。因此，對(duì)HFSP 的研究具有重要的實(shí)際應(yīng)用價(jià)值和理論研究?jī)r(jià)值。

與一般流水車(chē)間調(diào)度問(wèn)題相比，HFSP 在各道工序中存在并行機(jī)，需要同時(shí)確定工件排序和機(jī)器分配。按并行機(jī)類型的不同，HFSP可分為三類[1]：均勻并行機(jī)，指工件每道工序在任意一臺(tái)并行機(jī)上的加工時(shí)間與其加工速度成反比；相同并行機(jī)，指工件每道工序在任意一臺(tái)并行機(jī)上的加工時(shí)間相同；不相關(guān)并行機(jī)，指工件每道工序在任意一臺(tái)并行機(jī)上的加工時(shí)間互不相關(guān)，有所不同。不相關(guān)并行機(jī)上的加工時(shí)間取決于工件與機(jī)器的適配程度，更符合實(shí)際生產(chǎn)，同時(shí)，加工時(shí)間的互不相關(guān)性加大了求解難度，因此本文研究的是不相關(guān)并行機(jī)HFSP。

本文研究目的是針對(duì)HFSP的特性來(lái)設(shè)計(jì)一種有效的元啟發(fā)式算法，以求解該類問(wèn)題，并提高解的質(zhì)量和穩(wěn)定性。

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

HFSP 的求解方法有精確計(jì)算、啟發(fā)式規(guī)則和元啟發(fā)式算法[4]。相對(duì)于精確計(jì)算求解時(shí)間過(guò)長(zhǎng)，啟發(fā)式規(guī)則難以獲得全局最優(yōu)解，元啟發(fā)式算法運(yùn)算速度快，所得解質(zhì)量好，因而運(yùn)用廣泛，如遺傳算法（Genetic Algorithm，GA）、模擬退火算法、禁忌搜索算法，新興的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）[5]、蟻群優(yōu)化算法[6]、蝙蝠算法[7]和混合蛙跳算法[8]等。王凌等[1]針對(duì)不相關(guān)并行機(jī)HFSP 提出了人工蜂群算法，采用基于多操作的鄰域搜索和隨機(jī)搜索，通過(guò)實(shí)例驗(yàn)證了該算法求解HFSP 的有效性。王圣堯等[9]建立了HFSP 解空間的概率模型，進(jìn)而提出了一種分布估計(jì)算法，對(duì)HFSP有著較快的求解速度。崔琪等[10]針對(duì)相同并行機(jī)HFSP提出一種變鄰域改進(jìn)遺傳算法，采用NEH 啟發(fā)式算法產(chǎn)生初始種群，設(shè)計(jì)兩種交叉算子提高算法搜索效率。Bozorgirad等[11]提出將三種基于禁忌搜索及三種基于模擬退火的局部搜索算法與兩種基于遺傳算法的種群算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果表明基于種群的算法比局部搜索算法在求解HFSP 時(shí)得到的解質(zhì)量更優(yōu)。Santosa 等[12]針對(duì)有限等待區(qū)間HFSP，提出了一種多目標(biāo)離散粒子群優(yōu)化算法。Azami等[13]針對(duì)航空航天復(fù)合材料制造系統(tǒng)中的兩階段HFSP，提出一種新的啟發(fā)式規(guī)則生成遺傳算法的初始種群，并在算法中設(shè)計(jì)了一種新的交叉算子。雖然對(duì)于HFSP 的求解算法已有大量研究，但是大多算法都沿用了一般流水車(chē)間調(diào)度的求解方法，即基于工件排列的編碼方法以及基于工件先到先加工和最先空閑機(jī)器規(guī)則的解碼方法。這種解碼方法易導(dǎo)致算法早熟，因此王芳等[14]設(shè)計(jì)了一種混合隨機(jī)概率與規(guī)則解碼方法（簡(jiǎn)稱隨機(jī)規(guī)則解碼），擴(kuò)大搜索空間，阻止算法早熟，但該方法并沒(méi)有根據(jù)HFSP的特性來(lái)設(shè)計(jì)，還有待改進(jìn)和提高解的質(zhì)量。

布谷鳥(niǎo)搜索（Cuckoo Search，CS）算法是由Yang等[15]于2009 年提出的一種新型元啟發(fā)式算法，有著算法結(jié)構(gòu)簡(jiǎn)單、控制參數(shù)少、尋優(yōu)能力強(qiáng)和易于結(jié)合其他算法進(jìn)行改進(jìn)等優(yōu)點(diǎn)，已被成功應(yīng)用于多種工程優(yōu)化領(lǐng)域[16-18]。然而，CS算法應(yīng)用于求解HFSP的研究較少。Burnwal等[19]基于CS算法求解以最小化延期懲罰成本和最大化機(jī)器利用率為目標(biāo)的HFSP，經(jīng)仿真驗(yàn)證了CS算法性能優(yōu)于GA、PSO 算法；Marichelvam 等[20]通過(guò)NEH 啟發(fā)式規(guī)則生成HFSP的初始解，提高了CS算法的收斂速度；Han等[21]針對(duì)HFSP設(shè)計(jì)了自適應(yīng)CS算法，并加強(qiáng)了算法跳出極值的能力。文獻(xiàn)調(diào)研表明，CS 算法在求解調(diào)度類問(wèn)題時(shí)，大多數(shù)文獻(xiàn)都是基于某種排序映射規(guī)則將CS 算法產(chǎn)生的連續(xù)解轉(zhuǎn)換為離散解。該方法不能將連續(xù)解空間中全局搜索和局部搜索之間的關(guān)系有效地轉(zhuǎn)換到離散解空間，削弱了CS 算法優(yōu)越的尋優(yōu)能力。針對(duì)該方法的缺陷，陳飛躍等[22]為求解帶阻塞有差速的HFSP，提出了一種基于交叉策略的離散萊維飛行，但這種交叉策略容易產(chǎn)生不可行調(diào)度解，尋優(yōu)能力還有待加強(qiáng)。

為更好地求解不相關(guān)并行機(jī)HFSP，基于上述研究，本文所做的研究改進(jìn)有：（1）設(shè)計(jì)了一種改進(jìn)的隨機(jī)規(guī)則解碼方法，即基于工件數(shù)與并行機(jī)數(shù)，按概率隨機(jī)分配機(jī)器，提高了解的質(zhì)量；（2）根據(jù)標(biāo)準(zhǔn)布谷鳥(niǎo)算法中萊維飛行和巢寄生行為兩種位置更新策略的核心思想，提出了基于位置交叉和個(gè)體距離的離散萊維飛行，設(shè)計(jì)了基于最優(yōu)插入和最優(yōu)交換的巢寄生策略；（3）結(jié)合以上兩點(diǎn)，在標(biāo)準(zhǔn)布谷鳥(niǎo)算法結(jié)構(gòu)的基礎(chǔ)上，構(gòu)建了一種求解HFSP 的離散布谷鳥(niǎo)（Discrete Cuckoo Search，DCS）算法，并通過(guò)實(shí)例測(cè)試和算法比較，驗(yàn)證了該算法在求解質(zhì)量和穩(wěn)定性方面的優(yōu)越性。

3 問(wèn)題描述及模型構(gòu)建

不相關(guān)并行機(jī)HFSP 一般可描述為：n 個(gè)工件都需要按照相同的h 道工序順序進(jìn)行加工，每道工序有mj臺(tái)并行機(jī)(mj≥1;j=1,2,…,h)，每個(gè)工件的任意一道工序均可在該工序的任意一臺(tái)并行機(jī)上加工，且每道工序只能加工一次，已知各工件的各工序在各并行機(jī)上的加工時(shí)間，加工時(shí)間有所不同，要求確定每道工序的工件加工排序和對(duì)應(yīng)的機(jī)器分配情況，使得最大完工時(shí)間最小。

因HFSP的數(shù)學(xué)模型已有豐富而完善的研究，且本文研究的是該問(wèn)題的一種新的求解方法，本節(jié)參考王芳等[14]提出的0-1混合整數(shù)規(guī)劃模型，建立不相關(guān)并行機(jī)HFSP數(shù)學(xué)模型，符號(hào)定義如下：

N 為工件集合，N={1 ,2,…,n} ；

H 為工序集合，H={1 ,2,…,h} ；

M 為機(jī)器集合，M={1 ,2,…,m} ；

Mj為第j 道工序的可用機(jī)器集合：

mj為第j 道工序的可用機(jī)器數(shù)量；

i ∈N,k ∈M,t ∈N ；

Pi,j,k為工件i 的第j 道工序在機(jī)器k 上的加工時(shí)間；

Kk,t為機(jī)器k 第t 次開(kāi)始加工的時(shí)刻；

Jk,t為機(jī)器k 第t 次結(jié)束加工的時(shí)刻；

Fi,j為工件i 的第j 道工序開(kāi)始加工時(shí)間；

Ci,j為工件i 的第j 道工序結(jié)束加工時(shí)間；

U 為充分大的正數(shù)。

定義如下機(jī)器分配和工件排序兩個(gè)0-1決策變量：

基于以上兩決策變量構(gòu)建不相關(guān)并行機(jī)HFSP數(shù)學(xué)模型如下：

目標(biāo)函數(shù)（1）表示工件的最大完工時(shí)間最小化；約束（2）確保任一工件的任一道工序只能在該道工序中的某一臺(tái)機(jī)器上加工一次；約束（3）確定工件在某臺(tái)機(jī)器上加工順序；約束（4）確保一個(gè)工件只能在一臺(tái)機(jī)器上加工一次；約束（5）確保機(jī)器只能按順序加工工件；約束（6）確保機(jī)器加工任一工件的開(kāi)始時(shí)刻等于該工件開(kāi)始加工時(shí)刻；約束（7）和（8）確保任一工件結(jié)束加工時(shí)刻等于開(kāi)始加工時(shí)刻與加工時(shí)間之和；約束（9）確保機(jī)器前一次加工結(jié)束時(shí)刻不大于后一次的加工開(kāi)始時(shí)刻；約束（10）確保工件前一道工序加工結(jié)束時(shí)刻不大于后一道工序的開(kāi)始加工時(shí)刻。

4 求解HFSP的DCS算法

4.1 概述

標(biāo)準(zhǔn)CS算法是一種求解連續(xù)型優(yōu)化問(wèn)題的元啟發(fā)式算法，其核心思想是基于萊維飛行行為和巢寄生行為的兩種位置更新策略。萊維飛行行為是模仿自然界一些鳥(niǎo)類的飛行行為，可描述為一個(gè)運(yùn)動(dòng)體運(yùn)動(dòng)方向隨機(jī)，運(yùn)動(dòng)步長(zhǎng)以小步移動(dòng)為主，并偶爾伴有大步位移；巢寄生行為是指某些種類的布谷鳥(niǎo)有著具有侵略性的繁殖策略，它們趁其他鳥(niǎo)類（宿主鳥(niǎo)）外出時(shí)，偷偷在宿主鳥(niǎo)巢中產(chǎn)蛋，讓其代為孵化和育雛，而宿主鳥(niǎo)一旦發(fā)現(xiàn)了外來(lái)鳥(niǎo)蛋，會(huì)直接扔掉或者新建一個(gè)鳥(niǎo)巢。

因HFSP屬于組合優(yōu)化問(wèn)題，標(biāo)準(zhǔn)CS算法的位置更新策略中具體公式已不再適用，需要重新根據(jù)HFSP 的特性設(shè)計(jì)具體位置更新策略，以保留標(biāo)準(zhǔn)CS 算法優(yōu)勢(shì)。因此，本文基于標(biāo)準(zhǔn)CS算法的核心思想，提出求解HFSP的DCS算法。

4.2 解碼方法的改進(jìn)

在進(jìn)行詳細(xì)的算法設(shè)計(jì)之前，需進(jìn)行編碼和解碼規(guī)則的設(shè)計(jì)。因?yàn)橹苯永肏FSP 的數(shù)學(xué)模型求解，屬于精確計(jì)算，而HFSP是一種NP難題，在合理的時(shí)間范圍內(nèi)精確計(jì)算只能求解很小規(guī)模且簡(jiǎn)單的問(wèn)題。因此，在求解HFSP 這類調(diào)度問(wèn)題時(shí)，大量文獻(xiàn)都是根據(jù)問(wèn)題描述及模型約束等，設(shè)計(jì)相應(yīng)的編碼和解碼規(guī)則。這種方式既方便算法的進(jìn)化操作，也方便快速獲得目標(biāo)函數(shù)值以及詳細(xì)的調(diào)度方案。

本節(jié)在已有研究的基礎(chǔ)上，在編碼方面直接采用基于排列的編碼方法，在解碼方面基于王芳等[14]提出的一種隨機(jī)規(guī)則解碼方法，根據(jù)HFSP的特性，提出改進(jìn)的隨機(jī)規(guī)則解碼方法，使得解碼方法更加合理有效，能進(jìn)一步提高解的質(zhì)量。

基于排列的編碼方法，其編碼序列為：

其中，n 為待加工工件數(shù)，xi∈{1,2,…,n} ，工件號(hào)xi在編碼序列中的位置代表工件第一道工序的加工順序。

解碼可分為工件排序和機(jī)器分配兩部分。原始解碼方法是按照工件先到先加工規(guī)則和最先機(jī)器空閑規(guī)則，確定工件排序時(shí)，第一道工序由編碼序列確定工件先后加工順序，后續(xù)工序的工件排序采用先到先加工規(guī)則，按照工件前一工序的完成時(shí)間排列順序，先完成的先加工，若有工件在前一工序的完成時(shí)間相同，則隨機(jī)確定這些工件的加工順序；分配機(jī)器時(shí)，將工件分配到加工當(dāng)前工件所需的完工時(shí)間最早的機(jī)器上。隨機(jī)規(guī)則解碼方法是于2017 年提出的，工件排序按先到先加工規(guī)則確定，而在分配機(jī)器時(shí)，當(dāng)生成的隨機(jī)概率u 大于給定的機(jī)器選擇概率Pm 時(shí)，則隨機(jī)分配機(jī)器，反之，按完工時(shí)間來(lái)分配機(jī)器。隨機(jī)概率u 服從[0，1]均勻分布，機(jī)器選擇概率Pm 選取王芳等[14]確定的0.85 概率值。由于隨機(jī)概率的存在，同一編碼序列對(duì)應(yīng)的目標(biāo)函數(shù)值很有可能不同，因此為獲得更優(yōu)解，設(shè)定最大循環(huán)解碼次數(shù)C，當(dāng)循環(huán)過(guò)程中出現(xiàn)比上一代更優(yōu)的目標(biāo)函數(shù)值時(shí)，則退出循環(huán)，并記為該序列的目標(biāo)函數(shù)值。

表1為一個(gè)6工件、2工序的不相關(guān)并行機(jī)HFSP的加工時(shí)間表，編碼序列[2,4,3,6,1,5] 經(jīng)上述兩種解碼方法所得的甘特圖如圖1、圖2 所示。甘特圖中方框內(nèi)數(shù)字代表工件號(hào)，工件號(hào)自下至上出現(xiàn)的順序代表工序。例如，圖1 中工件2 的第1 道工序在機(jī)器M1 上加工，開(kāi)工時(shí)刻為0，完工時(shí)刻為3，第2 道工序在機(jī)器M6上加工，開(kāi)工時(shí)刻為3，完工時(shí)刻為7。對(duì)比圖1、圖2可知，在第2道工序給4號(hào)工件分配機(jī)器時(shí)，滿足u ＞Pm，于是將4號(hào)工件隨機(jī)分配給已加工了3號(hào)工件的5號(hào)機(jī)器。雖然最后兩者解碼得到的最大完工時(shí)間都為9，但是后者重復(fù)地將工件分配給同一臺(tái)機(jī)器，使6號(hào)機(jī)器僅在短時(shí)間內(nèi)加工了一個(gè)工件，同時(shí)加大了5 號(hào)機(jī)器負(fù)荷，還有可能增大最后完工時(shí)間。

表1 加工時(shí)間表

圖1 原始規(guī)則解碼

圖2 隨機(jī)規(guī)則解碼

因此，本文根據(jù)HFSP 需要同時(shí)確定工件和機(jī)器的特性，基于工件數(shù)和并行機(jī)數(shù)，對(duì)隨機(jī)規(guī)則解碼方法進(jìn)行改進(jìn)，提出改進(jìn)隨機(jī)規(guī)則解碼方法，以提高解的質(zhì)量。具體實(shí)施方法如下：工序j 中有mj臺(tái)并行機(jī)，加工任意一道工序時(shí)，每mj個(gè)工件進(jìn)行一次判斷，當(dāng)u ＞Pm時(shí)，任選其中一個(gè)工件對(duì)其隨機(jī)分配機(jī)器，剩余工件則以先到先加工規(guī)則確定的排序并按完工時(shí)間來(lái)分配機(jī)器，反之，這mj個(gè)工件都按完工時(shí)間來(lái)分配機(jī)器，若最后不足mj個(gè)工件但多于一個(gè)，依然按上述規(guī)則分配機(jī)器，若僅剩一個(gè)工件，則按最先機(jī)器空閑規(guī)則分配機(jī)器。對(duì)上述編碼序列用改進(jìn)解碼方法求得的甘特圖如圖3所示，獲得最大完工時(shí)間為8，提高了解的質(zhì)量。

圖3 改進(jìn)規(guī)則解碼

4.3 離散萊維飛行的改進(jìn)

在標(biāo)準(zhǔn)CS 算法中，萊維飛行是一種連續(xù)性的位置更新，而HFSP是一種典型的組合優(yōu)化問(wèn)題，因而需要設(shè)計(jì)適用于HFSP的離散萊維飛行。

一般的離散萊維飛行是基于某種排列映射規(guī)則，例如最小位置（Smallest Position Value，SPV）規(guī)則[23]和最大順序值（Largest Order Value，LOV）規(guī)則[24]。SPV 規(guī)則指將實(shí)數(shù)向量中的各分量進(jìn)行升序排列得到新向量，新向量中各分量所對(duì)應(yīng)原來(lái)向量中的位置序列即為整數(shù)編碼序列；LOV規(guī)則與SPV規(guī)則相反，是指對(duì)各分量進(jìn)行降序排列。這種方法簡(jiǎn)單易于實(shí)現(xiàn)，既能保證調(diào)度解的可行性，又無(wú)須修改CS算法的進(jìn)化操作，因而得到了廣泛的運(yùn)用。但是，這種方法不能有效地將連續(xù)空間中局部搜索與全局搜索之間的關(guān)系轉(zhuǎn)換到離散空間，削弱了算法性能，容易陷入局部極值，難以搜索到最優(yōu)解。因此，本文提出一種基于位置交叉和個(gè)體距離的離散萊維飛行機(jī)制，種群中每個(gè)鳥(niǎo)巢與最優(yōu)鳥(niǎo)巢之間的個(gè)體距離視為概率，以這個(gè)概率進(jìn)行基于位置的交叉操作。

基于位置的交叉是遺傳算法中的一種交叉策略，使用這種交叉策略可以避免在交叉操作過(guò)程中產(chǎn)生不可行解；個(gè)體距離是劉長(zhǎng)平等[25]在使用離散螢火蟲(chóng)算法時(shí)提出的，表示兩個(gè)體在離散空間中距離遠(yuǎn)近程度，本文將其引入作為離散萊維飛行中的交叉概率。由于編碼序列中xi僅代表工件號(hào)，工件號(hào)之差并不能代表它們?cè)陔x散空間中的距離遠(yuǎn)近，因此本文對(duì)其稍做改進(jìn)，使其更符合編碼序列之間的遠(yuǎn)近程度，改進(jìn)后個(gè)體距離求解過(guò)程如下：

首先，編碼序列的個(gè)體零點(diǎn)位置定義為：

然后，編碼序列的個(gè)體位置定義為：將編碼序列X的工件號(hào)按從小到大排列，并記錄每個(gè)工件號(hào)對(duì)應(yīng)所在位置，即為個(gè)體位置S。

最后，編碼序列之間的個(gè)體距離定義為：

式中，si,k、sj,k為個(gè)體i、j 第k 維的位置數(shù)；N 為分子項(xiàng)取值上限，按下式計(jì)算：

由定義可知di,j∈[0 ,1] ，反映了鳥(niǎo)巢之間的遠(yuǎn)近程度，值越大，則距離越遠(yuǎn)。

改進(jìn)的離散萊維飛行具體實(shí)施步驟如下：

（1）計(jì)算當(dāng)前鳥(niǎo)巢與最優(yōu)鳥(niǎo)巢的個(gè)體位置及兩者間的個(gè)體距離，并將后者定義為交叉概率。

（2）生成1×n 的隨機(jī)概率矩陣，將概率矩陣中每個(gè)位置的概率與交叉概率相比較，若大于交叉概率，則當(dāng)前鳥(niǎo)巢在該位置上對(duì)應(yīng)的工件號(hào)保留，反之，刪除對(duì)應(yīng)該位置的工件號(hào)。

（3）將最優(yōu)鳥(niǎo)巢的編碼序列上與當(dāng)前鳥(niǎo)巢的編碼序列保留的工件號(hào)相同的工件號(hào)刪除。

（4）將最優(yōu)鳥(niǎo)巢剩余的工件號(hào)依次填入當(dāng)前鳥(niǎo)巢被刪除的工件號(hào)的位置。

例如，當(dāng)前鳥(niǎo)巢編碼序列為[2 ,1,5,3,4,6] ，最優(yōu)鳥(niǎo)巢編碼序列為[3 ,5,2,4,6,1] 。首先執(zhí)行步驟（1），得到兩個(gè)鳥(niǎo)巢的個(gè)體位置分別為[2 ,1,4,5,3,6] 和[6,3,1,4,2,5] ，它們之間的個(gè)體距離為2/3，即交叉概率為2/3；然后執(zhí)行步驟（2），生成的隨機(jī)概率矩陣為[0.81,0.91,0.13,0.74,0.63,0.09] ，與交叉概率相比較，則當(dāng)前鳥(niǎo)巢編碼序列變?yōu)閇2 ,1,x,3,x,x] ；接著執(zhí)行步驟（3），刪除最優(yōu)鳥(niǎo)巢編碼序列上與之保留的相同的工件號(hào)，則最優(yōu)鳥(niǎo)巢編碼序列變?yōu)閇 x,5,x,4,6,x] 。最后執(zhí)行步驟（4），將其依次填入當(dāng)前鳥(niǎo)巢編碼序列中，即可得到新鳥(niǎo)巢的編碼序列[2 ,1,5,3,4,6] 。

4.4 巢寄生策略的設(shè)計(jì)

在標(biāo)準(zhǔn)CS 算法中，巢寄生策略的具體位置更新操作采用隨機(jī)游動(dòng)方式，是一種連續(xù)的位置更新，并不適合求解HFSP這類組合優(yōu)化問(wèn)題。本文根據(jù)HFSP的編碼形式特點(diǎn)，設(shè)計(jì)基于最優(yōu)交換和最優(yōu)插入的巢寄生策略。這兩種操作敘述如下：

（1）最優(yōu)插入操作：從編碼序列X 中隨機(jī)刪除一個(gè)工件號(hào)，得到n-1 個(gè)工件的序列X′，可知該序列有n個(gè)可插入位置，從左到右依次插入后計(jì)算新序列的目標(biāo)函數(shù)值，當(dāng)新序列的目標(biāo)函數(shù)值優(yōu)于原序列的目標(biāo)函數(shù)值時(shí)，則退出最優(yōu)插入操作，并更新編碼序列，反之，則繼續(xù)插入操作，直到達(dá)到可插入次數(shù)為止。

（2）最優(yōu)交換操作：在工件序列X 中隨機(jī)選取一個(gè)工件號(hào)，并與序列X 中其他位置上的工件一一交換，可知有n-1 次交換操作，從左到右依次交換后計(jì)算新序列的目標(biāo)函數(shù)值，新序列的目標(biāo)函數(shù)值優(yōu)于原序列的目標(biāo)函數(shù)值時(shí)，則退出最優(yōu)交換操作，并更新編碼序列，反之，則繼續(xù)交換操作，直到達(dá)到可交換次數(shù)為止。

基于最優(yōu)交換和最優(yōu)插入的巢寄生策略可敘述為：對(duì)鳥(niǎo)巢i 生成一個(gè)服從均勻分布的隨機(jī)數(shù)r ∈[0,1] ，并與給定的被發(fā)現(xiàn)概率Pa 相比，如果r ＞Pa，則執(zhí)行位置更新操作，其中最優(yōu)插入和最優(yōu)交換操作各有0.5 的概率執(zhí)行，產(chǎn)生新的鳥(niǎo)巢Xnew；若新鳥(niǎo)巢Xnew的適應(yīng)度優(yōu)于鳥(niǎo)巢

4.5 DCS算法流程及其復(fù)雜度

根據(jù)上述的求解HFSP 的算法設(shè)計(jì)思路，算法中各操作時(shí)間復(fù)雜度如表2 所示，算法總的時(shí)間復(fù)雜度為O(Gmax×PsizeChn logn)，log 的底數(shù)為大于1 的正整數(shù)，其中適應(yīng)度計(jì)算和巢寄生策略都考慮最差情況。

表2 算法各操作復(fù)雜度

DCS算法流程偽代碼如下所示：

1. 初始化參數(shù)：加工機(jī)器矩陣J 、加工時(shí)間矩陣T 、鳥(niǎo)巢種群數(shù)量Psize、被發(fā)現(xiàn)概率Pa、機(jī)器選擇概率Pm、解碼最大循環(huán)次數(shù)C、最大迭代次數(shù)Gmax；

2. 隨機(jī)初始化鳥(niǎo)巢，計(jì)算并記錄對(duì)應(yīng)適應(yīng)度值，記錄當(dāng)前全局最優(yōu)鳥(niǎo)巢Xm、適應(yīng)度值Fmin及具體最優(yōu)調(diào)度方案；

3. repeat 4. 采用4.3節(jié)提出的離散萊維飛行產(chǎn)生新的鳥(niǎo)巢；

5. 計(jì)算新鳥(niǎo)巢的適應(yīng)度，若有更優(yōu)的鳥(niǎo)巢則鳥(niǎo)蛋被孵化，取代較差的鳥(niǎo)巢；

6. 采用4.4 節(jié)設(shè)計(jì)的巢寄生策略進(jìn)行局部搜索，并記錄當(dāng)前最優(yōu)鳥(niǎo)巢Xn、適應(yīng)度值Fnew及其最優(yōu)調(diào)度方案；

7.if Fnew＜Fmin

8. Xm=Xn；

9. Fmin=Fnew；

10. 替換最優(yōu)調(diào)度方案；

11. end if

12. until滿足算法終止條件；//達(dá)到最大迭代次數(shù)Gmax

13. return最優(yōu)調(diào)度方案

5 仿真測(cè)試及分析

5.1 算法參數(shù)確定

求解HFSP 的DCS 算法主要相關(guān)參數(shù)有種群大小Psize、被發(fā)現(xiàn)概率Pa，解碼方法中相關(guān)參數(shù)有機(jī)器選擇概率Pm 和解碼最大循環(huán)次數(shù)C。種群大小Psize對(duì)算法影響較大，若種群數(shù)量過(guò)小，則初始化個(gè)體在解空間分布密度小，對(duì)解空間的搜索不夠徹底，并且影響種群多樣性，也易導(dǎo)致算法陷入局部極值；若種群數(shù)量過(guò)大，則會(huì)大大增加算法運(yùn)行時(shí)間，可能會(huì)出現(xiàn)重復(fù)搜索某區(qū)域的現(xiàn)象。被發(fā)現(xiàn)概率Pa 主要影響算法運(yùn)行時(shí)間和收斂速度，較小時(shí)，算法運(yùn)行時(shí)間較長(zhǎng)，收斂速度較快，而過(guò)小可能導(dǎo)致算法陷入局部極值，對(duì)于大多數(shù)優(yōu)化問(wèn)題，通常取Pa=0.25，就能滿足需求。機(jī)器選擇概率Pm 直接影響算法搜索空間大小，進(jìn)而影響算法收斂速度，Pm 較小，解碼過(guò)程偏向于隨機(jī)解碼，此時(shí)搜索空間較大，Pm 較大，解碼過(guò)程偏向于規(guī)則解碼，此時(shí)搜索空間較小。解碼最大循環(huán)次數(shù)C 對(duì)算法性能影響較大，C過(guò)小，難以對(duì)編碼序列進(jìn)行有效的解碼，C 過(guò)大，則會(huì)過(guò)多增加算法運(yùn)行時(shí)間。根據(jù)上述分析并經(jīng)過(guò)大量的測(cè)試，為兼顧算法運(yùn)行時(shí)間、收斂速度和優(yōu)化質(zhì)量，本文中，DCS算法參數(shù)設(shè)置如表3所示。

表3 算法參數(shù)設(shè)置

5.2 改進(jìn)解碼方法有效性驗(yàn)證

本節(jié)分別采用原始規(guī)則、隨機(jī)規(guī)則和改進(jìn)隨機(jī)規(guī)則解碼的DCS 算法（分別記為DCS_P、DCS_R、DCS_I）對(duì)5個(gè)隨機(jī)生成的算例進(jìn)行求解，以驗(yàn)證改進(jìn)隨機(jī)規(guī)則的有效性。采用10 工件、5 工序，并行機(jī)數(shù)[3,3,2,3,3] ，加工時(shí)間[30,60] 的5 個(gè)隨機(jī)整數(shù)算例，為更好地符合實(shí)際生產(chǎn)，并行機(jī)處理同一個(gè)工件的同一道工序的最大時(shí)間差不得超過(guò)5。每種算法均獨(dú)立運(yùn)行10次，以運(yùn)行結(jié)果的最優(yōu)下界Cmax、平均值A(chǔ)VG、標(biāo)準(zhǔn)差STD作為評(píng)價(jià)指標(biāo)，結(jié)果如表4所示。

表4 三種解碼方法的運(yùn)行結(jié)果對(duì)比

從表4可以看出，對(duì)于算例1，DCS_R和DCS_I算法求解得到的Cmax分別為356和355，小于DCS_P算法求解得到的358，再對(duì)比算例2～算例5，發(fā)現(xiàn)DCS_R 和DCS_I 算法所得到的Cmax數(shù)值都小于DCS_P 算法，驗(yàn)證了混合概率與規(guī)則的解碼方法更可能得到更優(yōu)解。然后，對(duì)算例1，DCS_I 算法求解10 次得到的平均值A(chǔ)VG 為355.9，小于DCS_R 算法得到的356.1，進(jìn)一步看出，除算例3兩種算法10次求解的平均值A(chǔ)VG相同外，對(duì)算例2、算例4、算例5，DCS_I算法求解所得AVG都小于DCS_R 算法，說(shuō)明改進(jìn)方法提高了算法解的質(zhì)量。最后，對(duì)于算例1～算例5，采用三種解碼方法求得的解的標(biāo)準(zhǔn)差STD 都小于1，說(shuō)明DCS 算法的解的穩(wěn)定性好。因此，對(duì)比結(jié)果驗(yàn)證了改進(jìn)隨機(jī)規(guī)則的有效性。

圖4為算例1采用不同解碼方法的收斂曲線圖?？梢钥闯?，在算法前期時(shí)，DCS_P算法的收斂速度最快，但導(dǎo)致了算法早熟，從而陷入了局部極值；DCS_I 算法的收斂速度快于DCS_R 算法，說(shuō)明改進(jìn)方法能對(duì)解空間進(jìn)行更為有效的搜索，從而加快算法收斂速度，進(jìn)一步驗(yàn)證了改進(jìn)隨機(jī)規(guī)則的有效性。

圖4 不同解碼方法求解算例1的收斂曲線

5.3 實(shí)例驗(yàn)證及算法比較

本文利用王圣堯等[9]采用的兩個(gè)不相關(guān)并行機(jī)HFSP實(shí)例進(jìn)行測(cè)試，并與其他文獻(xiàn)提出的求解算法做對(duì)比，其中SACS[21]算法為一種求解HFSP 的自適應(yīng)布谷鳥(niǎo)算法，GA算法為常用算法，F(xiàn)OA[26]、EDA[9]、EDA_H[14]、IPSO[27]均為近年來(lái)求解以最小化完工時(shí)間為目標(biāo)的不相關(guān)并行機(jī)HFSP 的典型代表算法。算法在Intel Core i5-7300HQ 2.50 GHz CPU、8 GB RAM、Windows 10操作系統(tǒng)和Matlab編程環(huán)境下編譯測(cè)試。

DCS_I 算法求解實(shí)例中兩種位置更新步驟的詳細(xì)代碼如下。

離散萊維飛行位置更新步驟的代碼：

巢寄生策略位置更新步驟的代碼：

表5、表6 為各種算法求解兩個(gè)實(shí)例獨(dú)立運(yùn)行10 次的結(jié)果。

從表5、表6的運(yùn)行結(jié)果可以看出，DCS_I算法對(duì)第一個(gè)實(shí)例的10次運(yùn)行結(jié)果中有6次求出了最優(yōu)解23，對(duì)第二個(gè)實(shí)例10 次運(yùn)行結(jié)果都求出了最優(yōu)解297。對(duì)比其他算法結(jié)果可以看出DCS_I 算法在解的質(zhì)量方面優(yōu)于SACS、GA、FOA、EDA等算法，說(shuō)明了本文所提算法求解該類問(wèn)題的優(yōu)越性。DCS_I 算法求解結(jié)果對(duì)應(yīng)的調(diào)度甘特圖如圖5、圖6所示。

表5 實(shí)例1的運(yùn)行結(jié)果

表6 實(shí)例2的運(yùn)行結(jié)果

圖5 實(shí)例1調(diào)度甘特圖

圖6 實(shí)例2調(diào)度甘特圖

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

本文在不相關(guān)并行機(jī)混合流水車(chē)間調(diào)度問(wèn)題的現(xiàn)有研究基礎(chǔ)上，提出了一種求解HFSP 的離散布谷鳥(niǎo)算法。本文主要工作如下：

（1）提出了改進(jìn)隨機(jī)規(guī)則解碼方法，通過(guò)算例對(duì)比分析，驗(yàn)證了改進(jìn)解碼方法的有效性，能合理地加快算法收斂速度，同時(shí)增加搜索到更優(yōu)解的可能性，提高解的質(zhì)量。

（2）根據(jù)標(biāo)準(zhǔn)布谷鳥(niǎo)算法的兩種位置更新策略思想，提出了基于位置交叉和個(gè)體距離的離散萊維飛行，設(shè)計(jì)了基于最優(yōu)插入和最優(yōu)交換操作的巢寄生策略。

（3）通過(guò)實(shí)例測(cè)試和算法比較，驗(yàn)證了本文算法在求解質(zhì)量和穩(wěn)定性方面優(yōu)于自適應(yīng)布谷鳥(niǎo)算法、遺傳算法和分布估計(jì)算法等。

通過(guò)研究，發(fā)現(xiàn)本文算法在求解大規(guī)模問(wèn)題時(shí)，用時(shí)較長(zhǎng)，因此如何減少算法求解時(shí)間而不犧牲算法原有性能是一個(gè)未來(lái)研究方向，或者結(jié)合工程實(shí)際需要，拓展本文算法的應(yīng)用領(lǐng)域。