黃海松，劉 凱，初光勇

(1.貴州大學(xué) 現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025； 2.銅仁職業(yè)技術(shù)學(xué)院 工學(xué)院，貴州 銅仁 554300)

0 引言

隨著生產(chǎn)力的不斷進(jìn)步，生產(chǎn)調(diào)度在制造企業(yè)中的地位越來越重要。在工作效率、成本、加工質(zhì)量等方面，生產(chǎn)調(diào)度成為影響企業(yè)的關(guān)鍵因素[1]，調(diào)度方案的優(yōu)劣會(huì)直接影響資源消耗和污染排放。因此，調(diào)度是生產(chǎn)計(jì)劃的制定、資源合理利用中最重要的一環(huán)，也是先進(jìn)制造和環(huán)保制造的研究方向[2]。

傳統(tǒng)的作業(yè)車間調(diào)度問題對(duì)加工工序可以使用的機(jī)器進(jìn)行了限制，柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem, FJSP)解除了機(jī)器選擇的限制，是在傳統(tǒng)問題上的擴(kuò)展，其為典型的NP-hard問題，并且柔性作業(yè)車間調(diào)度更符合目前實(shí)際的生產(chǎn)狀況[3]。相對(duì)其他算法而言，智能優(yōu)化算法在求解FJSP上具有獨(dú)特的優(yōu)勢，是目前的主流算法，如遺傳算法、粒子群算法、蜂群算法等。前人在這些算法上取得了很多成果，例如：Rahmati等[4]針對(duì)車間調(diào)度中的完工時(shí)間以及機(jī)器負(fù)載問題，通過融合兩種不同的排序方法改進(jìn)傳統(tǒng)的遺傳算法求解問題；張超勇等[1]針對(duì)交貨拖期、生產(chǎn)成本、最大完工時(shí)間和設(shè)備利用率等目標(biāo)，采用改進(jìn)的非支配遺傳算法(Non(dominated Sorting Genetic AlgorithmⅡ，NSGA-Ⅱ)求解問題；朱傳軍等[5]針對(duì)提高車間調(diào)度算法的穩(wěn)定性和魯棒性，將工件狀態(tài)、機(jī)器故障特點(diǎn)和調(diào)度策略結(jié)合，改進(jìn)了混合重調(diào)度策略；Li等[6]針對(duì)最大完工時(shí)間、機(jī)器的總工作量和關(guān)鍵機(jī)器工作量，通過融合多種局部搜索來提高算法的尋優(yōu)能力，提出了混合洗牌蛙跳算法；Luo等[7]針對(duì)流水車間，提出考慮不同電價(jià)的優(yōu)化調(diào)度算法；劉愛軍等[8]針對(duì)最大客戶滿意度和最大完工時(shí)間，提出一種縱橫改進(jìn)的多種群遺傳算法；徐華等[9]針對(duì)最大完工時(shí)間、生產(chǎn)成本和生產(chǎn)質(zhì)量，提出一種混合蝙蝠算法；李俊青等[10]針對(duì)最大完工時(shí)間、設(shè)備負(fù)荷及低碳環(huán)保等目標(biāo)，提出一種混合禁忌搜索算法；Karthikeyan等[11]提出混合離散螢火蟲算法求解以完工時(shí)間、機(jī)器工作量為目標(biāo)的優(yōu)化問題。

花朵授粉算法(Flower Pollination Algorithm, FPA)是劍橋大學(xué)Xin-She Yang教授[12]受自然界花朵授粉的啟發(fā)下提出的。自從該算法提出以來，已經(jīng)有許多學(xué)者將FPA應(yīng)用于各個(gè)領(lǐng)域，如整數(shù)規(guī)劃[13]、函數(shù)優(yōu)化[14]、產(chǎn)品序列拆裝[15]等，并取得了滿意的效果。FJSP問題是一個(gè)NP-hard問題，目前很少有學(xué)者將FPA應(yīng)用在FJSP問題上。綜合以上所述，針對(duì)車間調(diào)度的多個(gè)優(yōu)化目標(biāo)，包括最大完工時(shí)間、生產(chǎn)成本、加工質(zhì)量和能量消耗，本文提出一種離散花朵授粉算法(Discrete flower pollination algorithm, DFPA)對(duì)多目標(biāo)車間調(diào)度進(jìn)行求解：首先利用輪盤賭策略指派機(jī)器，避免初始種群的非可行解，其次提出改進(jìn)FPA進(jìn)行優(yōu)化，最后使用機(jī)器序列算法求解目標(biāo)值。與其他智能算法相比，本文算法的優(yōu)點(diǎn)有：生成較高質(zhì)量的初始種群，采用兩種不同搜索方式避免算法的早熟收斂，使用機(jī)器序列算法同時(shí)計(jì)算多個(gè)目標(biāo)。

通過實(shí)驗(yàn)驗(yàn)證并和其他算法比較，證明DFPA可以用于求解多目標(biāo)柔性車間調(diào)度問題(Multi-Objective Flexible Job-shop Scheduling Problem， MOFJSP)。

1 問題描述與模型建立

多目標(biāo)FJSP模型建立如下：n個(gè)加工工件集合J={J1,J2,J3,…,Ji,…,Jn}(i∈[1,n])，m臺(tái)加工機(jī)器集合M={M1,M2,M3,…,Mj,…,Mm}(j∈[1,m])，有以下約束條件：①工件的每一道工序都可以在第x臺(tái)機(jī)器上加工，x為可用機(jī)器集合，但只能被一臺(tái)機(jī)器加工完成；②工序在加工過程中不會(huì)被外力干擾，即機(jī)器不會(huì)出現(xiàn)停工現(xiàn)象;③機(jī)器在任何時(shí)刻可以停工,其最多只能加工一件工件。

為了之后的公式表達(dá)，引入以下符號(hào)，如表1所示。

表1 數(shù)學(xué)符號(hào)定義

本文的調(diào)度模型考慮生產(chǎn)時(shí)間(T)、生產(chǎn)成本(C)、加工質(zhì)量(Q)和能源消耗(E)4個(gè)優(yōu)化目標(biāo)，表示為min(T,C,Q,E)。各優(yōu)化目標(biāo)的具體計(jì)算方法如下：

(1)加工時(shí)間 最大加工時(shí)間

(1)

(2)加工成本 加工成本分為材料成本和加工成本兩部分，其中：

1)材料成本

(2)

式中mci為第i個(gè)工件的原材料成本。

2)加工成本

(3)

因此，最終的加工成本

C=MC+PC。

(4)

(3)加工質(zhì)量 一臺(tái)機(jī)器的性能優(yōu)劣由該機(jī)器生產(chǎn)成品的不合格率反映，不合格率越高，機(jī)器的加工質(zhì)量越差。并且隨著工件的不斷加工，后期出現(xiàn)不合格工序所造成的損失大于前期，故加工質(zhì)量

(5)

(4)能源消耗 能源消耗包括啟動(dòng)能源消耗、加工能源消耗、空載能源消耗，即

E=∑Es+∑En+∑Ep。

(6)

式中：∑Es表示啟動(dòng)能耗；∑En表示空載能耗；∑Ep表示加工能耗。

2 離散花朵授粉算法

原始的FPA應(yīng)用于求解連續(xù)函數(shù)極值上。本文通過重新定義FPA的兩種授粉方式，提出了離散的FPA。

2.1 編碼與解碼

求解MOFJSP首先需要進(jìn)行編碼，編碼方式的選擇直接決定算法運(yùn)行的速度和準(zhǔn)確性。傳統(tǒng)算法大多選擇雙層整數(shù)編碼方式，但工序?qū)拥木幋a序列經(jīng)FPA更新迭代后因產(chǎn)生大量非可行解而難以處理，增加了算法的復(fù)雜度，不適用于本算法。本文采用基于工序的單層編碼[9]，編碼的形式為

O={M1,M2,M3,…,Mλ}。

例如，一個(gè)基于工序的單層編碼入圖1所示，圖中共有4個(gè)工件和5臺(tái)機(jī)器，每個(gè)工件的待加工工序的數(shù)分別是2，3，3，3，其中的一個(gè)工序編碼為O={2 5 1 3 5 2 4 1 3 2 1}，由編碼序列和每個(gè)工件的工序數(shù)可以得到11道工序，即O序列的長度。工件1共有2道工序，O(1)=2，O(2)=5表示工件1的第1道工序在2號(hào)機(jī)器上加工，工件1的第2道工序在5號(hào)機(jī)器上加工；工件2有3道工序，O(3)=1，O(4)=3，O(5)=5表示工件2的第1道工序在1號(hào)機(jī)器上加工，工件2的第2道工序在3號(hào)機(jī)器上加工，工件3的第3道工序在5號(hào)機(jī)器上加工。以此類推。

完成編碼后需要進(jìn)行解碼操作，解碼的結(jié)果存入矩陣PT中。矩陣PT為4×n的矩陣，n為總工序數(shù)，O的解碼矩陣

式中：第1行表示工件號(hào)；第2行表示工序號(hào)；第3行表示加工機(jī)器號(hào)；第4行表示該工序在對(duì)應(yīng)機(jī)器上的加工時(shí)長。例如第1列表示工件1的第1道工序在2號(hào)機(jī)器上加工，時(shí)間為1；第2列表示工件1的第2道工序在5號(hào)機(jī)器上加工，時(shí)間為2，以此類推。

2.2 輪盤賭均值派選

調(diào)度目標(biāo)值的優(yōu)劣取決于編碼序列的優(yōu)劣，提高初始種群的質(zhì)量不僅可以縮短求解目標(biāo)值的運(yùn)行時(shí)間，還可以增強(qiáng)算法的搜尋能力，因此機(jī)器的選派對(duì)解的質(zhì)量起至關(guān)重要的作用。因?yàn)槿嵝攒囬g調(diào)度具有所產(chǎn)生的編碼為非可行解，以及編碼和結(jié)果不存在明顯映射關(guān)系的特性，所以使用混沌序列方法產(chǎn)生的部分編碼為非可行解，而反向搜索需要考慮非可行解與可行解的關(guān)系，其過程過于復(fù)雜。輪盤賭策略既滿足了剔除非可行解、快速生成初始種群的要求，又保存了所有可用機(jī)器被選中的可能性，滿足了初始種群的多樣性。綜上，本文提出一種平均值與輪盤賭算法相結(jié)合的方法構(gòu)建初始種群解。

2.2.1 工序指派

對(duì)于任意兩個(gè)工件i,j(i≠j)且λi=λj,在第λ道工序上有

(7)

(8)

(9)

此時(shí)生成一個(gè)隨機(jī)數(shù)p∈(0,1)，若0

其中：ti，tj分別是工件i，j在第λ道工序上可使用的機(jī)器數(shù)量；Mi,λ(k)，Mj,λ(k)表示工件i，j第λ道工序的第k臺(tái)加工機(jī)器。

指派的基本思想是，先計(jì)算出可以加工該工件、工序的所有機(jī)器加工時(shí)間的總和，再分別求出工件對(duì)應(yīng)的概率，最后生成一個(gè)隨機(jī)數(shù)p，p落入哪個(gè)區(qū)間，就優(yōu)先加工該區(qū)間對(duì)應(yīng)的工件工序。指派原則是優(yōu)先加工平均值較大的工序。

2.2.2 機(jī)器指派

工序確定后，為了避免出現(xiàn)二次編碼現(xiàn)象，通過輪盤賭的方式選取機(jī)器。以3臺(tái)機(jī)器為例,具體流程如下：

(1)將表2中的加工時(shí)間從小到大排序，相應(yīng)地調(diào)整第1行機(jī)器號(hào)碼的次序。

表2 二維機(jī)器編碼

(2)計(jì)算全部加工時(shí)間的總和∑Tj和每個(gè)工件j所占的比例pj，

(10)

(3)產(chǎn)生一個(gè)隨機(jī)數(shù)g并滿足g∈(0,1)，如果0

由以上可以得出：2號(hào)機(jī)器不能加工該工序所以是0，故不會(huì)被指派。并且由式(10)可知用時(shí)越短的機(jī)器所占的比例越大，被指派的概率也越大，同時(shí)保存了其他可執(zhí)行機(jī)器被選中的可能，滿足初始種群的多樣性并且不會(huì)產(chǎn)生非可行解。

2.3 選擇操作

多目標(biāo)問題與單目標(biāo)問題的最大區(qū)別在于多目標(biāo)存在非支配解。本文采用適應(yīng)度函數(shù)與聚集距離選擇非支配解。

2.3.1 適應(yīng)度計(jì)算

為了評(píng)價(jià)編碼的優(yōu)劣程度，引入帶有權(quán)重系數(shù)的適應(yīng)度函數(shù)，將每個(gè)個(gè)體的各個(gè)目標(biāo)值與隨機(jī)權(quán)重系數(shù)結(jié)合，然后線性組合得到個(gè)體的適應(yīng)度，計(jì)算公式為

(11)

2.3.2 個(gè)體選擇

對(duì)所得到的種群按照從大到小的順序進(jìn)行選擇，適應(yīng)度相同的個(gè)體需要通過一定策略進(jìn)行篩選。本文采用聚集距離策略，該策略的優(yōu)點(diǎn)是群體具有多樣性。聚集距離的計(jì)算公式為

(12)

為維持種群多樣性，聚集距離大的個(gè)體將參與下一次迭代。

2.4 面向MOFJSP的花朵授粉算法

FPA的基本步驟如下：

步驟1參數(shù)初始化，包括花朵初始種群的規(guī)模、轉(zhuǎn)換概率p等。

步驟2計(jì)算種群里每個(gè)變量的解，并求出當(dāng)前種群中的適應(yīng)度值和所對(duì)應(yīng)的解。

步驟3生成隨機(jī)數(shù)rand，如果p>rand,則按式(13)處理，否則按式(14)處理。

(13)

(14)

步驟4計(jì)算新解對(duì)應(yīng)的適應(yīng)度值，若新解對(duì)應(yīng)的適應(yīng)度較優(yōu)，則用新解和對(duì)應(yīng)的函數(shù)值替代當(dāng)前解和當(dāng)前解得的函數(shù)值。

步驟5通過前文的選擇策略更新外部精英解集。

步驟6判斷迭代次數(shù)。若達(dá)到結(jié)束條件，則退出程序，輸出最優(yōu)解和最優(yōu)值，否則轉(zhuǎn)步驟3。

對(duì)于MOFJSP這種離散問題，求解的難點(diǎn)在于花朵個(gè)體的定義，以及兩種授粉規(guī)則不能直接用于處理編碼更新。因此，本文構(gòu)建一種DFPA重新定義花朵的個(gè)體及兩種授粉方式，方法如下:

(1)定義花朵

為了便于之后運(yùn)算和比較，將種群中的花朵定義為一條編碼

X=[M1,M2,M3,…,Mi,…,Mλ]。

(2)定義授粉方式

這里涉及兩個(gè)序列的加減，即編碼里每個(gè)位置的數(shù)對(duì)應(yīng)相加減。例如：假設(shè)A=(1,2,3,4)，B=(4,2,2,3)，則C=A-B=(1,2,3,4)-(4,2,2,3)=(-3,0,1,1)，D=A+B=(1,2,3,4)+(4,2,2,3)=(5,4,5,7)。

因此兩種不同的授粉方式改為：

(15)

(16)

對(duì)產(chǎn)生的新解可行性進(jìn)行判斷和處理，處理方法如下：①對(duì)編碼進(jìn)行掃描并剔除不能使用的機(jī)器編號(hào)或不在機(jī)器集合里的編號(hào);②使用上文所述的機(jī)器指派原則將編碼補(bǔ)充完整，保證加工該工序的機(jī)器大概率為性能較好的機(jī)器。

2.5 機(jī)器序列算法

確定編碼并安排各個(gè)工件的工序先后順序之后，需要計(jì)算各個(gè)目標(biāo)值，因?yàn)楸疚墓灿?個(gè)優(yōu)化目標(biāo)，所以提出一種可一次性計(jì)算出編碼序列4個(gè)目標(biāo)值的機(jī)器序列算法，具體內(nèi)容如下：

首先生成一個(gè)9×l×m機(jī)器矩陣，其中l(wèi)為總工序數(shù)，m為加工機(jī)器數(shù)。將編碼進(jìn)行擴(kuò)展，生成一個(gè)擴(kuò)充矩陣，矩陣包括加工時(shí)長、能量消耗、加工質(zhì)量等系數(shù)。一次讀取擴(kuò)展矩陣?yán)锏男畔?，并將信息填充進(jìn)機(jī)器矩陣中。最后檢索機(jī)器矩陣，輸出4個(gè)目標(biāo)值。

機(jī)器序列算法的偽代碼如下：

l//工序編碼序列

pi//機(jī)器第幾次執(zhí)行加工

ST//記錄工序時(shí)間

MT//機(jī)器矩陣

SizeX//計(jì)算編碼長度

begin

輸入編碼序列x

X//將其變成擴(kuò)展矩陣

for i=1 to sizeX

X(:,i)//讀取擴(kuò)展矩陣數(shù)據(jù)

a1=X(1，i)//記錄工件號(hào)

a2=X(2，i)//記錄工序號(hào)

a3=X(3，i)//記錄機(jī)器號(hào)

If(p<2)//判斷該機(jī)器是否為第一次執(zhí)行

MT=X//將X的信息按照前文公式計(jì)算后賦值給MT,包括成本、質(zhì)量系數(shù)、能耗

If(a2

ST(a1，a2)=MT(4，pi，a3)//完成時(shí)間作為下一道工序的開始時(shí)間

end

else

if (ST(a1，a2)

ST(a1,a2)=MT(4，pi-1，a3)

end

MT=X//將X的信息按照前文公式計(jì)算后賦值給MT,包括時(shí)間、成本、質(zhì)量系數(shù)、能耗

If(a2

ST(a1，a2)=MT(4，pi，a3)//完成時(shí)間作為下一道工序的開始時(shí)間

end

end

end

根據(jù)矩陣MT計(jì)算目標(biāo)值

輸出完工時(shí)間、加工成本、能源消耗、加工質(zhì)量

end

其中：lo為工序存儲(chǔ)序列，是l×n矩陣，n為工件數(shù)；pi為機(jī)器加工記錄矩陣，記錄機(jī)器第幾次使用，是l×m矩陣，m為機(jī)器總數(shù)；ST為工序時(shí)間，是n×l矩陣，行數(shù)表示工件編號(hào)，列數(shù)表示工序編號(hào)；MT為機(jī)器矩陣，是9×l×m矩陣，第1～9行分別記錄工件、工序、開始裝夾時(shí)間、開始加工時(shí)間、開始卸夾時(shí)間、完成時(shí)間、成本、能耗、質(zhì)量系數(shù)；X為編碼序列擴(kuò)展矩陣，是9×L矩陣，Len為編碼序列長度，第1～9行分別記錄工件、工序、加工機(jī)器、裝夾時(shí)長、加工時(shí)長、卸夾時(shí)長、成本、能耗、質(zhì)量系數(shù)。

2.6 算法流程

參數(shù)初始化包括花朵種群的規(guī)模N、授粉方式轉(zhuǎn)化概率p和最大迭代次數(shù)MaxIter。FPA流程圖如圖2所示。

3 實(shí)驗(yàn)仿真與分析

本文算法采用MATLAB軟件編程實(shí)現(xiàn)，計(jì)算機(jī)硬件條件：處理器為Core i5 2.5 GHz，內(nèi)存為4 GB。下面分別從初始種群驗(yàn)證、關(guān)鍵參數(shù)設(shè)定、測試DFPA求解FJSP的性能、實(shí)例測試4個(gè)方面進(jìn)行說明。

3.1 初始種群驗(yàn)證

采用Kacern算例中的8×8算例，對(duì)比不同的初始種群生成策略，結(jié)果如表3所示。

表3 初始種群生成策略結(jié)果對(duì)比

由表3可以看出混沌序列的可行解為3，原因是一條序列中任意一個(gè)編碼選擇錯(cuò)誤，這條序列就是非可行序列，故其可行解較少。雖然采用反向搜索和輪盤賭策略的運(yùn)行結(jié)果均為120，但是反向搜索策略需要對(duì)非可行編碼進(jìn)行處理，而輪盤賭策略不需要考慮非可行解，因此反向搜索較為復(fù)雜，性能不如輪盤賭策略。

3.2 關(guān)鍵參數(shù)設(shè)定

種群規(guī)模和迭代次數(shù)參考文獻(xiàn)[15]，3個(gè)參數(shù)中對(duì)結(jié)果影響較大的參數(shù)是轉(zhuǎn)換率p，設(shè)置不同的p值并運(yùn)行20次的結(jié)果如表4所示。

表4 不同P值的實(shí)驗(yàn)結(jié)果

從表4可以看出，當(dāng)p=0.5時(shí)，無論算法的收斂性如何，尋優(yōu)性都達(dá)到最好。DFPA初始參數(shù)如表5所示。

表5 離散花朵授粉算法初始參數(shù)設(shè)置

3.3 算法性能測試

為了驗(yàn)證本文算法的性能，采用經(jīng)典文獻(xiàn)中的算例作為樣本，并將運(yùn)算結(jié)果與文獻(xiàn)中的結(jié)果進(jìn)行對(duì)比。

算例1數(shù)據(jù)來源于文獻(xiàn)[16]，有3個(gè)待加工工件和6臺(tái)執(zhí)行機(jī)器。本文的DFPA對(duì)算例1進(jìn)行計(jì)算，得到的最小完工時(shí)間為123，對(duì)應(yīng)最優(yōu)解的甘特圖如圖3所示。

算例2數(shù)據(jù)來源于文獻(xiàn)[17]，分別有6個(gè)待加工工件和6臺(tái)執(zhí)行機(jī)器，得到的最小完工時(shí)間為200，對(duì)應(yīng)的最優(yōu)解的調(diào)度甘特圖如圖4所示。

算例3為了比較本算法的性能與其他算法的性能，采用標(biāo)準(zhǔn)算例Kacern中的一個(gè)8×8標(biāo)準(zhǔn)算例進(jìn)行實(shí)驗(yàn)，并與最新研究成果對(duì)比，結(jié)果證明DFPA可以找到全局最優(yōu)解14，調(diào)度甘特圖如圖5所示。

通過表6可以得出本文DFPA找到的最優(yōu)解優(yōu)于前兩個(gè)文獻(xiàn)的結(jié)果，且最優(yōu)解比文獻(xiàn)[16]的算法提高了8.2%，比文獻(xiàn)[17]的算法提高了11.8%，第3個(gè)算例的解與目前最新研究成果相同。表7所示為本文算法求解3個(gè)算例的運(yùn)行時(shí)間和達(dá)到最優(yōu)結(jié)果的次數(shù)。通過表8與經(jīng)典算法的運(yùn)行時(shí)間對(duì)比，得出在時(shí)間復(fù)雜度方面FPA與經(jīng)典算法相差不大。綜上得出,本文所提DPFA在求解MOFJSP上是可行的，并且性能不差于經(jīng)典文獻(xiàn)的算法。

表6 3個(gè)算例結(jié)果比較

表7 算法得到的最優(yōu)計(jì)算時(shí)間和迭代次數(shù)

表8 經(jīng)典算法運(yùn)行時(shí)間

3.4 實(shí)例仿真

實(shí)例來源于文獻(xiàn)[20]，其中加工工件數(shù)n=6，加工機(jī)器數(shù)m=6，工序的加工時(shí)長、裝夾時(shí)長等具體數(shù)據(jù)如表9所示。

文獻(xiàn)[20]給出加工時(shí)間、加工成本、加工質(zhì)量和加工能耗的最優(yōu)值分別為89，782.4，292.38，444.65。運(yùn)行相同的算例，本文DFPA求得的最小最大完工時(shí)間為79.4，最小加工成本為768.4，最優(yōu)加工質(zhì)量為273.681，最小加工能耗為423.363。通過對(duì)比相同優(yōu)化目標(biāo)的最優(yōu)值可以得出，本文DFPA在求解調(diào)度問題上優(yōu)于文獻(xiàn)[20]的算法。圖6～圖9分別表示完成時(shí)間、加工成本、加工質(zhì)量和能源消耗的迭代過程。

圖6～圖9終止收斂次數(shù)不同的原因如下：

(1)優(yōu)化目標(biāo)不同，不同優(yōu)化目標(biāo)最終的收斂次數(shù)可能不相同。雖然能量消耗和成產(chǎn)質(zhì)量終止次數(shù)相近，但是由圖8和圖9可以看出其優(yōu)化過程完全不同。

(2)因?yàn)镕PA的授粉方式有兩種且存在編碼修補(bǔ)的隨機(jī)性，所以迭代結(jié)果會(huì)產(chǎn)生差異。運(yùn)行20次實(shí)例，由于有4個(gè)目標(biāo)，共80次結(jié)果，收斂次數(shù)如表10所示，通過表10驗(yàn)證了之前的結(jié)論。

表9 實(shí)例數(shù)據(jù)

表10 收斂次數(shù)統(tǒng)計(jì)

收斂次數(shù)0～200200～300300～400400～500結(jié)果165122

通過刪除重復(fù)個(gè)體，最終得到包含50組解的解集,如表11所示。

表11 最終得到的50組解集

續(xù)表11

算法的最終結(jié)果為車間調(diào)度提供一系列的不同解。在實(shí)際生產(chǎn)中，決策者根據(jù)不同的生產(chǎn)要求對(duì)4個(gè)優(yōu)化目標(biāo)設(shè)置不同的權(quán)重，本文沿用文獻(xiàn)[20]提出的權(quán)重系數(shù)，令T,C,Q,E的權(quán)重系數(shù)分別為0.5,0.3,0.1,0.1。從表7得出第3組解為最優(yōu)解，目標(biāo)值為完工時(shí)間79.4、加工成本795.1、能源消耗561.402、加工質(zhì)量555.927。對(duì)應(yīng)的調(diào)度甘特圖如圖10所示。

4 結(jié)束語

本文以最大完工時(shí)間、加工成本、能源消耗和加工成本為優(yōu)化目標(biāo)，改進(jìn)了FPA。為了使算法運(yùn)行更加有效，選擇基于工序的單層編碼方式；為了解決所生成初始種群質(zhì)量較低的問題，采用輪盤賭機(jī)器派選方式。重新定義了FPA中的兩種授粉方式，并采用可以同時(shí)計(jì)算多個(gè)目標(biāo)值的機(jī)器序列算法計(jì)算目標(biāo)值。最后通過算例驗(yàn)證了DFPA的基本性能，實(shí)例證明該算法可以求解實(shí)際問題。未來將針對(duì)生產(chǎn)工廠分布的分散性和生產(chǎn)過程的不確定性改進(jìn)FPA的算子，研究分布式車間的調(diào)度策略。