程 強， 高元杰， 初紅艷， 張彩霞， 劉志峰

(1.北京工業(yè)大學先進制造與智能技術(shù)研究所， 北京 100124；2.北京工業(yè)大學先進制造技術(shù)北京市重點實驗室， 北京 100124；3.北京工業(yè)大學機械工業(yè)重型機床數(shù)字化設計與測試技術(shù)重點實驗室， 北京 100124)

調(diào)度研究的問題簡單來說就是如何將稀缺資源分配，即將資源給在一定時間內(nèi)的不同任務. 調(diào)度在大多數(shù)制造和生產(chǎn)系統(tǒng)及信息處理環(huán)境中扮演著重要的角色[1]. 目前關于調(diào)度的研究主要涉及模型建立和算法設計，其中問題建模主要研究調(diào)度模型、調(diào)度規(guī)則、目標函數(shù)等，而調(diào)度算法設計主要研究算法復雜性、算法收斂性、算法質(zhì)量等[1-6].

目前，關于柔性作業(yè)車間的模型調(diào)度建立國內(nèi)外都有相關的研究. Willian[7]作為調(diào)度理論的奠基人，提出了車間調(diào)度，開創(chuàng)了調(diào)度問題的理論研究工作. 針對多品種、多件數(shù)的工件調(diào)度難的問題，Low[8]和Chinyao等[9]在柔性作業(yè)車間模型的基礎上考慮了分批調(diào)度，建立了柔性作業(yè)車間分批處理模型，基于其數(shù)學模型的研究表明：在作業(yè)車間中，通過分批處理可減少機床閑置時間和工件流動時間. Jeong等[10]在分批調(diào)度的基礎上進一步建立單工藝路線生產(chǎn)車間動態(tài)批量分批作業(yè)計劃，將生產(chǎn)輔助時間(setup times)和加工時間(process times)進行了區(qū)分. 與此同時，一種考慮返工的數(shù)學模型也開始被提出. 陳建國等[11]針對傳統(tǒng)Job-Shop數(shù)學模型忽略返工及重加工的因素，構(gòu)建了考慮該情形下的Job-Shop調(diào)度數(shù)學模型及相應的求解算法. 廖怡娜等[12]建立了考慮作業(yè)返工的資源受限項目調(diào)度問題的數(shù)學模型，針對該模型，設計了面向3種不同情況的修復算法. Ceylan等[13]針對多階段供應鏈網(wǎng)絡的特點，將多階段供應約束考慮到模型中，建立了雙目標混合整數(shù)線性規(guī)劃模型，提出了一個新的協(xié)調(diào)調(diào)度. 目前調(diào)度模型研究主要圍繞著設置約束條件和優(yōu)化目標等進行研究，主要包括返工、批量、資源受限等約束條件和能耗、最大完工時間和最大延長時間等優(yōu)化目標，但是大部分研究關于約束條件的設定較為簡單，譬如文獻[11]將返工率視為固定值，文獻[10]的準備時間不受工序次序影響等. 而且在機加工中，刀具的成本往往也占很大的比重，且刀具也屬于易耗品，但是關于以刀具作為調(diào)度優(yōu)化目標的研究還較少，因此本文在前人研究的基礎上，將機加工的常見約束如批量約束、基于貝葉斯條件概率求返工概率和受次序影響的準備時間等考慮至模型中，并結(jié)合機加工中的刀具損耗特點進行建模，提出一種新的機加工柔性車間調(diào)度批量模型，使模型更加符合實際生產(chǎn)需求，最終提出一種以最大完工時間、能耗和刀具損耗數(shù)量為優(yōu)化目標，考慮返工、序列的準備時間和以批量作為約束的多目標機加工柔性作業(yè)車間調(diào)度模型，并采取差分進化算法進行求解.

1997年，差分進化(differential evolution,DE)[14]算法由Storn提出，其初衷是解決切比雪夫多項式問題. 作為一種基于群體導向的隨機搜索技術(shù)，DE算法包括初始化、變異、交叉以及選擇等操作[15]. 由于算法原理較為簡單、參數(shù)較少、魯棒性較好并且易于實現(xiàn)，因此已有部分研究應用于車間調(diào)度問題[16-17]中. 傳統(tǒng)差分進化算法在解決本文提出的多目標機加工柔性作業(yè)車間調(diào)度模型時，由于隨機初始化導致算法求解時間較長，在短期內(nèi)不能得到較好的調(diào)度結(jié)果，同時由于生產(chǎn)條件的復雜性，機器差分運算得到的差分向量較差，因此需要進行一定的改進. 目前針對DE算法的理論研究主要集中在如何提高算法的尋優(yōu)能力、收斂速度以及克服啟發(fā)式算法常見的早熟收斂以及搜索停滯等缺陷方面[15]，本文從模型特點出發(fā)，提出一種初始化策略和機器選擇策略分別對差分進化算法的收斂速度和解的質(zhì)量進行一定程度上的改進.

1 多目標機加工柔性作業(yè)車間調(diào)度模型

多目標機加工柔性作業(yè)車間調(diào)度可定義為：有N類工件在M臺機器加工，每類工件包含若干道工序，每道工序再分成若干個任意大小的批次，工序可在多臺不同性能的機器上進行作業(yè)操作，由于機器性能的不同，工序在不同機器上的加工時間是不同的，同時，能耗和刀具磨損也是不同的. 因此工序在不同的機器上加工，調(diào)度指標除了最大加工時間外，還有能耗指標和刀具壽命指標. 多目標機加工柔性作業(yè)車間調(diào)度所要解決的問題是：

1) 確定各個工件劃分批次數(shù)量及各批次大小.

2) 確定各子批在哪臺機器設備上加工.

3) 確定最優(yōu)的工序加工順序.

4) 在多約束條件下求得較優(yōu)多目標調(diào)度方案.

1.1 變量定義

為了方便后續(xù)模型和算法描述，定義了下列相關變量用于描述數(shù)學模型.

N：工件類別數(shù).

M：機器總數(shù).

H：工序總數(shù).

Ω：總的機器集.

i：工件類別號，i=1,2,…,N.

k：機器序號，k=1,2,…,M.

j：工序序號，j=1,2,…,H.

ni：每類工件的件數(shù)，i∈{1,2,…,N}.

Bi：每類工件的批數(shù)，i∈{1,2,…,N}.

li,b：每類工件的子批的工件數(shù)，b∈{1,2,…,Bi}.

ti,li,b,j,S:i類工件的li,b子批j工序起始加工時間.

ti,li,b,j,E:i類工件的li,b子批j工序終止加工時間.

ti,j,k,P:i類工件j工序在機器k上的加工時間.

ti,j,k,R:考慮返工的i類工件的j工序在機器k上的加工時間.

ri,j,k:i類工件的j工序在機器k上的加工不合格返工概率.

Xi,li,b,j,k:如果i類工件的li,b子批的j工序在機器k加工則為1，否則為0.

tk,C：機器k上最后一個子批工序的完工時間,k=1,2,…,M.

tCmax：最大完工時間.

1.2 數(shù)學模型

模型以優(yōu)化最大完工時間、能耗和刀具損壞數(shù)為優(yōu)化目標，首先建立批量約束.

每類工件分批后，該類工件的每個子批的工件數(shù)量之和為該類工件的總件數(shù).

(1)

根據(jù)Xi,li,b,j,k的含義可知，每類工件的子批的每道工序同一時刻只能在一臺設備上進行加工.

(2)

各子批在加工時存在工序先后順序約束,tsetup為加工前準備時間，取決于上一工件和目前工件的類別.

ti,li,b,j+1,S≥ti,li,b,j,E
ti,li,b,j,E=ti,li,b,j,S+tsetup+ti,j,k,R×li,b

(3)

考慮到加工過程中不合格返工現(xiàn)象常有發(fā)生，將返工這一動態(tài)問題轉(zhuǎn)換為靜態(tài)問題進行處理，在已知ti,j,k,P的基礎上為返工預留加工時間

ti,j,k,R=ti,j,k,P+ri,j,k×ωP

(4)

式中ωP是由MES系統(tǒng)中的歷史數(shù)據(jù)所得，表示考慮不同概率下加權(quán)的返工修復時長.

通過統(tǒng)計可以常見地求得加工條件不合理的先驗概率：P(X=A)、P(X=B)、P(X=C).其中X表示加工條件不合理的隨機事件，A、B、C分別表示人操作不規(guī)范、毛坯不合格和機床加工性能不達標事件.

進一步地，經(jīng)過統(tǒng)計可以獲得在加工條件不合理時，工件不合格的條件概率：P(Y=不合格|X=A)、P(Y=不合格|X=B)和P(Y=不合格|X=C).最后根據(jù)統(tǒng)計的先驗概率和條件概率，計算當工件出現(xiàn)不合格時，各種加工條件不合理情況發(fā)生的后驗概率，并基于后驗概率和各種加工條件不合理的情況下的平均修復時長，通過概率加權(quán)設計預留的返工時長，其中tR,person、tR,workblank、tR,machine表示統(tǒng)計所得在各種不合理條件下進行修復的平均時長.

ωP=P(X=A|Y=不合格)×tR,person+
P(X=B|Y=不合格)×tR,workblank+
P(X=C|Y=不合格)×tR,machine

(5)

最后讓ti,j,k,R與子批li,b工件數(shù)量相乘，表示i類工件的子批li,b的j工序在機器k上的加工時長.

因為工件在機器的準備時間取決于上一工件，因此考慮帶有工件次序的準備時間，tMatrix為考慮序列準備時間矩陣，其中行與列表示工件和工件之間如果在機器上相鄰時，切換工作環(huán)境的準備時間.

(6)

最大完工時間取決于機器最后一個子批完工時間的最大值, 即

tCmax=max(t1,t2,…,tM)

(7)

以最后一個子批完工時間為優(yōu)化目標：min(tmax)，同時為考慮機床機加工過程中的能耗，建立了模型[18]

Ek=Pk,ftk,f+Pk,airtk,air+Pk,vtk,v

(8)

式中:Pk,f、Pk,air和Pk,v分別表示機床k待機功率、空載功率以及切削功率; 而tf、tair和tv為其對應的時間.

此機加工能耗模型，主要由3個部分構(gòu)成，分別是待機能耗、空載能耗以及切削能耗.

Pk,air與主軸轉(zhuǎn)速相關， 且

Pk,air=An2+Bn+C

(9)

式中A、B、C取決于機床特性和主軸轉(zhuǎn)速.類似地，Pk,f和Pk,v也取決于機床特性，可通過實驗觀測求得.

因此，可以得到

(10)

以能耗作為優(yōu)化目標：min(Etotal)，同時應注意，在切削速度增大的同時，依據(jù)文獻[18]給出的模型，可以推測得出切削速度增大盡管能縮短加工時長，但是卻會一定程度上增加能耗的結(jié)論.

由于在機加工過程中，機床在給定的工藝參數(shù)下，刀具壽命是固定的，以銑削的方式進行加工的刀具壽命[19]

(11)

式中Ti,j,k表示i類工件的j工序在機器k以確定的工藝參數(shù)加工下刀具的壽命.工藝參數(shù)中Vc為切削速度，fz為每齒進給量，ap為軸向切深，ae為徑向切深.

在文獻[19]中，所求得的b1、b2、b3、b4分別為-2.929 8、-1.912 8、-1.511 9和-1.141 3，這表明切削速度對刀具壽命影響非常顯著，實際經(jīng)驗表明切削速度越大，切削區(qū)溫度越高，刀具磨損程度越大，刀具壽命越短，這與所求得的公式是一致的.

考慮到刀具也有成本，通過計算在此工藝下子批的累計加工時長，讓累計加工時長除以該工藝下的刀具壽命，可大概估算出預計耗費刀數(shù)

(12)

式中Ni,j,k,tool為所有i類工件的子批的j工序在機器k上加工累計耗費的刀具數(shù)，通過對每個設備實際加工時間進行累加求和，然后將累加求和的時間除以刀具預估壽命即可求得.

因此考慮所有子批的刀具磨損情況，以刀具損壞數(shù)量為優(yōu)化目標

其余假設條件如下.

1) 已知每類工件總批量數(shù)，劃分子批后每批次的工件在一起加工.

2) 同種工件每個子批的每道工序可以選擇不同設備進行加工.

3) 每臺設備在同一時刻只能加工某類工件某批次的一道工序.

4) 某工序一旦于設備上開始加工，不允許中斷.

2 差分進化算法設計

考慮到傳統(tǒng)差分進化算法在本文調(diào)度模型的應用上效果不佳，為得到較優(yōu)解，在傳統(tǒng)差分進化算法的基礎上進行一定的改進，主要對初始化策略和差分操作進行改進.

2.1 編碼方式與解碼方式

本文采取以工序為基準的編碼方式，以10個工件5道工序6個機器為例，總工序為10×5=50道工序.為50道工序分配機器，因此染色體中還需要為50個工序預留50個機器位置，染色體總長度為100，為方便解碼，設定染色體前一半部分代表的是工序，后一半部分代表的是加工該工序?qū)臋C器，其中染色體機器位置部分第1～5個位置表示工件1的第1道工序到第5道工序所選擇的機器，第6～10個位置表示工件2的第1道工序到第5道工序所選擇的機器，以此類推，如圖1所示.

圖1 編碼圖Fig.1 Coding diagram

工件的個數(shù)計算方式為

(13)

表示將每個子批作為一個工件視為調(diào)度，因此確定好如何分批和每批的批數(shù)問題也是本文關注點之一.考慮到當使用等分批不能使結(jié)果更加優(yōu)化時，才考慮用其他分批策略[20]，因此采用等分批進行分批，為確定批數(shù)，根據(jù)經(jīng)驗所得劃分的批次判定公式[21]進行批數(shù)確定.

(14)

式中:Tz為考慮分批的時間參數(shù)，即最小加工時間；H為工序數(shù)；l為批數(shù)；tj為某工件第j工序的加工時間;tL為最長工序的加工時間；Kz為子批中包含的工件數(shù).

分批算法的基本流程如下.

1) 初始化參數(shù)，令x=1，n=1，x表示工件類別，n表示批數(shù).

2) 將x分成n批，按式(14)求得Tz，即此類工件分批時間參數(shù).

3) 若n

4) 計算批數(shù)為1,2,…,nx批的時間參數(shù)Tz.

5) 從4)計算得到的一組Tz中找到最小的Tz，存儲并輸出此時的批數(shù)n.

6) 若x

解碼時將染色體中的工序部分編碼和機器部分編碼分別與加工信息表一一對應，如表1所示，可獲取每類工件的每道工序的加工時長和能耗信息，并將其代入各個適應度函數(shù)進行求解，進行解碼.

表1 5種類-4工序-6機器加工信息

2.2 多目標適應度函數(shù)設計

在實際生產(chǎn)中，調(diào)度常常需要滿足多目標的任務需求，為此，需要將多個目標進行綜合考慮，本文考慮各目標的單位成本生成多目標適應度函數(shù)

Ftotal=Ctool×Ntool+Cenergy×Etotal+Ctime×tCmax

(15)

式中Ctool、Cenergy和Ctime分別為對應目標的單位成本，可根據(jù)企業(yè)生產(chǎn)的實際情況獲取，而Ntool、Etotal和tCmax可分別根據(jù)式(12)(10)和(7)求得.

2.3 初始化種群

傳統(tǒng)差分進化算法中，使用隨機初始化對種群進行初始化，種群的全局性雖然能夠得到保證，但是個體質(zhì)量較差，將導致迭代次數(shù)過多才能獲得較優(yōu)個體，為保證全局性，同時一定程度上提高初始種群的質(zhì)量，本節(jié)在編碼的工序部分采用隨機初始化，而機器部分考慮到模型的多目標特點，提出一種綜合考慮能耗和加工時間的輪盤賭初始化策略，這種初始化策略縮短了差分進化算法的運行時間，一定程度上改進了差分進化算法.

首先確定好種群個體的數(shù)量，之后，對每個個體進行以下初始化操作，初始化流程如下.

1) 工序初始化

根據(jù)工件分批的批數(shù)，確定工件數(shù)量，根據(jù)每工件的工序數(shù)量確定工序總數(shù)，例如工件共有15件，工序4道，生成4個1、4個2……4個15，然后將生成60道工序亂序處理，其中第1個1表示工件1的第1道工序，第2個1表示工件1第2道工序，以此類推，其余工件類似.

2) 機器初始化

① 開始循環(huán)，令i=1.

② 循環(huán)讀取已生成的工序部分，獲取每工序的所有可用設備的加工時長和能耗，基于輪盤賭規(guī)則生成相應的數(shù)據(jù)矩陣.

③ 生成隨機數(shù)，根據(jù)隨機數(shù)在該工序?qū)旧w的機器位置查輪盤賭數(shù)據(jù)矩陣所對應的機器部分，為該位置賦值找到的機器.例如，某工件的工序1有3個機器可以選擇，機器1、機器2、機器3對應的加工時間分別為6、3、2 h，而能耗分別為12、5、2 kW·h，此時基于自定義的輪盤賭規(guī)則，考慮模型中的優(yōu)化目標能耗和加工時長，假設以0.75表示考慮能耗的權(quán)重，0.25表示考慮時長的權(quán)重，則該工序選擇機器1進行加工的概率區(qū)間為

P1=[0～(6÷11×0.75+12÷19×0.25)]

類似可得到關于機器2、機器3的輪盤賭概率區(qū)間[0.567，0.838]、[0.838，1.000]，可以得到輪盤賭矩陣(0.567,1)，(0.838,2),(1,3).如若生成隨機數(shù)0.80，根據(jù)矩陣，隨機數(shù)在0.567和0.838之間，根據(jù)輪盤賭矩陣，此時使用機器2加工該工序.

2.4 差分進化

為得到較優(yōu)解，通過差分進化算法對初始化的種群進行更新，差分進化包括變異、交叉及選擇， 算法流程如下.

步驟1算法初始化，生成最大迭代次數(shù)maxgen、變異因子F和交叉因子Cr.

步驟2開始循環(huán)，令i=1.

步驟3隨機選擇3個個體X1、X2、X3，并生成隨機數(shù)rand，對X1、X2進行差分操作：首先生成隨機數(shù)，如果隨機數(shù)小于變異因子，則進行變異操作，子代向量為變異操作后的向量個體，否則子代向量為父代個體X1.

(16)

式中G(X1,X2)表示父代個體彼此之間進行交叉，由于涉及工序和機器2個子問題，該差分操作較為復雜，具體如下.

1) 關于編碼中的工序部分交叉采用優(yōu)先交叉(POX)，如圖2所示：P1和P2為父代的2個個體，C1和C2為子代2個個體，P1和P2將若干工件置入一個集合中，之后C1和C2繼承集合中的工件在父代的位置和值，并且將父代P1的剩余部分按照原順序置入C2，將父代P2的剩余部分按照原順序置入C1.

圖2 POX交叉過程Fig.2 Pox crossover process

2) 關于編碼中的機器部分交叉如果采用POX由于部分機器無法加工某道工序(見表1)可能導致出現(xiàn)不可行解，傳統(tǒng)差分進化算法雖然在這方面設計了一種交叉方式，但是這種交叉方式得到的子代機器部分的信息繼承有著一定的缺陷.因此本文在傳統(tǒng)差分進化算法中的機器交叉的基礎上進行一定的改進，操作流程如下.

以常見的一種傳統(tǒng)交叉進化算法中機器部分交叉方法為例，首先遍歷每個機器位置，例如遍歷到機器位置1，生成隨機數(shù)，如果隨機數(shù)小于等于F，將X1的機器位置1的值賦到子代機器位置1上，否則，將X2的機器位置1的值賦到子代機器位置1上，對子代的每個機器位置操作都類似.考慮到X1和X2的機器部分的編碼都是合理的，因此不會產(chǎn)生不可行解，但是這樣的交叉方式存在一定的問題，子代基因的繼承是從X1和X2輪番按位繼承，優(yōu)秀段的信息可能無法繼承，除非連續(xù)產(chǎn)生的隨機數(shù)都小于交叉因子，否則子代繼承的基因很可能就是X1的小片段，然后是X2的小片段，之后又是X1的小片段，這樣的處理僅能增加新個體的多樣性，子代的質(zhì)量卻無從保證.

因此本節(jié)在傳統(tǒng)差分進化算法機器交叉后得到的子代的基礎上再添加一個處理方案，即對子代的機器位置再進行一次循環(huán)遍歷，設定機器位置的變異因子，為每個機器位置設計一種機器選擇策略，提高了差分得到的向量的質(zhì)量，一定程度上改進了差分進化算法，具體操作流程如下.

① 設定機器變異因子Mr，循環(huán)遍歷子代個體的機器編碼.

② 遍歷機器位置h時，h≥2，生成隨機數(shù)，如果隨機數(shù)小于Mr，對該位置進行變異，變異時統(tǒng)計之前各位置機器k出現(xiàn)的數(shù)量Mk，該位置變異取決于之前位置各機器的累計數(shù)量.例如遍歷到某位置，此時生成隨機數(shù)小于變異因子Mr，則變異時選擇該位置為某機器k的概率為

(17)

步驟4將變異個體和父代個體X3，進行交叉

(18)

差分操作同步驟3，差分操作后得到試驗個體U.

步驟5將試驗個體U與當前種群中某個體進行比較，如果該試驗個體的適應度較好則將該個體暫存至臨時種群中，待此次迭代完成后，采用輪盤賭方法從最終種群挑取和最初種群個體數(shù)量一致的個體進入下一輪迭代[4].

步驟6i++，判斷i是否滿足最大迭代次數(shù)要求，否跳到步驟3，是則退出程序，最優(yōu)個體從此時的種群選出.

2.5 小結(jié)

本節(jié)提出了一種結(jié)合模型多目標特點的初始化方法，包括工序初始化方法和機器初始化方法，其中機器初始化方面結(jié)合模型多目標特點，設定多權(quán)值綜合考慮多目標進行機器初始化.并且提出一種機器選擇策略用于改進差分進化算法，即在滿足設定的機器變異條件時，如何對傳統(tǒng)差分進化算法得到的子代個體的機器部分進行一次優(yōu)化.下面就改進差分進化算法與傳統(tǒng)差分進化算法進行算例驗證.

3 算例驗證分析

為驗證算法的實用性，對某加工廠的5類工件進行批量調(diào)度，5類工件的數(shù)量分別為33、45、36、60、26，根據(jù)式(15)，求得等分批的最好方案為類1工件等分3批, 類2工件等分3批, 類3工件等分3批, 類4工件等分4批, 類5工件等分2批，將每個子批視為一個工件進行調(diào)度，因此共有3+3+3+4+2=15個工件，每工件4道工序，共60道工序.每類工件的單件加工信息見表1，表中52-10.13表示加工時長和能耗，其中52表示加工時長為 52 min，能耗為10.13 kW·h.考慮序列的準備時間表如表2所示.

表2 考慮上一道工序的準備時間

為驗證算法的性能，在CPU型號為Intel(R) Core(TM) i5-9300H CPU @ 2.40 GHz、計算機內(nèi)存為8 GB的筆記本電腦上以3.7.0版本的Python語言進行算法測試.在參數(shù)選擇上，考慮到變異因子F過大會導致算法的收斂速度變慢，而過小會導致種群的多樣性降低，出現(xiàn)早熟，因此選擇變異因子F=0.5.交叉因子Cr越大交叉概率就越大，一般選擇Cr=0.1.機器變異因子不宜太大，否則減緩收斂速度，本文中Mr=0.05.對比迭代次數(shù)為500、700和1 000次時，種群最優(yōu)個體的適應度函數(shù)值收斂情況，如圖3所示，分別代表迭代次數(shù)為500、700和1 000次時，最優(yōu)個體的適應度函數(shù)值的收斂情況.通過觀察可以發(fā)現(xiàn)迭代次數(shù)為500時，3張圖收斂效果較好，超過500次后，700次迭代圖和1 000次迭代圖的繼續(xù)收斂的程度不明顯，因此取迭代次數(shù)為500進行算法對比.

圖3 500、700、1 000次迭代最優(yōu)個體適應度值變化曲線Fig.3 Variation curve of optimal individual fitness value for 500, 700 and 1 000 iterations

綜上所述，本文以最大迭代次數(shù)500次，變異因子F=0.5，交叉因子Cr=0.1，機器變異因子Mr=0.05，種群個體數(shù)量為50作為算法參數(shù).將改進差分進化算法對算例的調(diào)度結(jié)果和傳統(tǒng)差分進化算法對算例的調(diào)度結(jié)果進行對比.表3為5組實驗下，傳統(tǒng)差分進化算法調(diào)度求解的各目標的調(diào)度結(jié)果，表4為5組實驗下，改進差分進化算法調(diào)度求解的各目標的調(diào)度結(jié)果.從整體效果上來看，改進差分進化算法求解耗時平均為81.01 s，超過傳統(tǒng)差分進化算法6 s，6 s的運行時間增加主要來自于初始化策略和機器選擇策略的引入.但是優(yōu)化后差分進化算法調(diào)度求解所得的最優(yōu)個體最大完工時間、能耗、刀具磨損件數(shù)較傳統(tǒng)算法分別優(yōu)化了11.64%、14.93%和3件，極大地優(yōu)化了最大完工時長、能耗和刀具磨損這3個目標.

表3 傳統(tǒng)差分進化算法調(diào)度結(jié)果

表4 改進差分進化算法調(diào)度結(jié)果

圖4(a)為傳統(tǒng)差分進化算法500次迭代過程最優(yōu)個體最大完工時間，圖4(b)為改進差分進化算法500次迭代過程最優(yōu)個體最大完工時間.通過對比傳統(tǒng)差分進化算法和改進的差分進化算法的500次迭代種群中最優(yōu)個體的情況，可發(fā)現(xiàn)在初始迭代時，改進的差分進化算法所得種群中最優(yōu)個體的適應度值較低.5組實驗中，改進差分進化算法初始化時所得最優(yōu)個體的最大完工時間5組實驗均值較傳統(tǒng)差分進化算法初始化時所得最優(yōu)個體的最大完工時間5組實驗均值低100 min左右，且達到500次迭代次數(shù)時，改進差分進化算法所得最優(yōu)個體最大完工時間的收斂也低于傳統(tǒng)差分進化算法所得最優(yōu)個體300 min.這表明初始化策略在算法收斂上有較為明顯的作用.

圖4 500次迭代過程中最優(yōu)個體最大完工時間Fig.4 Maximum completion time of the optimal individual in 500 iterations

圖5是在采取機器選擇策略后，改進差分進化算法能耗和機器加工時間，其中圖5(a)為傳統(tǒng)差分進化算法500次迭代過程最優(yōu)個體能耗圖，圖5(b)為改進差分進化算法500次迭代過程最優(yōu)個體能耗圖.可以發(fā)現(xiàn)，未采用機器選擇策略的傳統(tǒng)差分進化算法其最優(yōu)個體能耗圖各組之間上下限區(qū)間較大，震蕩性較為明顯，而改進差分進化算法收斂較為平滑，各組之間上下限區(qū)間較小，達到500次迭代時能耗小于傳統(tǒng)差分進化算法，優(yōu)化值為500 kW·h，一定程度上表明初始化策略在本調(diào)度模型的有效性.

圖5 500次迭代過程中最優(yōu)個體能耗Fig.5 Optimal individual energy consumption in 500 iterations

圖6(a)為傳統(tǒng)差分進化算法所得最優(yōu)個體設備累計加工時間，從左到右，設備累計加工時間(單位:min)為3 107、4 102、3 212、4 034、3 783、3 751.圖6(b)為改進差分進化算法所得最優(yōu)個體設備累計加工時間，從左到右，設備累計加工時間(單位：min)為3 223、3 362、3 342、2 994、3 201、3 402.同樣可以發(fā)現(xiàn)傳統(tǒng)差分進化算法進行機器部分編碼的交叉時只是單純地增加機器編碼的全局性而未考慮機器編碼部分的質(zhì)量，極易出現(xiàn)負載不均的現(xiàn)象，而考慮機器選擇策略的改進差分進化算法的設備工作時間較為均衡.

圖6 最優(yōu)個體設備累計加工時間Fig.6 Cumulative processing time of optimal individual equipment

最終獲得一個可用的調(diào)度結(jié)果染色體：[工序部分：1 5 2 3 13 1 7 14 5 6 11 4 12 15 9 5 7 2 4 14 5 1 15 12 8 3 13 1 10 11 12 4 12 3 9 11 10 8 10 3 9 11 8 14 13 6 14 15 4 6 7 10 9 8 2 2 7 15 6 13；機器部分：6 4 2 4 5 2 1 4 5 4 1 5 2 3 4 4 2 1 1 6 5 2 4 2 4 4 4 3 2 5 1 3 4 6 3 3 2 5 1 3 6 3 6 5 1 3 6 3 5 2 4 6 3 1 3 6 2 5 3 1].

其調(diào)度甘特圖如圖7所示，其最大完工時間為3 511 min，能耗為8 640 kW·h，預估損壞刀數(shù)30把.

圖7 最優(yōu)調(diào)度方案Fig.7 Optimal scheduling scheme

4 結(jié)論

本文針對機加工柔性作業(yè)車間工件品種和批量較多、車間環(huán)境較為復雜導致的調(diào)度成本過高、機器設備負載不均衡的問題進行研究，取得了以下結(jié)論.

1) 以最大完工時間、能耗和刀具損耗數(shù)量為優(yōu)化目標，以返工、批量調(diào)度和考慮序列的準備時間作為約束建立了多目標機加工柔性作業(yè)車間調(diào)度模型，該模型能有效反映實際多目標機加工柔性作業(yè)車間生產(chǎn)特點.

2) 設計一種改進差分進化算法，通過實際算例測試，分別分析改進差分進化算法和傳統(tǒng)差分進化算法對多目標機加工柔性作業(yè)車間調(diào)度模型求解結(jié)果，發(fā)現(xiàn)基于改進差分進化算法的多目標機加工柔性作業(yè)車間調(diào)度結(jié)果較優(yōu)，有一定的實用價值.