朱穎穎，吳正佳,唐秋華+，孟榮華

(1.武漢科技大學 冶金裝備及其控制教育部重點實驗室，湖北 武漢 430081；2.武漢科技大學 機械傳動與制造工程湖北省重點實驗室，湖北 武漢 430081；3.三峽大學 機械與動力學院，湖北 宜昌 443002)

1 問題的描述

多品種、小批量、交期短是現(xiàn)行客戶訂單的普遍特征，與此相反的是在其生產(chǎn)過程中，存在制造周期長、設(shè)備通用化等弊端，會降低車間生產(chǎn)效率、加大交貨延遲風險。為此，企業(yè)常用措施是將一個訂單或一批工件拆分為多個批次，多臺機器并行加工，達到加快生產(chǎn)進度、縮短制造周期的目標。此類問題常稱為并行機分批調(diào)度問題，由于各批次在不同機器上加工時可能存在時間重疊，部分文獻也稱其為并行機批量流調(diào)度問題[1]。

并行機分批調(diào)度是NP-難問題，與傳統(tǒng)的并行機調(diào)度相比，其不同點是需要將一批具有一定數(shù)量的工件分為若干子批；相同點是需要將各子批分配到并行機上，再進行加工。與分批相反的批量調(diào)整策略是組批[2](Batching)，它需要將不同工件整合成一個批次，故還需決策每個子批內(nèi)不同工件的加工順序。并行機分批策略通常包括等量分批和可變分批[3]兩種，其中等量分批要求每個子批的批量相等，而可變分批與其相反。本文研究的是并行機等量分批調(diào)度問題(Parallel Machine Equally Lot-sizing and Scheduling Problem，PM-ELSP)，不僅要制定分批策略，還需考慮子批在各臺并行機上的排序和定時問題[4]。

諸多學者研究啟發(fā)式或元啟發(fā)式算法，來求解并行機分批調(diào)度問題。WANG等[5]針對太陽能電池制造，提出混合粒子群算法，解決具有多階段的并行機分批調(diào)度問題，指出各子批的機器分配、批量確定和生產(chǎn)排序三者之間是彼此關(guān)聯(lián)、互為條件的，需要聯(lián)合優(yōu)化。GüNG?R等[6]考慮到機器要么空閑、要么滿負荷工作，沒有中間狀態(tài)，故以最小化工裝夾具等裝備安裝和卸載次數(shù)為目標，設(shè)計啟發(fā)式算法，求解并行機分批調(diào)度問題。EREMEEV等[7]以最大完工時間最小為目標，研究具有不相關(guān)并行機、工件可絕對均衡分批的并行機分批調(diào)度問題，且通過數(shù)學證明了該問題的NP-難特性。DE ARMAS等[8]提出一種數(shù)學規(guī)劃和后處理排序啟發(fā)式相結(jié)合的方法，解決以最大化總產(chǎn)量為目標的并行機分批調(diào)度問題。DANESHAMOOZ等[9]提出結(jié)合自適應的變鄰域搜索算法，解決以最大完工時間最小的并行組裝站分批調(diào)度問題。WANG等[10]提出融入交叉和變異算子的差分進化算法，求解以最大完工時間最小為目標的單目標并行機分批調(diào)度問題。WANG等[11]設(shè)計了一種基于規(guī)則的貪婪啟發(fā)式算法，求解以最大完工時間最小為目標的單目標并行機分批調(diào)度問題。

綜上可見，分批調(diào)度能縮短制造周期、減少生產(chǎn)提前期(如圖1)，故而被廣泛應用。但是，當前并行機分批調(diào)度研究主要針對單目標優(yōu)化問題，很少使用多目標優(yōu)化，且目標主要是最大完工時間的最小化。針對分批過程中產(chǎn)生的若干子批，如何保證各子批工件能同時、準時進行交付，尚無文獻進行研究。此外，上述研究中每批工件可劃分的子批數(shù)目是定值，而實際工作中不同工件、不同批量，所劃分的子批數(shù)量亦不相同。并且，在實際生產(chǎn)中，刀具成本高昂，可用刀具數(shù)目受限，對于工件劃分的批次數(shù)目存在約束，上述研究均無考慮。

因此，本文以完工時間和交付時間偏差最大值的最小化為優(yōu)化指標，在考慮刀具數(shù)量、切換時間等約束條件下，求解批次受限的多目標并行機分批調(diào)度問題。設(shè)計改進的多目標鯨魚群算法(Multi-objective Whale Swarm Algorithm, MOWSA)實現(xiàn)工件分批、機器分配與子批排序3個子問題的聯(lián)合求解。

2 批次受限的雙目標并行機等量分批調(diào)度模型

隨著柔性化能力的提升，在數(shù)控加工中心等加工設(shè)備上只需更換刀具，便可對不同工件進行加工。同時，由于刀具造價高、不易配套齊全，使得刀具數(shù)量有限，其數(shù)量小于加工設(shè)備的數(shù)量。因此，在生產(chǎn)調(diào)度時需要考慮刀具約束，保證每個工件能被合適的刀具加工。同時，考慮到一批工件需要同時、準時進行交付，工件分批數(shù)量應小于并行機數(shù)量；又因為刀具約束，工件批次數(shù)量更應小于刀具數(shù)量。由此，考慮刀具約束的并行機分批調(diào)度問題本質(zhì)上就變成了批次受限的并行機分批調(diào)度問題。該問題可以描述為：假定某車間有M臺并行機，需對N種工件進行加工，每種工件的批量已知，每批工件所能采用的刀具數(shù)亦已知，且刀具數(shù)小于并行機臺數(shù)。

針對該問題，提出以下假設(shè)：①在一定生產(chǎn)周期內(nèi)所需加工工件的批次數(shù)和批量已知；②每批工件的刀具類型和刀具數(shù)量確定；③同類工件在各設(shè)備上的加工時間已知；④各工件優(yōu)先級相同，不存在搶先生產(chǎn)；⑤每批工件種類相同，各子批一旦開始加工就不可中斷，且不能被再次分割；⑥同一時刻每臺設(shè)備只能加工一個子批；⑦同一設(shè)備換刀加工不同工件時，工件的加工順序不同，換刀時間也不同；⑧所有設(shè)備上的第一個子批不需要調(diào)整，所要加工的工件均已準備好。

為便于對求解問題進行準確描述，引入下述符號和變量：

(1)輸入條件

N為批量數(shù)N={j|1,2,3,…,N}；

M為機器數(shù)M={i|1,2,3,…,N}；

Lj為工件j的最大分批數(shù)；

Pj為工件j的加工時間；

Qj,k為工件j到k間的換刀設(shè)置時間；

dj為工件j的交貨時間；

wr為拖期完工的權(quán)重系數(shù)；

we為提前完工的權(quán)重系數(shù)；

V為一個極大的正數(shù)；

t為機器上的加工序列。

(2)輸出條件

Nj為工件批量數(shù)；

Bj為整數(shù)變量，工件j的實際分批數(shù)；

Oi,t為連續(xù)變量，機器i上序列t的開始時間；

Ci,t為連續(xù)變量，機器i上序列t的結(jié)束時間；

ETj為連續(xù)變量，工件j的r子批提前期；

DTj為連續(xù)變量，工件j的r子批拖期；

Fj,r為整數(shù)變量，工件j的r子批的批量數(shù)；

Wj,r為0-1變量，若工件j分了r批則Wj,r為1，否則為0；

Xi,t,j,r：0-1變量，如果工件j的r子批在機器i的t序列加工為1，否則為0。

(3)目標

Cmax為連續(xù)變量，最大完工時間；

Z為連續(xù)變量，交付時間偏差最大值。

基于上述定義，構(gòu)建如下批次受限的雙目標并行機分批調(diào)度模型：

(1)目標函數(shù) 最大完工時間是車間調(diào)度問題的常用目標，能表達車間的整體生產(chǎn)效率。此外，一批工件常常是源自一個訂單、一個客戶，若部分工件先交付，另一部分再交付，不利于所加工產(chǎn)品的運輸和交付，也給客戶增加了麻煩。因此，將每批工件各子批交付時間與計劃交貨期進行對照，得到提前與拖期權(quán)重和，即交付時間偏差。最大交付時間偏差的最小化，能保證一批工件同時、準時進行交付。同時，進行完工時間和交付時間偏差最大值的最小化，可實現(xiàn)雙目標優(yōu)化。

F=min(Cmax,Z)。

(1)

Cmax≥Ci,t,?i∈M,t∈[1,2,…,N]；

(2)

(3)

(2)提前與拖期值計算 在精益生產(chǎn)中，提前或是拖期生產(chǎn)都被定義為對資源的浪費。限制提前期，可以避免因過度提前完工而增加的庫存或產(chǎn)品變質(zhì)等風險；限制拖期，可以減少延期交付而帶來的經(jīng)濟或名譽損失。

ETj≥dj-Ci,t-V×(1-Xi,t,j,r),

?i∈M,j∈N,r=Bj,t∈[1,2,…,N];

(4)

DTj≥Ci,t-dj-V×(1-Xi,t,j,r),

?i∈M,j∈N,r=Bj,t∈[1,2,…,N]。

(5)

(3)等量分批策略 每個子批的批量相同。考慮到可能出現(xiàn)工件總數(shù)無法均分為指定批次數(shù)的情況，在等量均分基本原則上進行一定調(diào)整，具體操作為：前Bj-1個子批的數(shù)量為該工件總數(shù)除以實際批數(shù)后取整，最后一個子批批量等于該工件總數(shù)減去前Bj-1個子批的工件數(shù)。

1≤Bj≤Lj,?j∈N;

(6)

(7)

(8)

(4)機器分配策略 對于每一批工件來說，需要前一個子批劃分后，后一個子批才可劃分。已經(jīng)劃分的每一個子批需且必須分配到一臺機器的某個事件點上進行加工。每臺機器的每個事件點上最多可以加工一個子批。而對每臺機器的兩個連續(xù)事件點，一定是已經(jīng)給前一事件點安排加工任務(wù)后，后一個事件點才可啟用。若同一批次的兩個子批分到同一臺機器上，不允許連續(xù)加工，若連續(xù)加工即可視為一個子批。

(9)

(10)

(11)

?i∈M,t∈[1,2,…,N)；

(12)

?i∈M,j∈N,t∈[1,2,…,N)。

(13)

(5)計算完工時間 計算每個子批的完工時間，且在同一臺機器上預留出前后兩個子批之間的生產(chǎn)切換時間。

Ci,t-Oi,t≥Pj×Fj,r-V×(1-Xi,t,j,r),

?i∈M,j∈N,r∈Lj,t∈[1,2,…,N];

(14)

Ci,t-Oi,t≤Pj×Fj,r+V×(1-Xi,t,j,r),

?i∈M,j∈N,r∈Lj,t∈[1,2,…,N];

(15)

Oi,t+1-Ci,t-Qj,k≥

?i,k∈M,j∈N,r,s∈Lj,t∈[1,2,…,N]。

(16)

上述問題是NP-難問題[11]，若使用精確求解算法，很難在可接受的時間內(nèi)找到最優(yōu)解。求解本問題的難度在于如何確定每批工件的最優(yōu)分批數(shù)量，如何改進算法滿足刀具等各種約束，以及在問題規(guī)模較大的情況下如何高效求解本問題。

3 改進多目標鯨魚群算法

針對批次受限的并行機分批調(diào)度問題，采用由高亮等[12]提出的鯨魚群算法(WSA)進行求解，該方法因全局尋優(yōu)能力較強而被廣為應用。在WSA中每個個體會積極地向距離該個體“較優(yōu)且最近”的鯨魚移動。移動公式為：

(17)

批次受限的并行機分批調(diào)度問題是一種離散組合優(yōu)化問題。然而，WSA主要用于求解連續(xù)性函數(shù)問題，不能直接求解離散型問題。為求解批次受限的多目標并行機分批調(diào)度問題，需要根據(jù)問題特征，對WSA進行相應的改進，主要有：①設(shè)計批次受限的子批生成策略及排序的雙層編碼方式；②設(shè)計采用漢明距離表示個體間的距離；③融入多點保留交叉策略，設(shè)計個體移動規(guī)則；④提出隨機鄰域搜索與非劣個體選擇策略。下文將詳細闡述這些改進點。

3.1 批次受限的子批編碼、解碼及排序策略

工件實際分批數(shù)不定會導致：①使用傳統(tǒng)編碼方式時，個體編碼長度無法確定；②固定工件子批的位置使用機器號編碼時，機器上子批排序難以表達。針對以上問題，引入虛擬占位符[14]，設(shè)計允許批次數(shù)可變的定長編碼、采取雙層分段的編碼方式來表示問題的解。首先編碼的長度由所有工件的最大分批總數(shù)之和決定，編碼中第一層為機器編碼，如圖2所示工件號下包含的3個位置編碼表示該工件最大可分為3批，數(shù)字表示第幾臺并行機器，當機器編碼為虛擬占位符0時，表示工件未達到最大分批，此時子批的數(shù)量為總批量除以實際分批數(shù)；當工件完全分批時，子批的數(shù)量為總數(shù)除以最大分批數(shù)。第二層為加工順序編碼，隨機生成工件位置排序的概率，機器上加工順序由隨機概率大小決定，概率小的優(yōu)先在該機器上加工。編碼與解碼方式如圖2所示。

3.2 “較優(yōu)且最近”鯨魚引導個體尋找

尋找“較優(yōu)且最近”的鯨魚個體，用其引導其他個體移動，是本算法最重要的步驟之一。為此，需要針對每個個體，依據(jù)漢明距離找出距離它最近的優(yōu)秀個體。其中，漢明距離計算方法如圖3所示。假定兩個個體向量PWS均包含12個元素，從標記的部分可以看出向量PWS1和PWS2有3個元素不同，因此兩向量之間漢明距離就是3。而較優(yōu)個體的判定標準是Pareto支配關(guān)系。當且僅當其他個體處于前一Pareto層級，才判定其比當前個體更為優(yōu)秀。

隨機在種群中選一個個體作為父代，并在種群尋找另一個與父代個體“較優(yōu)且最近”的引導個體，以漢明距離找出“最近”，以非支配排序等級作為“較優(yōu)”。尋找“較優(yōu)且最近”引導鯨魚個體的偽代碼如下所示：

算法1尋找“較優(yōu)且最近”的鯨魚。

輸入:鯨魚群Ω,鯨魚Ωu;

輸出:鯨魚Ωu的“較優(yōu)且最近”的鯨魚。

1:開始

2:定義初始化為0的整數(shù)變量v；

3:定義一個初始化為無窮大的浮點變量temp；

4:while 終止條件不滿足do

5:fori=1to|Ω|do

6:iff(Ωi)

7:v=i;

8:temp=dist(Ωi,Ωu);

9:end if

10:end for

11: end while

12:返回Ωv；

13:結(jié)束

3.3 引入多點保留交叉的鯨魚個體移動規(guī)則

在PM-ELSP中，不僅要劃分批量為若干子批，給子批分配機器，還需要對分配到機器上的各子批進行合理的排序。本文算法引入多點保留交叉[15](Multipoint Preservative Crossover，MPX)策略來設(shè)計個體移動規(guī)則，尋找子批的最優(yōu)排產(chǎn)策略。如圖4所示，舊個體以及引導個體“較優(yōu)且最近”的機器編碼。引導移動從而產(chǎn)生的新個體機器編碼如圖4最下方分段編碼所示。移動規(guī)則具體為如下步驟：①隨機生成一組0和1組成的隨機數(shù)，長度為各工件最大分批數(shù)的總和；②原個體中子批元素對應隨機數(shù)為1的不變(圖4中原個體虛線框部分)，對應隨機數(shù)為0的存儲到新建集合O中；③將引導個體中所有屬于集合O的子批元素依次填入到原個體，得到新的個體。第二層加工順序編碼跟隨機器編碼而變。

3.4 鄰域搜索及非劣解保留策略

無論是在父代個體向引導個體移動階段還是鄰域搜索階段，都會產(chǎn)生一個子代新個體。然而，并不是所有新個體都需要保留在子代種群，因此提出非劣個體保留策略，即當子代個體不劣于父代個體時，就保留在子代種群中，偽代碼如下：

算法2新個體選擇策略偽代碼。

輸入:父代個體X、子代新個體X′;

輸出:新個體子代種群OffSpringPop。

1:開始

2: ifX′Xthen

3:X′加入到OffSpringPop

4: else ifXX′then

5:Xcount++

6: else then

7:X′加入到OffSpring

8:Xcount++

9: end if

10:返回OffSpringPop

11:結(jié)束

其中：OffSpringPop表示在算法迭代過程中產(chǎn)生的新個體子代種群，X′X表示新的個體X′支配X。

3.5 Pareto外部存檔

Pareto將無法直接比較的多個目標函數(shù)的優(yōu)化問題進行歸納，數(shù)學公式如下所示：

max/minF=f(x)=(f1(x),f2(x),…,fm(x))。

(18)

s.t.

gi(x)≤0,i=1,2,…,p;

(19)

ej(x)=0,j=1,2,…,q。

(20)

式中：x=(x1,x2,…,xn)T為決策空間Ω中的一個n維決策向量，F(xiàn)是m個目標函數(shù)(f1(x),f2(x),…,fm(x))T組成的一個m維的目標向量，gi(x)≤0定義了p個不等式約束，ej(x)=0定義了q個等式約束。

算法3MOWSA。

輸入:目標函數(shù)，鯨魚群Ω;

輸出:全局最優(yōu)解。

1:開始

2:初始化參數(shù)；

3:鯨魚種群初始化并評價；

4:初始化Pareto外部存檔；

5:while 終止條件不滿足do

6:fori=1to|Ω|do

7:尋找Ωi的“較優(yōu)且最近”的鯨魚Y；//算法1

8:if Y存在then

9:生成鯨魚Ωi的副本X′；

10:副本X′根據(jù)個體移動規(guī)則向Y移動；

11:評價新副本X′；

12:else 生成鯨魚Ωi的副本X″；

13:按照領(lǐng)域搜索策略對副本X″進行領(lǐng)域搜索；

14:評價新副本X″；

15:end if

16:SelectIndividual(OffSpringPop,Ωi,X′);//算法2

17:ifΩi.count≥Ts

18:重新初始化Ωi,并進行評價;

19:end if

20:i=i+1;

21:end for

22:父代、子代種群合并;

23:非占優(yōu)排序并更新種群;

24:更新Pareto外部存檔；

25:end while

26:返回全局最優(yōu)解；

27:結(jié)束

4 數(shù)據(jù)實驗

為驗證MOWSA在求解PM-ELSP問題方面的有效性，從http://www.cima.uadec.mx/instancias/中選用包含大中小規(guī)模的15個實例進行實驗。同時，將其與解決多目標優(yōu)化問題常用的帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ)[16]、多目標人工蜂群算法(Multi-objective Artificial Bee Colony algorithm,MOABC)[17]與改進后的MOWSA算法進行比較。對所有算法參數(shù)進行統(tǒng)一設(shè)置，最大迭代次數(shù)Maxiter=200，種群P=50，Pareto外部存檔的大小設(shè)置為50，每個算例運行10次。

4.1 性能評價指標

為評價多目標優(yōu)化算法，通過查閱相關(guān)文獻，選取以下評價指標。世代距離(GD)，其值越小表示算法性能越好。反世代距離(IGD)，其值越小表明算法的收斂性和多樣性比較好。非支配解的個數(shù)(NDS)，其值越大表明算法的效果越好。超體積指標(HV)，算法獲得的非支配解集與參照點圍成的目標空間中區(qū)域的體積。HV值越大，說明算法的綜合性能越好。

4.2 實驗結(jié)果分析

三個算法各獨立運行10次，同時選取各評價指標的最小值(min)，最大值(max)，平均值(agv)，標準差(sd)進行分析。比較結(jié)果如表1～表4及圖5所示，表中加粗數(shù)據(jù)表示案例中性能較好的指標值。

表1 世代距離(GD)

表2 反世代距離(IGD)

表3 非支配解的個數(shù)(NDS)

表4 超體積指標(HV)

從測試指標IGD的8組數(shù)據(jù)箱線圖如圖5所示，可以看出，大多數(shù)時候MOWSA比NSGA-Ⅱ、MOABC小，意味著MOWSA比其他兩種算法獲得的解有更好的收斂性，MOWSA在15組實例驗證下，表現(xiàn)都優(yōu)于其他兩種算法，可以看出MOWSA不但收斂性好，而且分布均勻。

圖5中IGD的測試結(jié)果箱型圖可見，MOWSA算法所獲得解的上、下四分位數(shù)或中位數(shù)，均小于NSGA-Ⅱ和MOABC算法所得的解，證明增加非劣個體保留策略后，MOWSA算法更好地跳出了局部最優(yōu)。

從表3所示的非支配解個數(shù)來看，MOABC在多數(shù)情況下只能取得1～2個非支配解，而在大中小不同規(guī)模的算例中，MOWSA可以獲得多個非支配解，其數(shù)目遠大于NSGA-Ⅱ和MOABC。分析可見，MOWSA算法中設(shè)計了融入多點保留交叉策略的個體移動規(guī)則，增強了解的多樣性，從而保證了MOWSA能獲取到PM-ELSP的更多前沿解。

由表4測試結(jié)果可見，在多數(shù)情況下MOWSA超體積均大于兩個對比算法，表明其在目標空間中獲得非支配解集與參照點圍成的區(qū)域體積更大，證明其前沿解的分布更均勻。

綜上所述，在求解PM-ELSP問題時，改進的MOWSA算法在收斂性、多樣性上顯著優(yōu)于對比算法，且得到的Pareto前沿解的分布更為均勻。

5 案例分析

某次訂單包含有13種型號的工件，各型號工件的數(shù)量、加工時間、刀具數(shù)量如表5所示，各型號工件間換刀時間如表6所示，該車間有6臺并行機加工設(shè)備，由于實際生產(chǎn)中存在交貨期限定，具體交貨期dj隨機產(chǎn)生，

表5 各型號工件的相關(guān)信息

表6 各型號工件間換刀時間

(21)

其中σ是介于0～1之間的隨機實數(shù)。

將提前/拖期罰系數(shù)分別設(shè)置為WE=0.2,WT=0.8,算法相關(guān)參數(shù)如下：種群P=80,迭代次數(shù)Maxiter=300。

圖6是3種算法所得到的Pareto前沿對比圖，可以看出，3種算法的Pareto前沿一直處于優(yōu)化狀態(tài)，其中黃色三角形為MOWSA最終的Pareto最優(yōu)解集，所包含的調(diào)度方案對應的兩個目標函數(shù)值如表7所示，表中標黑的數(shù)據(jù)分別是圖6中的A、B、C三點調(diào)度方案對應的目標值。圖7給出了圖6中A、B、C三個點的調(diào)度甘特圖。從圖6中可以看出，MOWSA的Pareto前沿要優(yōu)于其余兩種算法，說明MOWSA求解多目標問題是可行且有效的。

表7 前沿解集

圖7分別是圖6中對應3個點的調(diào)度方案甘特圖，圖中的子批表示J8.3或J13.1分別表示第8種工件第3個子批和第13種工件的第1個子批。由圖可以看出，在最大完工時間最小時，其各個設(shè)備的利用率比較均衡，而當提前與拖期的權(quán)重和最小時，由于每個工件更偏向于按交期完工，導致設(shè)備的利用率比較不均衡。

6 結(jié)束語

本文通過分析多品種小批量的并行生產(chǎn)需求和加工中存在的刀具約束，凝練了批次受限的多目標并行機等量分批調(diào)度問題(PM-ELSP)，以完工時間和交付時間偏差最大值的最小化為目標，以期同時達到高效、準時生產(chǎn)的目標?；谠搯栴}特征，構(gòu)建了數(shù)學規(guī)劃模型，提出一種多目標鯨魚群算法(MOWSA)。其中，設(shè)計了允許批次數(shù)可變的定長編碼機制，保證了最大批次數(shù)限制下的子批劃分；融入了多點保留交叉策略，以增強解的多樣性；提出了非劣個體保留策略，以促進算法跳出局部最優(yōu)。結(jié)果表明，所提算法能有效求解PM-ELSP問題，其性能優(yōu)于對比算法NSGA-Ⅱ和MOABC。特別是在大規(guī)模算例中，算法表現(xiàn)出收斂速度快、前沿解個數(shù)多、前沿解分布均勻的優(yōu)勢。研究發(fā)現(xiàn)，相對于并行機調(diào)度，并行機分批調(diào)度更貼近實際，更有利于均衡設(shè)備利用率、縮短生產(chǎn)周期、提高生產(chǎn)效率、實現(xiàn)準時生產(chǎn)。為了更加符合生產(chǎn)實際，未來將在現(xiàn)有研究基礎(chǔ)上，圍繞具有可變批量和刀具指派的并行機分批調(diào)度問題進行研究。