金亮亮 張超勇 GEORGE GERSHOM CHRISTOPHER 文笑雨

(1.紹興文理學(xué)院 機(jī)電學(xué)院，浙江 紹興 312000；2.華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院，湖北 武漢 430074；3.紹興文理學(xué)院 土木工程學(xué)院，浙江 紹興 312000；4.鄭州輕工業(yè)大學(xué) 河南省機(jī)械裝備智能制造重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450002)

0 引言

集成式工藝規(guī)劃與車間調(diào)度(IPPS)問(wèn)題是在柔性作業(yè)車間調(diào)度問(wèn)題[1,2]的基礎(chǔ)上引入序列柔性、加工柔性得到的；通過(guò)整合工藝規(guī)劃及車間調(diào)度消除資源沖突、提高設(shè)備利用率[3-7]，因此，更適合于多周期、小批量、個(gè)性化的生產(chǎn)制造模式.

IPPS問(wèn)題的本質(zhì)在于工藝規(guī)劃和車間調(diào)度模塊的有機(jī)融合.目前，IPPS問(wèn)題中兩大模塊常見(jiàn)的融合方法可分為兩類：(1)順序融合模式：先生成若干備選工藝規(guī)劃，在車間調(diào)度環(huán)節(jié)中根據(jù)優(yōu)化目標(biāo)選取最合理的工藝規(guī)劃[8],但由于此模式常常無(wú)法生成全部可行的工藝規(guī)劃，導(dǎo)致僅能得到局部最優(yōu)解，同時(shí)該模式忽略了工藝規(guī)劃和車間調(diào)度內(nèi)在的聯(lián)系；(2)集成融合模式：將工藝規(guī)劃和車間調(diào)度混為一體進(jìn)行建模及優(yōu)化，避免了順序融合模式中的缺陷，真正實(shí)現(xiàn)了集成優(yōu)化.

IPPS問(wèn)題的優(yōu)化方法大致可分為三類：(1)元啟發(fā)式方法：由于IPPS屬于NP-Hard問(wèn)題，因此這類方法應(yīng)用較為廣泛，從單目標(biāo)到多目標(biāo)，從靜態(tài)到動(dòng)態(tài)，從確定到不確定問(wèn)題等都有涉及.韓國(guó)全南國(guó)立大學(xué)Kim等人使用共生進(jìn)化算法求解了基于網(wǎng)絡(luò)圖的IPPS實(shí)例，Kim等人提出的測(cè)試實(shí)例也成為經(jīng)典的實(shí)例[9].華中科技大學(xué)李新宇和高亮等針對(duì)Kim實(shí)例進(jìn)行了相關(guān)的研究并取得了一系列成果[7-8]；Lian等人基于Kim實(shí)例的特點(diǎn)，提出了基于網(wǎng)絡(luò)圖中OR節(jié)點(diǎn)的編碼方式，使用新穎的殖民競(jìng)爭(zhēng)算法對(duì)Kim實(shí)例進(jìn)行了優(yōu)化[10].巴黎等人研究了基于工件批量柔性劃分的IPPS問(wèn)題，提出了新的編碼方法并使用粒子群算法進(jìn)行了求解[6]；Lv和Qiao提出了新的個(gè)體初始化方法及相應(yīng)的遺傳操作，使用混合遺傳算法優(yōu)化了IPPS實(shí)例并獲得了較好的結(jié)果[11].近年來(lái)Zhang和Wong針對(duì)IPPS實(shí)例提出了對(duì)象編碼方法，在求解Kim實(shí)例時(shí)取得了較好的效果，改進(jìn)了許多已有的結(jié)果[12].文獻(xiàn)[13]提出了一種基于變鄰域搜索的文化基因算法，對(duì)于Kim的實(shí)例進(jìn)行測(cè)試，得到了許多實(shí)例的最優(yōu)解.此外，也有學(xué)者使用元啟發(fā)式算法求解了多目標(biāo)IPPS問(wèn)題.例如Li等人受博弈論中的納什平衡啟發(fā)，用納什平衡處理各個(gè)優(yōu)化目標(biāo)間的關(guān)系，并提出了一種混合算法求解多目標(biāo)IPPS問(wèn)題[14].文獻(xiàn)[15]針對(duì)最大完工時(shí)間、機(jī)床最大負(fù)荷、機(jī)床總負(fù)荷三個(gè)指標(biāo)使用多目標(biāo)文化基因算法進(jìn)行優(yōu)化.(2)基于Agent的優(yōu)化方法.這類方法優(yōu)化后的結(jié)果與使用元啟發(fā)式算法得到的結(jié)果有一定的差距；Wong等使用基于Agent的談判方法求解IPPS問(wèn)題并提出了工件Agent和機(jī)器Agent間的談判協(xié)議[16].(3)其他方法：例如基于啟發(fā)式規(guī)則的方法[17]及數(shù)學(xué)規(guī)劃方法，前者常常無(wú)法得到較優(yōu)的結(jié)果，后者無(wú)法在合理的時(shí)間內(nèi)得到最優(yōu)解.文獻(xiàn)[3]建立了一個(gè)IPPS問(wèn)題的集成融合模型，并進(jìn)行了求解.

目前，IPPS問(wèn)題的研究已取得了相應(yīng)的進(jìn)展和研究成果，但實(shí)際生產(chǎn)制造過(guò)程中某一工序的加工時(shí)間常常不固定，前續(xù)工序加工時(shí)間波動(dòng)必將影響后續(xù)工序的加工，從而影響整個(gè)調(diào)度方案的實(shí)施，這是現(xiàn)有IPPS問(wèn)題研究的一大挑戰(zhàn).因此，研究加工時(shí)間不確定的IPPS問(wèn)題有現(xiàn)實(shí)的意義.相對(duì)于確定的IPPS問(wèn)題，加工時(shí)間不確定的IPPS問(wèn)題的研究尚未成熟.常見(jiàn)的優(yōu)化方法諸如機(jī)會(huì)約束規(guī)劃方法[18]無(wú)法應(yīng)用于大規(guī)模優(yōu)化問(wèn)題.基于模糊理論的優(yōu)化方法是一種較好的優(yōu)化方法.Wang等人通過(guò)用模糊數(shù)表征不確定加工時(shí)間，提出了一種基于模糊數(shù)的人工蜂群算法求解柔性作業(yè)車間調(diào)度問(wèn)題[19]；雷德明將不確定加工時(shí)間映射為三角模糊數(shù)，在遺傳算法框架下優(yōu)化了最大完工時(shí)間[20].最近，Jamrus等人將加工時(shí)間用三角模糊數(shù)模擬，使用粒子群算法對(duì)柔性車間調(diào)度問(wèn)題進(jìn)行優(yōu)化[21].筆者前期在這方面做了相關(guān)的研究[22]，特別是在中智數(shù)建模的基礎(chǔ)上使用線性加權(quán)的方法優(yōu)化了IPPS實(shí)例，但這類方法無(wú)法給出最優(yōu)Pareto前沿,且現(xiàn)有方法在表達(dá)決策者偏好方面存在一定不足.

綜上，基于模糊數(shù)的方法大多將加工時(shí)間假設(shè)為三角模糊數(shù)，但現(xiàn)實(shí)中常常無(wú)法準(zhǔn)確估計(jì)加工時(shí)間服從何種分布或某種規(guī)律，通常僅知曉大致的波動(dòng)范圍，這為傳統(tǒng)基于模糊數(shù)優(yōu)化方法的使用帶來(lái)了困難.相反，使用中智數(shù)描述一個(gè)不確定量只需要知道極大和極小值即可，而不必求得具體的分布或規(guī)律，這為刻畫不確定加工時(shí)間帶來(lái)了方便.基于中智數(shù)的優(yōu)點(diǎn)，本文使用中智數(shù)對(duì)不確定加工時(shí)間進(jìn)行模擬并研究相應(yīng)的優(yōu)化方法.此外，決策者常常僅對(duì)目標(biāo)空間某部分的非支配解感興趣而非全部非支配解，然而現(xiàn)有文獻(xiàn)中提出的方法大多無(wú)法利用偏好信息引導(dǎo)Pareto前沿趨向于決策者感興趣的區(qū)域.因此，本文利用中智數(shù)刻畫不確定加工時(shí)間，提出基于偏好的ε-支配優(yōu)化算法求解多目標(biāo)不確定IPPS問(wèn)題，并對(duì)名義最大完工時(shí)間及魯棒性兩個(gè)指標(biāo)進(jìn)行優(yōu)化.

1 基本概念與問(wèn)題描述

1.1 中智數(shù)及其運(yùn)算

中智數(shù)最早由Smarandache教授提出[23]，可表示為N=a+bI，其中a和b為兩個(gè)實(shí)數(shù)，I為不確定區(qū)間，滿足I2=I,0·I=0.例如：N=2.2+0.3I其中I=[-0.1,0.5]等價(jià)于N=[2.17,2.35]，也可表示為N=2.17+0.18I,I=[0,1].通過(guò)調(diào)整參數(shù)a和b可將兩中智數(shù)的不確定部分調(diào)整為同一個(gè)I.中智數(shù)的加減法運(yùn)算可表示為N1±N2=a1±a2+(b1±b2)I.對(duì)兩個(gè)中智數(shù)Ni=ai+biI,Nj=aj+bjI，I=[β-,β+]，則Ni≥Nj的概率可表示為[24]：

(1)

對(duì)于n個(gè)中智數(shù)，兩兩之間通過(guò)式(1)計(jì)算后可得到概率矩陣P=(Pij)n×n，根據(jù)(2)式計(jì)算每個(gè)中智數(shù)排序順序值ri，則最大ri值對(duì)應(yīng)的中智數(shù)即為n個(gè)中智數(shù)中最大者.

(2)

中智數(shù)的“取大”算子可定義為：

1.2 問(wèn)題描述與建模

IPPS問(wèn)題可定義為：給定n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件均含有若干道工序，通過(guò)選取合理的工序、機(jī)器、加工順序，得到最優(yōu)調(diào)度方案.如圖1所示，IPPS問(wèn)題中可選的工序、加工資源及加工時(shí)間可用網(wǎng)絡(luò)圖進(jìn)行描述[9].圖中開(kāi)始節(jié)點(diǎn)和終止節(jié)點(diǎn)為虛擬節(jié)點(diǎn)，表示一個(gè)工件加工的開(kāi)始與結(jié)束.每個(gè)普通節(jié)點(diǎn)代表一個(gè)工序，提供了該工序的ID、備選加工設(shè)備及相應(yīng)的加工時(shí)間.若某個(gè)分支旁標(biāo)有“OR”，則兩個(gè)分支中只需選擇一個(gè)分支上的工序即可.各工序只要滿足箭頭所指的先后關(guān)系(直接或間接)即可.相對(duì)于傳統(tǒng)柔性作業(yè)車間問(wèn)題，IPPS問(wèn)題中存在著三種柔性：工序柔性、序列柔性、加工柔性.工序柔性是指一個(gè)工序可在任意一臺(tái)備選的設(shè)備上加工；序列柔性是指同樣一組工序可以有若干種排列方式，只要符合網(wǎng)絡(luò)圖中的先后順序；加工柔性是指可以選擇不同的“OR”分支上的工序來(lái)完成工件加工.參考現(xiàn)有的IPPS問(wèn)題的數(shù)學(xué)模型[15]，對(duì)中智數(shù)的確定部分和不確定部分分離，可以建立基于中智數(shù)的IPPS數(shù)學(xué)模型.

首先對(duì)模型中所需的相關(guān)符號(hào)、變量等進(jìn)行定義.

n：工件集合

M：機(jī)器集合

Ti：工件i的所有工藝規(guī)劃集合

NOil：工件i的第j個(gè)工藝規(guī)劃所有工序集合

Rijl：工序Oijl的可用機(jī)器集合

A：一個(gè)很大的正整數(shù)

Xil：=1，若工件i的第l個(gè)工藝規(guī)劃選中；=0，否則

Zijkl：=1，若工序Oijl在機(jī)器k上加工；=0，否則

Yijli′j′l′：=1，若工序Oijl直接或間接地在工序Oi′j′l′之后加工；=0，否則

優(yōu)化目標(biāo)：

(3)

(4)

約束方程：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

1.3 ε-支配與多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化算法中，常得到一組折中解(非支配解)，而不是全局最優(yōu)解，以便決策者從中選取較為合理的方案.具有代表性的算法為Deb等人提出的NSGA-II多目標(biāo)遺傳算法[25].然而，現(xiàn)有多目標(biāo)進(jìn)化算法常將算法得到的非支配解全部呈現(xiàn)于決策者，而無(wú)法在進(jìn)化中融入決策者的偏好信息，因此可以在算法中融入偏好信息，引導(dǎo)算法的搜索過(guò)程集中于感興趣的區(qū)域.本文通過(guò)目標(biāo)空間中的一控制點(diǎn)引入偏好信息，將目標(biāo)空間劃分為偏好區(qū)域和非偏好區(qū)域，提出基于偏好及中智數(shù)的ε-支配多目標(biāo)進(jìn)化算法.

定義1：設(shè)p和q為群體中任意兩個(gè)個(gè)體，則當(dāng)fi(p)≤fi(q),?i且fj(p)

定義2：若一個(gè)個(gè)體p沒(méi)有被當(dāng)前所有個(gè)體支配，稱p為非支配解；群體中所有非支配解構(gòu)成Pareto前沿.

在ε-支配中先將目標(biāo)空間劃分為若干尺度為εj的格子，通過(guò)格子間的支配關(guān)系決定個(gè)體間的支配關(guān)系.通過(guò)控制格子的尺度進(jìn)而控制非支配解的分布.

2 算法設(shè)計(jì)

IPPS問(wèn)題為NP-Hard問(wèn)題，整數(shù)線性規(guī)劃難以對(duì)其求解.本研究由于引入了中智數(shù)，導(dǎo)致模型更加復(fù)雜，求解更加困難.故本文提出一種ε-支配多目標(biāo)遺傳算法.以下介紹算法的編碼、選擇交叉等操作并給出該算法的流程圖.

2.1 編碼方案

如圖2所示，一個(gè)個(gè)體中包含調(diào)度串、工藝規(guī)劃串、工序串.調(diào)度串采用基于工序的編碼方法，數(shù)字i第j次出現(xiàn)對(duì)應(yīng)工序?yàn)楣ぜ工序串中第j個(gè)位置的工序，調(diào)度串中含有的格子數(shù)恰好為實(shí)際一個(gè)調(diào)度問(wèn)題中最大可能的工序數(shù).工件i的序號(hào)在調(diào)度串中正好出現(xiàn)|NOil|次，當(dāng)各工件實(shí)際工序數(shù)之和小于各工件最大可能的工序數(shù)之和，則在調(diào)度串多余位置用數(shù)字0補(bǔ)足.圖2a)中各工件分別有3,2,4個(gè)工序，因此，無(wú)須在調(diào)度串中補(bǔ)零.工序串反映了工藝規(guī)劃的信息，每一個(gè)格子代表一個(gè)工序，括號(hào)內(nèi)分別是工序ID及對(duì)應(yīng)的機(jī)床.例如，圖2a)中第一個(gè)工件三個(gè)工序加工順序?yàn)?,1,2且分別在機(jī)床2,1,4上加工.工藝規(guī)劃串僅含一位數(shù)字，代表該工件所選擇的工藝規(guī)劃(工序組合)代號(hào).對(duì)于圖1中的工件，根據(jù)“OR”節(jié)點(diǎn)，分為兩個(gè)工藝規(guī)劃(工序組合)：工序1-11、14和工序1-8、12-14.

圖2 編碼方案與遺傳操作

2.2 解碼方法

傳統(tǒng)調(diào)度問(wèn)題采用主動(dòng)調(diào)度方法進(jìn)行解碼并生成甘特圖，相對(duì)于半主動(dòng)調(diào)度，基于主動(dòng)調(diào)度的解碼方法能夠生成更優(yōu)的調(diào)度方案.但本研究中工序加工時(shí)長(zhǎng)和最大完工時(shí)間均為中智數(shù)，無(wú)法直接使用現(xiàn)有的解碼方法.改進(jìn)的解碼方法主要步驟如下：

(N3為機(jī)床k上空余時(shí)間段結(jié)束時(shí)間)時(shí)可將當(dāng)前工序安排到機(jī)器上當(dāng)前空余時(shí)間段.

(3)若無(wú)法在空余的時(shí)間段內(nèi)插入工序，只能將工序安排到相應(yīng)機(jī)床的當(dāng)前末尾的位置，工序開(kāi)工時(shí)間為：

(4)按照個(gè)體調(diào)度串中的序號(hào)，重復(fù)上述步驟，逐個(gè)處理完所有工序.

2.3 遺傳操作

考慮到非支配解的數(shù)量多少以及個(gè)體進(jìn)化的快慢，本文提出的算法部分參考了NSGA-II算法及現(xiàn)有的ε-支配多目標(biāo)算法，算法包括的遺傳操作主要有交叉和變異操作.圖2b)為交叉操作的過(guò)程，選取兩個(gè)父代個(gè)體P1、P2中被選中的工序串與工藝規(guī)劃串并復(fù)制一份分別放到兩個(gè)子代個(gè)體O2、O1對(duì)應(yīng)位置；將P1(P2)中未選中工件的工藝規(guī)劃串和工序串復(fù)制一份到O1(O2)相應(yīng)位置.由于同一工件不同工藝規(guī)劃包含不同數(shù)目的工序，需要調(diào)整兩個(gè)個(gè)體的調(diào)度串.將個(gè)體P1(P2)調(diào)度串中未被選中個(gè)體的ID按照原位置填入O1(O2)調(diào)度串對(duì)應(yīng)位置中，將個(gè)體P2(P1)調(diào)度串中被選中個(gè)體的ID依次填入O1(O2)調(diào)度串對(duì)應(yīng)空位中.所有工件的工序均填入調(diào)度串后空缺位置用數(shù)字0填充.圖2b)中由于P1、P2中第三個(gè)工件分別有3、4個(gè)工序，交換后個(gè)體O2的調(diào)度串中需要補(bǔ)充一個(gè)數(shù)字0.此外，為充分利用IPPS網(wǎng)絡(luò)圖中序列柔性，如圖2c)所示，設(shè)計(jì)了工藝規(guī)劃間的單點(diǎn)交叉操作.

變異操作包含三種：隨機(jī)交換調(diào)度串中兩個(gè)任意位置的數(shù)字；為某工序隨機(jī)選取不同的機(jī)床；為某工件重新生成一新的工藝規(guī)劃.算法運(yùn)行變異操作時(shí)在三種變異中隨機(jī)選取一種.

2.4 選擇操作與算法流程

對(duì)于決策者給定的點(diǎn)P(坐標(biāo)為(Pf1,Pf2))，最小化問(wèn)題中偏好區(qū)域即為坐標(biāo)原點(diǎn)與點(diǎn)P圍成的矩形，如圖3所示.除偏好區(qū)域外的其余目標(biāo)空間為非偏好區(qū).將兩部分區(qū)域劃分不同尺度的網(wǎng)格，ε-支配即為網(wǎng)格間的支配.顯然，偏好區(qū)網(wǎng)格較非偏好區(qū)更密，這表明偏好區(qū)域能夠容納更多的非支配解，而在非偏好區(qū)由于網(wǎng)格尺度較粗，僅能容納少量的非支配解，這樣引導(dǎo)算法的非支配解更多地分布于偏好區(qū).

圖3 ε-支配示意

隨機(jī)產(chǎn)生初始個(gè)體后，構(gòu)造普通Pareto支配的非支配解集合：將初始個(gè)體利用NSGA-II類似算法得到非支配個(gè)體(此時(shí)可能有不止一個(gè)個(gè)體處于同一格子中)，按照第一個(gè)指標(biāo)f1的數(shù)值由小到大排列各個(gè)非支配解，依次將排列后的非支配解按上述定義3的方法放入指定的格子中，從第二個(gè)非支配解開(kāi)始，判斷若當(dāng)前處理的個(gè)體與前一個(gè)個(gè)體均處于偏好區(qū)或非偏好區(qū)則進(jìn)一步按以下處理：

1)若當(dāng)前個(gè)體C(如圖3)在已有個(gè)體A下方，則刪除個(gè)體C上方所有個(gè)體；

2)若當(dāng)前個(gè)體B(如圖3)在已有個(gè)體B右方，則刪除當(dāng)前個(gè)體B；

3)若當(dāng)前個(gè)體E(如圖3)和已有個(gè)體D在同一格，則只保留距離該格子左下角頂點(diǎn)歐氏距離最短的點(diǎn)(圖中為E點(diǎn)).

否則接受當(dāng)前個(gè)體.

這樣，處理完所有非支配解后得到了初始?xì)w檔集.初始?xì)w檔集中的個(gè)體相互間均不構(gòu)成ε-支配關(guān)系.之后算法按照選擇、交叉、變異進(jìn)行優(yōu)化，但傳統(tǒng)ε-支配多目標(biāo)優(yōu)化算法中每次僅進(jìn)行單個(gè)個(gè)體間的交叉操作，效率與優(yōu)化效果較差.此外，為提高偏好區(qū)域中的個(gè)體被選入下一代的概率，對(duì)選擇操作進(jìn)行了改進(jìn)，具體如下：

1)任取兩個(gè)個(gè)體若均在非偏好區(qū)，則去掉非支配的個(gè)體，保留另一個(gè)個(gè)體；

2)若兩個(gè)個(gè)體均在偏好區(qū)，則同時(shí)接受這兩個(gè)個(gè)體；

3)若兩個(gè)個(gè)體所屬區(qū)域不同，確保處于偏好區(qū)的個(gè)體被選中，若另一個(gè)體支配處于偏好區(qū)的個(gè)體，則也被選中進(jìn)入下一代；

4)重復(fù)以上步驟直到所選個(gè)體數(shù)目達(dá)到規(guī)定要求.

為改善個(gè)體多樣性，選擇操作中允許一小部分新生成的個(gè)體代替老的個(gè)體.算法每一輪進(jìn)化后允許15%的新生成個(gè)體代替老的個(gè)體.

歸檔集更新主要考慮用當(dāng)前群體中的非支配解更新原歸檔集中的ε-非支配解.因此，先將當(dāng)前群體中非支配解和歸檔集中的個(gè)體合并，并按照第一個(gè)指標(biāo)f1的數(shù)值由小到大排列各個(gè)體，參考初始?xì)w檔集生成方法，得到當(dāng)前更新后的歸檔集.需要注意的是：若前后兩個(gè)個(gè)體均處于(非)偏好區(qū)，按ε-支配關(guān)系決定是否保留個(gè)體，若前后兩個(gè)個(gè)體處于不同區(qū)域的直接按普通的Pareto支配關(guān)系決定是否保留個(gè)體.

本文使用中智數(shù)來(lái)模擬現(xiàn)實(shí)中不確定的加工時(shí)長(zhǎng)及完工時(shí)間，定義了兩種不同的工序加工時(shí)長(zhǎng)波動(dòng)范圍：1)小范圍波動(dòng)：工序加工時(shí)長(zhǎng)最大波動(dòng)量為其名義值的±5%；2)較大范圍波動(dòng)：工序加工時(shí)長(zhǎng)最大波動(dòng)量為其名義值的±15%.算法主要流程如圖4所示.

圖4 算法流程

本文主要考慮兩個(gè)優(yōu)化指標(biāo)：名義最大完工時(shí)間指標(biāo)及魯棒性指標(biāo).由于實(shí)際的最大完工時(shí)間是一個(gè)中智數(shù)，完工時(shí)間存在圍繞名義值上下波動(dòng)的情況，故本文中魯棒性指標(biāo)定義為最大完工時(shí)間上下波動(dòng)的最大偏差.顯然，完工時(shí)間波動(dòng)的偏差越小則魯棒性越好.

3 計(jì)算實(shí)例及分析

3.1 參數(shù)設(shè)置

計(jì)算實(shí)例來(lái)自Kim等人提出的一組實(shí)例[9]，共有24個(gè)實(shí)例.工序加工時(shí)長(zhǎng)精確到小數(shù)點(diǎn)后三位.名義最大完工時(shí)間和魯棒性指標(biāo)分別對(duì)應(yīng)目標(biāo)空間中的橫、縱坐標(biāo).在偏好區(qū)，橫、縱坐標(biāo)的偏差εj分別為0.005和0.004；在非偏好區(qū)，橫、縱坐標(biāo)的偏差分別為0.05和0.04.個(gè)體總數(shù)設(shè)置為800個(gè)，迭代次數(shù)800次，交叉和變異概率分別為0.7和0.08.所有計(jì)算在一臺(tái)裝有I5-9600(3.7GHz)CPU及16GB內(nèi)存的計(jì)算機(jī)上進(jìn)行.

3.2 計(jì)算結(jié)果與分析

首先求解Kim實(shí)例中最復(fù)雜的第24個(gè)實(shí)例，該實(shí)例中含有18個(gè)工件，在15臺(tái)機(jī)床上加工.比較在工序加工時(shí)長(zhǎng)處于較小波動(dòng)范圍時(shí)得到的非支配解；圖5為相應(yīng)的Pareto前沿，本例中偏好區(qū)域?yàn)?≤f1≤650及0≤f2≤20圍成的矩形區(qū)域.由圖可知，初始非支配解經(jīng)過(guò)不斷進(jìn)化形成了最終的Pareto前沿，并且大多數(shù)ε-非支配解集中于偏好區(qū)域(圖中方框內(nèi)區(qū)域?yàn)槠脜^(qū)域).此外，非偏好區(qū)域內(nèi)的非支配解只有一個(gè)，這說(shuō)明提出的ε-非支配多目標(biāo)算法確實(shí)能夠根據(jù)決策者偏好獲得較多的非支配解.圖6為相同條件下，偏好區(qū)域?yàn)?≤f1≤550,0≤f2≤35時(shí)的非支配解分布.顯然，對(duì)于不同的偏好區(qū)域，ε-非支配解分布的區(qū)域不同且隨偏好區(qū)域改變而改變.本例中ε-非支配解仍然集中于偏好區(qū)且只有兩個(gè)非支配解處于偏好區(qū)之外，因此，這表明提出的算法確實(shí)能夠使非支配解盡可能集中于偏好區(qū).

圖7為當(dāng)加工時(shí)長(zhǎng)在較大范圍波動(dòng)下第24個(gè)實(shí)例的Pareto前沿.對(duì)比前幾個(gè)圖可以發(fā)現(xiàn)當(dāng)加工時(shí)間的波動(dòng)范圍增加時(shí)，得到的最大工期波動(dòng)范圍也隨著增加，但對(duì)名義最大工期影響不是很大.此外，大多數(shù)非支配解均分布于給定的偏好區(qū)域(0≤f1≤600,0≤f2≤45).

圖5第24個(gè)實(shí)例小波動(dòng)范圍非支配解分布

圖6 第24個(gè)實(shí)例小波動(dòng)范圍非支配解分布(不同偏好區(qū)域)

圖7第24個(gè)實(shí)例較大波動(dòng)范圍非支配解分布

圖8為圖7中偏好區(qū)域內(nèi)某非支配解對(duì)應(yīng)的甘特圖(名義加工時(shí)間).圖9為第12個(gè)實(shí)例優(yōu)化前后的非支配解分布(加工時(shí)間較大范圍波動(dòng)下)，優(yōu)化后非支配解數(shù)量增加且主要分布于偏好區(qū)內(nèi).

選取Kim實(shí)例中第1、12、24三個(gè)實(shí)例(此三個(gè)實(shí)例分別代表典型的小、中、大規(guī)模實(shí)例)，得到每個(gè)實(shí)例5次計(jì)算時(shí)長(zhǎng)的平均值并將該平均值與Kim實(shí)例相應(yīng)實(shí)例的計(jì)算時(shí)長(zhǎng)進(jìn)行比較，相關(guān)結(jié)果列于表1中.

圖8 第24個(gè)實(shí)例的甘特圖

圖9第12個(gè)實(shí)例的非支配解分布

表1 計(jì)算時(shí)長(zhǎng)對(duì)比

由表1可知，求解大規(guī)模實(shí)例時(shí)，本文提出的算法所需計(jì)算時(shí)間較短.說(shuō)明本文算法在求解這類實(shí)例時(shí)具有較高的效率，能快速找到合理的非支配解.同時(shí)，對(duì)于中小規(guī)模的實(shí)例，文獻(xiàn)[9]的算法計(jì)算較快，這是由于本文使用了中智數(shù)模擬不確定加工時(shí)間，在解碼等過(guò)程中中智數(shù)的運(yùn)算增加了計(jì)算量.此外，為得到偏好區(qū)與非偏好區(qū)內(nèi)的非支配解，特別是保留并增加偏好區(qū)中的非支配解，本文提出了較為復(fù)雜的非支配排序方法，這也使得計(jì)算過(guò)程變得相對(duì)復(fù)雜，因此增加了計(jì)算時(shí)間.

4 結(jié)語(yǔ)

工序加工時(shí)間的不確定性給調(diào)度的魯棒性帶來(lái)了挑戰(zhàn)，鑒于中智數(shù)在描述不確定信息方面具有優(yōu)勢(shì)，本文將其引入集成式工藝規(guī)劃與調(diào)度問(wèn)題的優(yōu)化中，建立了基于中智數(shù)的數(shù)學(xué)模型，提出了基于ε-支配的多目標(biāo)優(yōu)化算法.通過(guò)控制網(wǎng)格尺度及參考點(diǎn)的設(shè)定控制非支配解的分布.算法對(duì)名義最大完工時(shí)間及魯棒性兩個(gè)指標(biāo)進(jìn)行了優(yōu)化，計(jì)算結(jié)果證明了算法的有效性，大多數(shù)非支配解集中于偏好區(qū)域.