基于多目標(biāo)差分進(jìn)化算法的機(jī)加工柔性作業(yè)車間調(diào)度

程 強(qiáng)， 高元杰， 初紅艷， 張彩霞， 劉志峰

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

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

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

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

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

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

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

2) 確定各子批在哪臺(tái)機(jī)器設(shè)備上加工.

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

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

1.1 變量定義

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

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

M：機(jī)器總數(shù).

H：工序總數(shù).

Ω：總的機(jī)器集.

i：工件類別號(hào)，i=1,2,…,N.

k：機(jī)器序號(hào)，k=1,2,…,M.

j：工序序號(hào)，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工序起始加工時(shí)間.

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

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

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

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

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

tk,C：機(jī)器k上最后一個(gè)子批工序的完工時(shí)間,k=1,2,…,M.

tCmax：最大完工時(shí)間.

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

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

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

(1)

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

(2)

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

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ā)生，將返工這一動(dòng)態(tài)問題轉(zhuǎn)換為靜態(tài)問題進(jìn)行處理，在已知ti,j,k,P的基礎(chǔ)上為返工預(yù)留加工時(shí)間

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

(4)

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

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

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

因?yàn)楣ぜ跈C(jī)器的準(zhǔn)備時(shí)間取決于上一工件，因此考慮帶有工件次序的準(zhǔn)備時(shí)間，tMatrix為考慮序列準(zhǔn)備時(shí)間矩陣，其中行與列表示工件和工件之間如果在機(jī)器上相鄰時(shí)，切換工作環(huán)境的準(zhǔn)備時(shí)間.

(6)

最大完工時(shí)間取決于機(jī)器最后一個(gè)子批完工時(shí)間的最大值, 即

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

(7)

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

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

(8)

式中:Pk,f、Pk,air和Pk,v分別表示機(jī)床k待機(jī)功率、空載功率以及切削功率; 而tf、tair和tv為其對(duì)應(yīng)的時(shí)間.

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

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

Pk,air=An2+Bn+C

(9)

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

因此，可以得到

(10)

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

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

(11)

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

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

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

(12)

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

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

其余假設(shè)條件如下.

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

2) 同種工件每個(gè)子批的每道工序可以選擇不同設(shè)備進(jìn)行加工.

3) 每臺(tái)設(shè)備在同一時(shí)刻只能加工某類工件某批次的一道工序.

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

2 差分進(jìn)化算法設(shè)計(jì)

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

2.1 編碼方式與解碼方式

本文采取以工序?yàn)榛鶞?zhǔn)的編碼方式，以10個(gè)工件5道工序6個(gè)機(jī)器為例，總工序?yàn)?0×5=50道工序.為50道工序分配機(jī)器，因此染色體中還需要為50個(gè)工序預(yù)留50個(gè)機(jī)器位置，染色體總長(zhǎng)度為100，為方便解碼，設(shè)定染色體前一半部分代表的是工序，后一半部分代表的是加工該工序?qū)?yīng)的機(jī)器，其中染色體機(jī)器位置部分第1～5個(gè)位置表示工件1的第1道工序到第5道工序所選擇的機(jī)器，第6～10個(gè)位置表示工件2的第1道工序到第5道工序所選擇的機(jī)器，以此類推，如圖1所示.

圖1 編碼圖Fig.1 Coding diagram

工件的個(gè)數(shù)計(jì)算方式為

(13)

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

(14)

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

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

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

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

3) 若n

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

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

6) 若x

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

表1 5種類-4工序-6機(jī)器加工信息

2.2 多目標(biāo)適應(yīng)度函數(shù)設(shè)計(jì)

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

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

(15)

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

2.3 初始化種群

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

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

1) 工序初始化

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

2) 機(jī)器初始化

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

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

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

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

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

2.4 差分進(jìn)化

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

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

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

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

(16)

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

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

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

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

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

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

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

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

(17)

步驟4將變異個(gè)體和父代個(gè)體X3，進(jìn)行交叉

(18)

差分操作同步驟3，差分操作后得到試驗(yàn)個(gè)體U.

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

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

2.5 小結(jié)

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

3 算例驗(yàn)證分析

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

表2 考慮上一道工序的準(zhǔn)備時(shí)間

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

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

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

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

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

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

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

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

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

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

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

最終獲得一個(gè)可用的調(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；機(jī)器部分：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所示，其最大完工時(shí)間為3 511 min，能耗為8 640 kW·h，預(yù)估損壞刀數(shù)30把.

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

4 結(jié)論

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

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

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