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

(1.武漢科技大學(xué) 冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081；2.武漢科技大學(xué) 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081；3.三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院，湖北 宜昌 443002)

1 問(wèn)題的描述

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

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

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

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

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

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

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

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

為便于對(duì)求解問(wèn)題進(jìn)行準(zhǔn)確描述，引入下述符號(hào)和變量：

(1)輸入條件

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

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

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

Pj為工件j的加工時(shí)間；

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

dj為工件j的交貨時(shí)間；

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

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

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

t為機(jī)器上的加工序列。

(2)輸出條件

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

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

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

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

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子批在機(jī)器i的t序列加工為1，否則為0。

(3)目標(biāo)

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

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

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

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

F=min(Cmax,Z)。

(1)

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

(2)

(3)

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

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)等量分批策略 每個(gè)子批的批量相同?？紤]到可能出現(xiàn)工件總數(shù)無(wú)法均分為指定批次數(shù)的情況，在等量均分基本原則上進(jìn)行一定調(diào)整，具體操作為：前Bj-1個(gè)子批的數(shù)量為該工件總數(shù)除以實(shí)際批數(shù)后取整，最后一個(gè)子批批量等于該工件總數(shù)減去前Bj-1個(gè)子批的工件數(shù)。

1≤Bj≤Lj,?j∈N;

(6)

(7)

(8)

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

(9)

(10)

(11)

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

(12)

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

(13)

(5)計(jì)算完工時(shí)間 計(jì)算每個(gè)子批的完工時(shí)間，且在同一臺(tái)機(jī)器上預(yù)留出前后兩個(gè)子批之間的生產(chǎn)切換時(shí)間。

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)

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

3 改進(jìn)多目標(biāo)鯨魚(yú)群算法

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

(17)

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

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

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

3.2 “較優(yōu)且最近”鯨魚(yú)引導(dǎo)個(gè)體尋找

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

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

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

輸入:鯨魚(yú)群Ω,鯨魚(yú)Ωu;

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

1:開(kāi)始

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

3:定義一個(gè)初始化為無(wú)窮大的浮點(diǎn)變量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 引入多點(diǎn)保留交叉的鯨魚(yú)個(gè)體移動(dòng)規(guī)則

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

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

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

算法2新個(gè)體選擇策略偽代碼。

輸入:父代個(gè)體X、子代新個(gè)體X′;

輸出:新個(gè)體子代種群OffSpringPop。

1:開(kāi)始

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表示在算法迭代過(guò)程中產(chǎn)生的新個(gè)體子代種群，X′X表示新的個(gè)體X′支配X。

3.5 Pareto外部存檔

Pareto將無(wú)法直接比較的多個(gè)目標(biāo)函數(shù)的優(yōu)化問(wèn)題進(jìn)行歸納，數(shù)學(xué)公式如下所示：

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為決策空間Ω中的一個(gè)n維決策向量，F(xiàn)是m個(gè)目標(biāo)函數(shù)(f1(x),f2(x),…,fm(x))T組成的一個(gè)m維的目標(biāo)向量，gi(x)≤0定義了p個(gè)不等式約束，ej(x)=0定義了q個(gè)等式約束。

算法3MOWSA。

輸入:目標(biāo)函數(shù)，鯨魚(yú)群Ω;

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

1:開(kāi)始

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

3:鯨魚(yú)種群初始化并評(píng)價(jià)；

4:初始化Pareto外部存檔；

5:while 終止條件不滿足do

6:fori=1to|Ω|do

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

8:if Y存在then

9:生成鯨魚(yú)Ωi的副本X′；

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

11:評(píng)價(jià)新副本X′；

12:else 生成鯨魚(yú)Ωi的副本X″；

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

14:評(píng)價(jià)新副本X″；

15:end if

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

17:ifΩi.count≥Ts

18:重新初始化Ωi,并進(jìn)行評(píng)價(jià);

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ù)實(shí)驗(yàn)

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

4.1 性能評(píng)價(jià)指標(biāo)

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

4.2 實(shí)驗(yàn)結(jié)果分析

三個(gè)算法各獨(dú)立運(yùn)行10次，同時(shí)選取各評(píng)價(jià)指標(biāo)的最小值(min)，最大值(max)，平均值(agv)，標(biāo)準(zhǔn)差(sd)進(jìn)行分析。比較結(jié)果如表1～表4及圖5所示，表中加粗?jǐn)?shù)據(jù)表示案例中性能較好的指標(biāo)值。

表1 世代距離(GD)

表2 反世代距離(IGD)

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

表4 超體積指標(biāo)(HV)

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

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

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

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

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

5 案例分析

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

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

表6 各型號(hào)工件間換刀時(shí)間

(21)

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

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

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

表7 前沿解集

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

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

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