改進(jìn)的離散型螢火蟲(chóng)優(yōu)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題

鄭 捷，潘大志,2

(1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川 南充 637009; 2.西華師范大學(xué)計(jì)算方法與應(yīng)用研究所，四川 南充 637009)

0 引 言

自柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job-shop Scheduling Problem, FJSP)由Brucker等[1]提出以來(lái)，就一直受到各個(gè)領(lǐng)域?qū)＜覍W(xué)者的關(guān)注[2-8]。與經(jīng)典的JSP不同，F(xiàn)JSP中的每一道工序可以在多臺(tái)機(jī)器上加工，且不同的機(jī)器上加工時(shí)間不相同，已被證明為NP-hard問(wèn)題。其調(diào)度目標(biāo)是以某個(gè)加工性能指標(biāo)為目標(biāo)函數(shù)來(lái)確定各個(gè)工件的工序在各機(jī)器上的加工順序，通常以最小化最大完工時(shí)間、最小化最大能耗、最遲完工時(shí)間等為目標(biāo)函數(shù)。

張桐瑞等[9]以最小化最大完工時(shí)間為目標(biāo)，提出了混合競(jìng)爭(zhēng)群優(yōu)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題，以混合競(jìng)爭(zhēng)優(yōu)化算法為基礎(chǔ)，加入POX交叉與環(huán)形拓?fù)浣Y(jié)構(gòu)相結(jié)合，引入鄰域搜索，增加算法的全局搜索能力和局部搜索能力；戴月明等[10]提出了一種骨干雙粒子群算法求解柔性作業(yè)車間調(diào)度問(wèn)題；姜天華[11]提出了一種混合灰狼優(yōu)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題；謝銳強(qiáng)等[12]以最小化最大完工時(shí)間為目標(biāo)函數(shù)建立模型，提出了一種求解柔性作業(yè)車間調(diào)度問(wèn)題的兩段式狼群算法；陶婷婷等[13]針對(duì)最大完工時(shí)間最小化為目標(biāo)，提出了一種改進(jìn)離散型飛蛾撲火優(yōu)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題；張捷等[14]提出了基于郊狼優(yōu)化算法求解柔性作業(yè)車間調(diào)度問(wèn)題；Wang等[15]提出了改進(jìn)的ACO算法求解FJSP；Li等[16]提出了基于Pareto的離散人工蜂群算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題。但是，目前尚未找到可以求得所有問(wèn)題的最優(yōu)解的算法。因此國(guó)內(nèi)外的學(xué)者們?nèi)栽诜e極地探索，以尋求更為豐富和有效的方法。

本文將FA應(yīng)用到柔性作業(yè)車間調(diào)度問(wèn)題中，首先對(duì)FJSP進(jìn)行描述和建模；然后根據(jù)FJSP的特點(diǎn)，提出一種改進(jìn)的離散的螢火蟲(chóng)算法(DFA)；利用標(biāo)準(zhǔn)算例對(duì)算法進(jìn)行仿真，驗(yàn)證DFA求解FJSP的有效性；最后，通過(guò)與傳統(tǒng)算法進(jìn)行仿真對(duì)比，驗(yàn)證DFA求解FJSP的優(yōu)越性。

1 柔性作業(yè)車間調(diào)度問(wèn)題

1.1 問(wèn)題描述

FJSP可描述為：有n個(gè)待加工的工件和m臺(tái)機(jī)器，每個(gè)工件有ni(1≤i≤m)道工序，且工序間必須遵循一定的加工順序。與JSP不同，F(xiàn)JSP問(wèn)題中每道工序可以在多于一臺(tái)機(jī)器上進(jìn)行加工，且已知每道工序在每臺(tái)加工機(jī)器上的加工時(shí)間。FJSP需解決2個(gè)問(wèn)題：機(jī)器選擇和工序排序。機(jī)器選擇是為每道工序選取合適的加工機(jī)器。工序排序是確定在同一機(jī)器上各個(gè)工序的加工順序。FJSP需要滿足以下條件：

1)同一時(shí)刻同一機(jī)器只能加工一道工序。

2)一旦工件的某一工序開(kāi)始加工，它就不能被中斷，直至該工序加工完成。

3)任何工件都不具有加工優(yōu)先級(jí)。

4)不同工件的各個(gè)工序沒(méi)有加工順序的約束，同一工件的各個(gè)工序有加工順序的約束。

5)任何工件在零時(shí)刻都能被加工。

1.2 變量定義

變量定義如下：

M={Mk|1≤k≤m}，表示機(jī)器集；

J={Ji|1≤i≤n}，表示工件集；

Oi={Oij|1≤j≤ni}，表示Ji的工序集；

Mij={Mk|Xijk=1}表示工件Ji的工序Oij的可用機(jī)器集；

Ci表示工件Ji的完工時(shí)間；

Pijk表示工件Ji的第j道工序Oij在機(jī)器Mk上的加工時(shí)間；

Sijk表示工件Ji的第j道工序Oij在機(jī)器Mk上的開(kāi)始加工時(shí)間；

Eijk表示工件Ji的第j道工序Oij在機(jī)器Mk上的結(jié)束時(shí)間；

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

本文以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，目標(biāo)函數(shù)f為：

f=min{max(Ci)},i=1,2,…,n

(1)

約束條件：

Eijk+Pijk≥Eegk,Rijegk=1,Xijk=1

(2)

Sijk+Pijk=Eijk,Xijk=1

(3)

Eijk≤Si(j+1)h，Xijk=Xi(j+1)h=1

(4)

其中式(2)表示1.1節(jié)中條件1)的約束；式(3)表示1.1節(jié)中條件2)的約束；式(4)表示同一工件的加工順序必須按照工藝順序進(jìn)行。

2 螢火蟲(chóng)算法

螢火蟲(chóng)算法(FA)是由劍橋大學(xué)的Yang[17]于2008年提出的一種基于群體智能的隨機(jī)搜索算法。為構(gòu)建FA的數(shù)學(xué)模型，使用以下3個(gè)理想化準(zhǔn)則：

1)所有的螢火蟲(chóng)都不分雌雄。

2)螢火蟲(chóng)之間的吸引力與距離成反比，與亮度成正比。

3)螢火蟲(chóng)的亮度與待優(yōu)化的目標(biāo)函數(shù)值有關(guān)。

根據(jù)上面的理想化準(zhǔn)則可知，亮度與吸引度是FA中2個(gè)重要的影響因子，假設(shè)問(wèn)題空間規(guī)模為d維，第i只螢火蟲(chóng)在d維空間中的位置表示為xi=(xi,1,xi,2,…,xi,d)。

定義1 螢火蟲(chóng)的亮度：

(5)

式(5)中，I0為螢火蟲(chóng)的初始亮度，取決于需要尋優(yōu)的目標(biāo)函數(shù)值，一般用式(6)表示；γ為光強(qiáng)吸收因子；rij為螢火蟲(chóng)i與螢火蟲(chóng)j之間的歐氏距離，一般用式(7)表示。

I0=f(x)

(6)

(7)

定義2 吸引度：

(8)

式(8)中β0為最大的吸引度。

定義3 位置更新公式：

(9)

式(9)中，α為隨機(jī)步長(zhǎng)因子，取值范圍為(0,1)；rand為服從在(0,1)上均勻分布的隨機(jī)數(shù)。

3 改進(jìn)的離散型螢火蟲(chóng)算法

3.1 編碼與解碼

由于FJSP需解決工序排序與機(jī)器分配這2個(gè)問(wèn)題，因此編碼應(yīng)該包括工序編碼和機(jī)器編碼2個(gè)的部分。本文采用兩段式編碼方式[18]，編碼長(zhǎng)度為工序總數(shù)目，假設(shè)工序數(shù)目為l，則編碼的總長(zhǎng)度為2l。示例編碼如圖1所示。

圖1 示例編碼

圖1中，第一段為基于工序順序的編碼，記為工序向量Xprocess[l]。第二段為基于機(jī)器分配的編碼，記為機(jī)器向量Xmachine[l]。對(duì)于工件序列，可以表達(dá)加工的序列為(O1,1,O3,1,O2,1,O4,1,O3,2,O2,2,O1,2,O4,2,O3,3,O2,3)，其對(duì)應(yīng)的加工機(jī)器為(M4,M3,M2,M1,M2,M3,M2,M1,M4,M1)。即O1,1在機(jī)器M4上進(jìn)行加工，O3,1在機(jī)器M3上進(jìn)行加工。

解碼方法：本文采用插入式貪婪解碼[19]的方法，獲得主動(dòng)調(diào)度解。首先通過(guò)機(jī)器向量編碼來(lái)獲得每道工序的機(jī)器選擇方案，然后確定工序在對(duì)應(yīng)加工機(jī)器的加工時(shí)間，最后根據(jù)工序向量確定工序加工順序，依次進(jìn)行解碼，在不推遲其他已經(jīng)安排好工序的開(kāi)工時(shí)間的條件下，將工序插入到對(duì)應(yīng)機(jī)器上最早可行的加工時(shí)刻進(jìn)行加工[20]。

3.2 種群初始化

由于初始種群對(duì)種群的多樣性以及算法的求解效率有著極其重要的影響，因此，在生成初始種群的機(jī)器向量時(shí)，種群中50%的個(gè)體使用本文提出的機(jī)器選擇策略進(jìn)行生成，另外50%的個(gè)體的機(jī)器向量采用隨機(jī)選擇的方式生成，而對(duì)于工序序列，則采用完全隨機(jī)的方式生成。

3.3 機(jī)器選擇策略

本文采用根據(jù)工序最小完工時(shí)間來(lái)選擇機(jī)器的策略。記工序可選擇的設(shè)備集為C，可選擇的設(shè)備個(gè)數(shù)為λ，該工序選擇加工機(jī)器上的前一工序的完工時(shí)間為ti1，該工序?qū)?yīng)工件的前一工序的完工時(shí)間為t，工序所選取的機(jī)器上的加工時(shí)間為ti2。則按照工序的加工順序在每個(gè)工序的可選設(shè)備集中選取使得當(dāng)前完工時(shí)間tc最小的機(jī)器。將其存入機(jī)器向量Xmachine[l]中，并更新工序的完工時(shí)間表。具體的機(jī)器選擇策略如公式(10)和公式(11)所示。

tc=min(tCi), 1≤i≤λ

(10)

(11)

3.4 局部搜索算法

為了增強(qiáng)算法的局部搜索能力，對(duì)種群適應(yīng)度排名前5%的個(gè)體進(jìn)行局部搜索。首先生成一個(gè)0～1之間的隨機(jī)數(shù)r，若r>0.5，則采用最優(yōu)插入操作[21]；否則采用最優(yōu)交換操作[21]。

1)最優(yōu)插入操作。

首先記錄當(dāng)前工序序列以及其對(duì)應(yīng)的目標(biāo)函數(shù)值，其次在[0,l]之間產(chǎn)生一個(gè)隨機(jī)整數(shù)，在原工序向量中將對(duì)應(yīng)位置的元素刪除，得到一個(gè)工序序列。然后將此元素從左到右依次插入原工序序列中，并更新機(jī)器向量，然后計(jì)算新生成序列的目標(biāo)函數(shù)值，當(dāng)新生成序列的目標(biāo)函數(shù)值比原序列的目標(biāo)函數(shù)值更優(yōu)時(shí)，則退出循環(huán)，并更新個(gè)體的編碼序列，否則繼續(xù)進(jìn)行插入操作，直到循環(huán)結(jié)束。其示意圖如圖2所示。

圖2 最優(yōu)插入操作

2)最優(yōu)交換操作。

首先記錄當(dāng)前工序序列以及其對(duì)應(yīng)的目標(biāo)函數(shù)值，其次在[0,l]之間產(chǎn)生一個(gè)隨機(jī)整數(shù)，在工件序列中將對(duì)應(yīng)位置的工件號(hào)記錄下來(lái)，然后與其他位置的工件號(hào)從左到右依次進(jìn)行交換，并更新機(jī)器向量，然后計(jì)算新生成序列的目標(biāo)函數(shù)值，當(dāng)新生成序列的目標(biāo)函數(shù)值比原序列的目標(biāo)函數(shù)值更優(yōu)時(shí)，則退出循環(huán)，并更新編碼序列，否則，繼續(xù)最優(yōu)交換操作，直到循環(huán)結(jié)束。其示意圖如圖3所示。

圖3 最優(yōu)交換操作

3.5 改進(jìn)的離散型螢火蟲(chóng)算法

由于標(biāo)準(zhǔn)的螢火蟲(chóng)算法適用于解決連續(xù)優(yōu)化問(wèn)題，而FJSP是一種典型的離散優(yōu)化問(wèn)題，因此有必要針對(duì)FJSP的特點(diǎn)，提出一種改進(jìn)的離散型螢火蟲(chóng)優(yōu)化算法(DFA)。此時(shí)，螢火蟲(chóng)的位置更新如公式(12)所示：

(12)

圖4 改進(jìn)的離散型螢火蟲(chóng)算法

圖5 交叉操作

Step1將工件集隨機(jī)分為2個(gè)集合A1和A2。

3.6 改進(jìn)的離散型螢火蟲(chóng)算法流程

本文針對(duì)FJSP問(wèn)題的特點(diǎn)，提出一種改進(jìn)的離散型螢火蟲(chóng)算法DFA。由于本文以最小化最大完工時(shí)間為目標(biāo)函數(shù)，因此目標(biāo)函數(shù)值越小，代表個(gè)體的亮度越高。DFA的算法步驟如下：

Step1設(shè)置種群規(guī)模、最大迭代次數(shù)、工件數(shù)量、機(jī)器數(shù)量等。

Step2對(duì)種群進(jìn)行初始化。

Step3計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，標(biāo)記適應(yīng)度最高的個(gè)體為Xbest。

Step4若I(i)

Step5使用改進(jìn)的離散型螢火蟲(chóng)算法更新個(gè)體的工序向量，使用機(jī)器選擇策略更新個(gè)體的機(jī)器向量，并更新個(gè)體的適應(yīng)度值。

Step6對(duì)種群適應(yīng)度排名前5%的個(gè)體進(jìn)行局部搜索，并更新Xbest。

Step7判斷是否達(dá)到終止條件，如果達(dá)到，則跳轉(zhuǎn)到Step8，否則跳轉(zhuǎn)到Step4。

Step8輸出結(jié)果。

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

為了驗(yàn)證DFA算法是否能夠有效求解FJSP，選取一個(gè)8×8的標(biāo)準(zhǔn)算例[22]對(duì)DFA在柔性作業(yè)車間調(diào)度問(wèn)題中的應(yīng)用進(jìn)行可行性驗(yàn)證，算例原始數(shù)據(jù)如表1所示。同時(shí)也對(duì)Kacem[23]標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。

表1 算例原始數(shù)據(jù)

設(shè)置種群規(guī)模NIND=40，迭代次數(shù)MAXGEN=50，仿真結(jié)果如圖6所示，仿真軟件為Matlab R2018a，硬件如下：計(jì)算機(jī)內(nèi)存為8 GB，處理器為Inter(R) Xeon(R) E3-1240 v5，主頻為3.50 GHz。

圖6 仿真結(jié)果

對(duì)于Kacem數(shù)據(jù)集，設(shè)置種群規(guī)模NIND=40，迭代次數(shù)MAXGEN=50，每個(gè)算例獨(dú)立運(yùn)行10次。測(cè)試結(jié)果如表2所示。

表2 算法求解結(jié)果(最小化最大完工時(shí)間)

表1中，Oi,j為第i個(gè)工件的第j道工序，M1～M8為各加工機(jī)器。由圖6中的調(diào)度甘特圖可知，調(diào)度結(jié)果滿足表1算例的加工要求，驗(yàn)證了DFA在柔性作業(yè)車間調(diào)度問(wèn)題中的可行性。表2驗(yàn)證了DFA在柔性作業(yè)車間調(diào)度問(wèn)題中的準(zhǔn)確性。

將DFA與求解FJSP中應(yīng)用最為廣泛的2種傳統(tǒng)算法——遺傳算法(GA)和粒子群算法(PSO)進(jìn)行仿真對(duì)比。各算法的種群規(guī)模均為40，迭代次數(shù)均為50，得到各算法種群收斂對(duì)比圖如圖7所示。

圖7 算法種群收斂對(duì)比圖

由圖7可知，GA與PSO算法在尋優(yōu)過(guò)程中容易陷入局部最優(yōu)，從而導(dǎo)致收斂的效果不佳。DFA通過(guò)局部搜索可有效地避免算法陷入局部最優(yōu)，同時(shí)也增強(qiáng)算法的尋優(yōu)能力。

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

各種群智能優(yōu)化算法廣泛應(yīng)用于柔性作業(yè)車間調(diào)度問(wèn)題，但由于傳統(tǒng)的群智能優(yōu)化算法的尋優(yōu)能力不足，容易陷入局部最優(yōu)。本文針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題，將DFA引入FJSP，提出了一種全新的離散方式，并在此基礎(chǔ)上引入了局部搜索算子。通過(guò)對(duì)建立的柔性作業(yè)車間調(diào)度問(wèn)題的模型進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了DFA在求解FJSP問(wèn)題的可行性。通過(guò)與GA和PSO算法進(jìn)行對(duì)比，表明了DFA在求解FJSP問(wèn)題的優(yōu)越性。