考慮序列設(shè)置時(shí)間的混合流水車間多目標(biāo)調(diào)度研究

黃 輝，李夢(mèng)想，嚴(yán) 永

(西北工業(yè)大學(xué) 管理學(xué)院，陜西 西安 710072)

0 引言

隨著經(jīng)濟(jì)社會(huì)的發(fā)展，技術(shù)水平和生活方式的革新與轉(zhuǎn)變，產(chǎn)品模式消費(fèi)需求逐漸開(kāi)啟了差異化個(gè)性化定制化的征程，相應(yīng)的生產(chǎn)模式將更多的轉(zhuǎn)向多品種小批量的混合流水生產(chǎn)。目前，在生產(chǎn)周期，設(shè)備利用率，生產(chǎn)成本等各項(xiàng)指標(biāo)下，混合流水生產(chǎn)企業(yè)正面臨著越來(lái)越復(fù)雜的生產(chǎn)調(diào)度問(wèn)題，因此針對(duì)混合流水生產(chǎn)調(diào)度的研究也顯得愈發(fā)迫切與重要。

Naderi B等[1]研究了存在工序跳躍的混合流水車間調(diào)度(Hybrid Flow Shop Scheduling，HFSS)問(wèn)題，以最小化最大完工周期為目標(biāo)建立模型并求解。Dios M等[2]研究了存在工序跳過(guò)的混合流程車間調(diào)度問(wèn)題，重點(diǎn)分析了存在工序跳過(guò)的HFSS問(wèn)題的難度并設(shè)計(jì)了新的啟發(fā)式算法進(jìn)行求解。Ebrahimi M等[3]研究了混合流水車間中依靠序列設(shè)置時(shí)間的調(diào)度問(wèn)題，同時(shí)考慮交貨期的不確定性和隨機(jī)性，建立模型并求解。Nikjo B和Zarook Y[4]提出了一種新的考慮工件間設(shè)置時(shí)間的以最小化最大完工時(shí)間為目標(biāo)的動(dòng)態(tài)流水車間制造單元調(diào)度問(wèn)題的數(shù)學(xué)模型并求解。徐建有等[5]和楊開(kāi)兵等[6]考慮設(shè)置時(shí)間建立了多目標(biāo)流水車間調(diào)度優(yōu)化模型并進(jìn)行求解。喻明讓等[7]研究了考慮調(diào)整時(shí)間和機(jī)械故障的作業(yè)車間調(diào)度問(wèn)題。周炳海和王騰[8]研究了考慮換模時(shí)間約束的混合流水車間調(diào)度問(wèn)題。張煜等[9]研究了考慮設(shè)置時(shí)間和存在批處理機(jī)的HFSS問(wèn)題。Visalakshi P和Sivanandam S N[10]研究了以負(fù)荷均衡為調(diào)度目標(biāo)的動(dòng)態(tài)車間調(diào)度問(wèn)題。Pach C等[11]研究了以完工時(shí)間，能耗和資源轉(zhuǎn)換的數(shù)量為多目標(biāo)的柔性制造車間的調(diào)度問(wèn)題。賀利軍等[12]研究了以最大完工時(shí)間，最小化拖期時(shí)間，最小化庫(kù)存成本以及最小化拖期成本為多目標(biāo)的流水車間調(diào)度問(wèn)題。蔣增強(qiáng)和左樂(lè)[13]研究了以能源消耗，加工質(zhì)量，最大完工時(shí)間，和加權(quán)成本為多目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題。施進(jìn)發(fā)等[14]研究了以最小機(jī)器總負(fù)荷，最小提前/拖期完工的懲罰值，最大設(shè)備利用率和成品合格率為多目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題；顧澤平等[15]研究了以最小化最大流程時(shí)間、設(shè)備負(fù)荷均衡以及最大化設(shè)備利用率為優(yōu)化目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題。

通過(guò)已有研究，可以發(fā)現(xiàn)在混合流水生產(chǎn)的研究中，針對(duì)帶有工序跳躍問(wèn)題或序列設(shè)置時(shí)間約束的調(diào)度問(wèn)題的研究相對(duì)較少，同時(shí)絕大部分文獻(xiàn)都是研究單目標(biāo)的，其中以最小化最大完工時(shí)間為目標(biāo)的最多，僅有少部分研究了多目標(biāo)問(wèn)題。而在實(shí)際的混合流水生產(chǎn)中，工序跳躍問(wèn)題，設(shè)置時(shí)間問(wèn)題以及調(diào)度的多目標(biāo)化是非常常見(jiàn)的問(wèn)題，且絕大多數(shù)生產(chǎn)系統(tǒng)都同時(shí)存在這三種問(wèn)題，因此忽略這三個(gè)問(wèn)題去研究生產(chǎn)系統(tǒng)調(diào)度，會(huì)由于與實(shí)際生產(chǎn)存在較大偏差而大大降低其研究?jī)r(jià)值和意義。本文在現(xiàn)有的研究基礎(chǔ)之上充分考慮這三個(gè)問(wèn)題，建立相應(yīng)的數(shù)學(xué)規(guī)劃模型并運(yùn)用啟發(fā)式算法進(jìn)行求解，更加貼合實(shí)際的生產(chǎn)調(diào)度系統(tǒng)，對(duì)豐富混合流水生產(chǎn)的研究?jī)?nèi)容和指導(dǎo)實(shí)際的生產(chǎn)調(diào)度都有很大的參考價(jià)值和意義。

1 混合流水車間調(diào)度模型構(gòu)建

1.1 問(wèn)題描述

混合流水線調(diào)度問(wèn)題(hybrid flow-shop scheduling problem, HFSP)最早由Salvador于1973年提出。標(biāo)準(zhǔn)的HFSP可描述為：n個(gè)工件在m個(gè)階段的流水線上加工，各階段均有一臺(tái)或多臺(tái)機(jī)器且必須有不少于一個(gè)階段擁有兩臺(tái)及以上機(jī)器，同一階段上各機(jī)器的處理性能相同，各個(gè)工件必須且只需在每個(gè)階段的任意一臺(tái)機(jī)器上加工一次[16]。

在實(shí)際生產(chǎn)中，標(biāo)準(zhǔn)HFSP相對(duì)較少，大多是標(biāo)準(zhǔn)HFSP的變形，其中有些工件在加工時(shí)存在工序跳躍的現(xiàn)象比較常見(jiàn)。這時(shí)為了使所有任務(wù)在加工時(shí)都能符合混合流水生產(chǎn)的標(biāo)準(zhǔn)模式，不妨假設(shè)那些需要跳躍的工序也需要進(jìn)行加工作業(yè)，即設(shè)置虛擬作業(yè)并將其加工作業(yè)時(shí)間設(shè)置為0，同時(shí)為了減小對(duì)其他作業(yè)順序的影響，可以設(shè)置虛擬的專用機(jī)器用于虛擬作業(yè)的加工，這樣企業(yè)的生產(chǎn)狀況就能符合混合流水生產(chǎn)的標(biāo)準(zhǔn)。相應(yīng)的也就可以應(yīng)用混合流水生產(chǎn)調(diào)度的方法和理論來(lái)針對(duì)企業(yè)現(xiàn)有的現(xiàn)狀和問(wèn)題進(jìn)行改進(jìn)優(yōu)化研究。

1.2 模型假設(shè)

基于上述分析，本文可以構(gòu)建企業(yè)的混合流水生產(chǎn)多目標(biāo)調(diào)度優(yōu)化模型。為使構(gòu)建的模型更加科學(xué)嚴(yán)謹(jǐn)，還需要對(duì)其他未被考慮的因素做出如下假設(shè)條件：

(1)不同調(diào)度方案的生產(chǎn)成本無(wú)差異；

(2)同一階段各加工設(shè)備屬相同并行機(jī)；

(3)每個(gè)加工任務(wù)在第一階段的發(fā)布時(shí)間均為0，且在其余階段均無(wú)時(shí)間窗限制；

(4)各加工任務(wù)經(jīng)過(guò)其序列設(shè)置時(shí)間后立即開(kāi)始加工；

(5)加工任務(wù)按照其優(yōu)先權(quán)進(jìn)行排序，優(yōu)先權(quán)大的工件序號(hào)排在前面，在同等條件下可優(yōu)先進(jìn)行加工；

(6)緩沖區(qū)容量為無(wú)窮大且操作允許等待，即加工任務(wù)的前一工序未完成，則后面的工序需要等待；

(7)每個(gè)任務(wù)的加工時(shí)間和序列設(shè)置時(shí)間事先給定，且在整個(gè)加工過(guò)程中保持不變；

(8)在加工任務(wù)存在工序跳躍的工序設(shè)定虛擬機(jī)器進(jìn)行虛擬作業(yè)。

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

(1)索引

i為加工任務(wù)索引，i∈{1,2,3,…,N}；

s為工序索引，s∈{1,2,3,…,S}；

k為工序s的機(jī)器索引，k∈{1,2,3,…,Ms}；

r為工序s下一加工工序snext的機(jī)器索引，若對(duì)應(yīng)工件下一工序跳過(guò)則表示下下工序，以此類推，r∈{1,2,3,…,Ms}；

l為各工序各機(jī)器設(shè)備的位置索引，l∈{1,2,3,…,Ns,k}。

(2)參數(shù)

N為加工任務(wù)總數(shù)量；

S為總工序數(shù)量；

Ms為工序s的實(shí)際機(jī)器數(shù)量，不包括加工虛擬作業(yè)的虛擬機(jī)器；

Ns為工序s加工的任務(wù)數(shù)，若該工序不存在工序跳躍則Ns=N，反之Ns等于N減去跳躍的任務(wù)數(shù)；

Ns,k為工序s上機(jī)器k加工的總加工任務(wù)數(shù)；

ti,s,k為加工任務(wù)i在s工序的設(shè)備k上的加工時(shí)間；

ps,m,l-1,l為在s工序k機(jī)器上第l-1位置的加工任務(wù)到第l位置的加工任務(wù)的加工的序列設(shè)置時(shí)間，通常為換模時(shí)間。

(3)變量

Ui,s,k,l當(dāng)加工任務(wù)i安排在工序s的機(jī)器k上的第l位置加工時(shí)Ui,s,k,l=1，反之，則Ui,s,k,l=0;

ci,s,k為加工任務(wù)i在s工序的k機(jī)器上的完工時(shí)間，若s=S則表示該加工任務(wù)的完工時(shí)間；

si,s,k為加工任務(wù)i在s工序的k機(jī)器上的開(kāi)始加工時(shí)間；

si,snext,r為加工任務(wù)i在snext工序的r機(jī)器上的開(kāi)始加工時(shí)間；

1.4 生產(chǎn)調(diào)度數(shù)學(xué)模型

本文充分考慮工序跳躍問(wèn)題，設(shè)置時(shí)間問(wèn)題和調(diào)度的多目標(biāo)化三個(gè)重要指標(biāo)，構(gòu)建更加符合企業(yè)實(shí)際生產(chǎn)狀況的混合流水生產(chǎn)多目標(biāo)調(diào)度優(yōu)化的數(shù)學(xué)模型如下:

minf1=Zp=min(max(ci,s,k))

(1)

(2)

公式(1)表示調(diào)度的目標(biāo)函數(shù)1最小化最大完工時(shí)間，即最后一道工序的最大完工工時(shí)間最小；公式(2)表示調(diào)度目標(biāo)2設(shè)備負(fù)荷均衡指標(biāo)，即各工序內(nèi)各機(jī)器設(shè)備的加工時(shí)間的標(biāo)準(zhǔn)差的均值；公式(3)表示機(jī)器約束，任意加工任務(wù)在任一工序只能在一臺(tái)機(jī)器設(shè)備上加工一次，若該任務(wù)在該工序存在工序跳躍，即使用虛擬機(jī)器進(jìn)行虛擬作業(yè)，則可以忽略不記；公式(4)表示任務(wù)約束，即任意加工任務(wù)都必須在每個(gè)工序進(jìn)行加工，不包括虛擬加工；公式(5)表示時(shí)間約束，只有前一工序的加工完成后才能開(kāi)始下一工序的生產(chǎn)；公式(6)表示加工任務(wù)的完工時(shí)間等于開(kāi)始時(shí)間加上加工任務(wù)的加工時(shí)間和序列設(shè)置時(shí)間；公式(7)表示設(shè)備只有上一加工任務(wù)加工結(jié)束后才能開(kāi)始下一加工任務(wù)的加工；公式(8)表示工序內(nèi)每臺(tái)機(jī)器設(shè)備的平均加工時(shí)間，不包括虛擬機(jī)器。

2 NSGA-II算法設(shè)計(jì)

參考同類研究可以發(fā)現(xiàn)多目標(biāo)的GA更適合求解本文所研究的具體問(wèn)題，常見(jiàn)有多目標(biāo)遺傳算法(MOGA)，小生境Pareto遺傳算法(NPGA)，非支配解排序遺傳算法(NSGA和NSGA-II)等，其中在多目標(biāo)的研究中，NSGA-II普遍具有更好的性能和效率。但是標(biāo)準(zhǔn)的NSGA-II在求解不同問(wèn)題時(shí)也存在一定的不足之處，如在進(jìn)行交叉變異操作時(shí)，其交叉變異參數(shù)固定不變，不利于最優(yōu)解搜索；精英保留策略選擇下一代時(shí)完全按照等級(jí)排序來(lái)選擇，未考慮進(jìn)化后期會(huì)出現(xiàn)大量重復(fù)個(gè)體以至于種群多樣性大大減小，從而影響算法后期的搜索能力等。為了獲得更加準(zhǔn)確的Pareto最優(yōu)解，本文針對(duì)NSGA-II的不足之處，設(shè)計(jì)了一種改進(jìn)的NSGA-II算法來(lái)進(jìn)行求解。

2.1 編碼設(shè)計(jì)

車間調(diào)度優(yōu)化問(wèn)題常采用實(shí)數(shù)編碼，混合流水生產(chǎn)調(diào)度問(wèn)題是車間調(diào)度問(wèn)題的一種，因此本文也選用十進(jìn)制編碼。由于混合流水生產(chǎn)需要把每個(gè)任務(wù)在每個(gè)階段的操作都表示出來(lái)的特殊性，在編碼時(shí)可以采用基于機(jī)器的矩陣編碼，這樣能更加清晰明了的把每個(gè)任務(wù)在每個(gè)階段的加工設(shè)備顯示出來(lái)，且能夠使解碼操作更加方便，不足之處是矩陣編碼不利于遺傳操作。為解決這個(gè)問(wèn)題，本文選擇以矩陣思想設(shè)計(jì)編碼，即先構(gòu)建虛擬矩陣，再運(yùn)用函數(shù)將其轉(zhuǎn)化為行數(shù)組，數(shù)組與矩陣對(duì)應(yīng)位置的特征相同，然后按照轉(zhuǎn)化的行數(shù)組特征來(lái)生成初始種群，并在解碼時(shí)可將其轉(zhuǎn)化為矩陣，最后在進(jìn)行遺傳操作時(shí)仍在原數(shù)組進(jìn)行。具體編碼方式為構(gòu)建一個(gè)虛擬的N×S的矩陣(N為加工任務(wù)的數(shù)量，S為加工階段的數(shù)量)，如公式(9)所示，X為該調(diào)度問(wèn)題的一個(gè)編碼(染色體)，表示該調(diào)度問(wèn)題的一個(gè)可行解，即一個(gè)個(gè)體，矩陣中的xij表示任務(wù)i在j加工階段所使用的機(jī)器設(shè)備編號(hào)，其取值范圍取決于該工序的機(jī)器數(shù)量，若該工件在該工序的機(jī)器固定則只取一個(gè)固定的整數(shù)，若該工件需要跳過(guò)該工序，則取值為0。編碼時(shí)運(yùn)用該矩陣轉(zhuǎn)化的行數(shù)組X′(如公式(10)所示)的特性生成數(shù)組形式的染色體，再在解碼時(shí)把行數(shù)組轉(zhuǎn)化為矩陣X″，如公式(11)所示。

(9)

X′=reshape(X,1,N×S)

=[x1,1,x2,1…xN,1,x1,2,

x2,2…xN,2…x1,S,x2,S…xN,S]

(10)

X″=reshape(X′,N,S)=X

(11)

2.2 NSGA-II算法的改進(jìn)

2.2.1 種群初始化改進(jìn)

種群初始化通常都是使用相應(yīng)的函數(shù)根據(jù)設(shè)計(jì)好的染色體編碼隨機(jī)生成種群規(guī)模數(shù)量的染色體，這些染色體均為優(yōu)化問(wèn)題的可行解，他們作為初始個(gè)體共同構(gòu)成了初始種群P0。在生成初始種群時(shí)，為保障隨機(jī)概率性，各基因位的取值范圍設(shè)為實(shí)數(shù)區(qū)間，如有4臺(tái)機(jī)器設(shè)備，其取值范圍為「1,5)，在解碼時(shí)對(duì)實(shí)數(shù)進(jìn)行向下取整，獲取相應(yīng)的機(jī)器設(shè)備編號(hào)。此外，為了提高算法性能，往往還需要進(jìn)行以下處理：一是讓初始種群盡可能均勻地分布在解的空間之內(nèi)，以避免陷入局部最優(yōu)；二是采用一些簡(jiǎn)單的方法對(duì)產(chǎn)生的初始解進(jìn)行初步的篩選，剔除質(zhì)量最差的一部分解。

針對(duì)本文所設(shè)計(jì)的染色體特征，可在初始化的染色體進(jìn)行以下篩選以提高算法的搜索效率和質(zhì)量：種群中每個(gè)個(gè)體的染色體需滿足每個(gè)工序中每個(gè)機(jī)器均被使用，否則該染色體需要重新生成，直到滿足該條件為止。

2.2.2 替換操作改進(jìn)

基本NSGA-II算法的精英保留策略能夠保留各代種群中最好的個(gè)體，使算法性能和效率大大提升，但是隨著進(jìn)化代數(shù)的增加，子代種群中逐漸會(huì)出現(xiàn)大量與父代種群相同且等級(jí)較高的個(gè)體，導(dǎo)致種群的多樣性也會(huì)迅速下降，進(jìn)而出現(xiàn)早熟或者陷入局部最優(yōu)解的現(xiàn)象[17]。為彌補(bǔ)精英保留策略的這種不足之處，保證種群的多樣性以確保搜索方向朝著真正的Pareto解發(fā)展，本文針對(duì)基本的精英選擇策略進(jìn)行了一定的改進(jìn)，在執(zhí)行精英保留策略選擇下代種群時(shí)只選擇各等級(jí)種群中擁擠度不為0的個(gè)體，這樣就能保證相同個(gè)體最多只能選取兩個(gè)，這樣既保證了種群的多樣性，又在一定程度上提高了算法的搜索效率。

2.2.3 交叉參數(shù)改進(jìn)

本文中交叉概率和變異概率相互補(bǔ)充，交叉概率越大，則變異概率越小，反之則變異概率越大。通常在算法求解的前期應(yīng)優(yōu)先保證新個(gè)體的產(chǎn)生，因此交叉概率應(yīng)相對(duì)較大，而后期算法相對(duì)收斂應(yīng)擴(kuò)大搜索范圍以避免陷入局部最優(yōu)，與此同時(shí)采用精英保留策略又能很好的消除變異率過(guò)大帶來(lái)的負(fù)面影響。據(jù)此本文設(shè)計(jì)一種自適應(yīng)交叉概率參數(shù)，其交叉概率隨著遺傳代數(shù)的增加而自適應(yīng)的降低，而變異概率則自適應(yīng)的提高，交叉概率的具體取值如公式(12)所示：

(12)

式中t表示種群當(dāng)前迭代數(shù)，T是指種群最大迭代次數(shù)，T1是指第一階段的最大迭代數(shù)，這里選擇為0.25T，T2是指第二階段的最大迭代數(shù)，這里選擇為0.75T，β為進(jìn)化后期階段交叉率的調(diào)節(jié)系數(shù)，該系數(shù)的設(shè)置可以保證非支配集個(gè)體的交叉率在進(jìn)化后期階段漸近于后期階段起始值的倍，其取值范圍為(0,1]，本文在進(jìn)化后期為了避免交叉率過(guò)小，設(shè)置為β=0.8[18]。

3 算例驗(yàn)證

3.1 算例數(shù)據(jù)

本文結(jié)合具體的混合流水車間生產(chǎn)的實(shí)際情況，根據(jù)車間實(shí)際數(shù)據(jù)來(lái)假定仿真的算理數(shù)據(jù)，主要包括生產(chǎn)資源數(shù)據(jù)和生產(chǎn)任務(wù)數(shù)據(jù)。在生產(chǎn)資源數(shù)據(jù)方面，混合流水車間共有4個(gè)工序，其各工序的設(shè)備數(shù)量如表1所示，在該生產(chǎn)車間中部分生產(chǎn)任務(wù)在工序2或者工序3存在工序跳躍。

表1 生產(chǎn)設(shè)備數(shù)量表

根據(jù)該車間歷史生產(chǎn)任務(wù)，假定了一定周期內(nèi)的生產(chǎn)訂單作為仿真的任務(wù)，同時(shí)根據(jù)各個(gè)訂單的產(chǎn)品類型獲取這些生產(chǎn)任務(wù)在各工序的生產(chǎn)加工時(shí)間以及各任務(wù)之間的序列設(shè)置時(shí)間。本文共選取了20個(gè)生產(chǎn)任務(wù)進(jìn)行仿真分析，其在各工序的加工時(shí)間數(shù)據(jù)如表2所示，各任務(wù)在各工序的序列設(shè)置時(shí)間表因篇幅原因不再展示。

3.2 基于改進(jìn)NSGA-II算法的調(diào)度結(jié)果與分析

本文采用MATLAB軟件實(shí)現(xiàn)了基于改進(jìn)NSGA-II算法的混合流水生產(chǎn)企業(yè)多目標(biāo)優(yōu)化研究的算法設(shè)計(jì)及編碼求解，在實(shí)驗(yàn)過(guò)程中，計(jì)算機(jī)的基本配置如下：(1)操作系統(tǒng)為Windows7 X64旗艦版；

(2)CPU為Intel core(TM)i5-2400，3.1GHz；

(3)內(nèi)存RAM為4GB。

表2 各工序加工時(shí)間數(shù)據(jù)表(單位：小時(shí))

基于上述企業(yè)的生產(chǎn)數(shù)據(jù)運(yùn)行改進(jìn)NSGA-II算法可求解出完成該生產(chǎn)任務(wù)的Pareto最優(yōu)調(diào)度方案，運(yùn)行結(jié)果可得到負(fù)荷均衡指標(biāo)Tlb進(jìn)化收斂曲線圖，如圖1所示；最大完工時(shí)間目標(biāo)Zp進(jìn)化收斂曲線圖，如圖2所示；本次求解共求得10個(gè)Pareto最優(yōu)解集，如表3所示。

圖1 負(fù)荷均衡指標(biāo)Tlb收斂曲線圖

圖2 最大完工時(shí)間Zp收斂曲線圖

圖1和圖2中最上方曲線分別表示各代種群中負(fù)荷均衡Tlb和最大完工時(shí)間Zp兩個(gè)目標(biāo)的最大值收斂曲線，中間部分曲線分別表示各代種群中這兩個(gè)目標(biāo)的均值收斂曲線，最下方曲線表示各代種群中兩個(gè)目標(biāo)的最小值收斂曲線。由圖中可知：

(1)整體來(lái)看，在進(jìn)化前期兩個(gè)優(yōu)化目標(biāo)無(wú)論是均值還是最大值和最小值，都在迅速的減小并逐漸收斂，這表明了算法具有較好的性能，而在進(jìn)化后期兩個(gè)目標(biāo)的均值和最小值基本不變或稍微減少，最大值卻存在一定的波動(dòng)，這表明算法在保留最優(yōu)解的同時(shí)還具有較強(qiáng)的持續(xù)搜索能力，在局部范圍內(nèi)波動(dòng)時(shí)兩者的波動(dòng)存在一定的相關(guān)性，即兩個(gè)目標(biāo)的最大值基本不同時(shí)減少，往往是在一個(gè)目標(biāo)保持不變或者增大時(shí)迅速地減小，這表明在兩個(gè)目標(biāo)在進(jìn)化過(guò)程中不斷地相互均衡取舍，并最終達(dá)到相對(duì)的平衡；

(2)隨著進(jìn)化代數(shù)t的增加，各代種群的負(fù)荷均衡目標(biāo)Tlb和最大完工時(shí)間目標(biāo)Zp的平均值先迅速減少然后逐漸趨于平穩(wěn)，并于100代之后分別收斂于18和375左右，在進(jìn)化后期，各代種群中負(fù)荷均衡目標(biāo)Tlb和最大完工時(shí)間目標(biāo)Zp的均值始終更接近于最小值，這表明種群中的各可行解主要集中于最小值附近，而最大值的適當(dāng)保留又表明了各代種群的多樣性，能夠提高進(jìn)化過(guò)程的進(jìn)化空間，有效的避免陷入局部最優(yōu)。

表3 Pareto最優(yōu)解集

本次優(yōu)化共生成10組帕累托最優(yōu)解，表3共展示有代表性的6組解，Pareto最優(yōu)解各行對(duì)應(yīng)的是該工序上各加工任務(wù)所使用的機(jī)器編號(hào)，Zp和Tlb對(duì)應(yīng)的是兩個(gè)目標(biāo)值，單位為小時(shí)，從表中可以看出：

(1)從Pareto最優(yōu)解1～6可以看出，相鄰解的差異非常小，各任務(wù)中大部分任務(wù)在各工序的加工機(jī)器是完全相同的，僅有3～5個(gè)任務(wù)在部分工序上選擇的機(jī)器不同，即便是最優(yōu)解1和6這兩個(gè)目標(biāo)距離最遠(yuǎn)的解，也有一半的任務(wù)在各工序的加工機(jī)器完全相同，這表明算法在局部搜索時(shí)具有優(yōu)異的性能；

(2)在這6個(gè)解中，Pareto最優(yōu)解1的最大完工時(shí)間目標(biāo)Zp最小，Pareto最優(yōu)解6的負(fù)荷均衡目標(biāo)Tlb最小，在進(jìn)行最優(yōu)調(diào)度方案選擇時(shí)，若決策者更加看重負(fù)荷均衡目標(biāo)Tlb，則最佳決策方案更可能為Pareto最優(yōu)解6，反之若決策者更加注重最大完工時(shí)間目標(biāo)Zp，則最佳決策方案更可能為Pareto最優(yōu)解1，若兩者之間相對(duì)平衡，則最優(yōu)解更可能為中間其他解；

根據(jù)所求解的Pareto最優(yōu)解集，可以繪制各個(gè)解的甘特圖，這里以Pareto最優(yōu)解6為例，其對(duì)應(yīng)的甘特圖如圖3所示，虛線白框，黑框，實(shí)線白框和灰框依次對(duì)應(yīng)第一道工序加工時(shí)間，第二道工序加工時(shí)間，第三道工序加工時(shí)間和第四道工序加工時(shí)間。從圖3中可以更加直觀的看到各加工任務(wù)在各工序加工時(shí)所使用的機(jī)器編號(hào)，起始加工時(shí)間以及各加工任務(wù)的完工時(shí)間，其中最后完工的加工任務(wù)為17號(hào)加工任務(wù)，其加工完工時(shí)間即為所有加工任務(wù)的最大完工時(shí)間。

圖3 Pareto最優(yōu)解6的甘特圖

4 結(jié)論

目前，在生產(chǎn)周期，設(shè)備利用率，生產(chǎn)成本等各項(xiàng)指標(biāo)下，混合流水生產(chǎn)企業(yè)正面臨著越來(lái)越復(fù)雜的生產(chǎn)調(diào)度問(wèn)題，針對(duì)混合流水生產(chǎn)調(diào)度的研究也顯得愈發(fā)迫切與重要，其中結(jié)合具體企業(yè)的研究更有理論意義和實(shí)用價(jià)值。因此本文結(jié)合混合流水車間多品種生產(chǎn)的特性，基于各個(gè)加工階段各加工設(shè)備在加工不同品種的產(chǎn)品時(shí)，需要一定的序列設(shè)置時(shí)間來(lái)完成設(shè)備設(shè)置、換?；蛘{(diào)試等任務(wù)以及某些產(chǎn)品在加工時(shí)存在工序跳躍這兩種特征為主要約束條件，建立以能夠直接反映生產(chǎn)周期的最大完工時(shí)間和能夠有效反映生產(chǎn)效率的負(fù)荷均衡指標(biāo)為雙目標(biāo)的多目標(biāo)調(diào)度優(yōu)化模型。并基于一定數(shù)據(jù)進(jìn)行算例驗(yàn)證分析，證明模型的有效性。該模型能夠有效的解決此類調(diào)度優(yōu)化問(wèn)題，并為企業(yè)的實(shí)際調(diào)度提供一定的參考。