跨單元調(diào)度及其車輛路徑集成優(yōu)化

連永偉 董釗睿，2 劉 瓊

1.華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院，武漢，4300742.昆山市科學(xué)技術(shù)局，昆山，215316

0 引言

為快速響應(yīng)市場變化、減少固定資產(chǎn)投入，單元制造系統(tǒng)中允許不能在一個(gè)單元內(nèi)完成所有工序加工的異常件進(jìn)行跨單元制造[1]。跨單元調(diào)度問題不僅需要確定待加工零件在機(jī)器上的加工順序以及開工完工時(shí)間，還需要考慮如何在有限的車輛運(yùn)輸能力下優(yōu)化異常件跨單元移動(dòng)時(shí)車輛的行駛路徑，以期達(dá)到最佳優(yōu)化效果。因此，跨單元調(diào)度問題既包含生產(chǎn)調(diào)度問題，又包含異常件跨單元運(yùn)輸?shù)能囕v路徑優(yōu)化問題。

針對運(yùn)輸能力受限的跨單元調(diào)度問題，目前的研究中普遍采用優(yōu)化運(yùn)輸策略來優(yōu)化異常件跨單元運(yùn)輸?shù)臅r(shí)間和順序。ZENG等[2]針對異常件只能運(yùn)輸?shù)教囟康膯卧M(jìn)行特殊工序加工的跨單元調(diào)度問題，在運(yùn)輸策略中規(guī)定每個(gè)制造單元擁有一輛車，每次只能運(yùn)輸本單元內(nèi)的一個(gè)異常件。田云娜等[3]和劉兆赫等[4]為提高運(yùn)輸車輛裝載率，采用組批運(yùn)輸策略，將多個(gè)異常件組批并分別運(yùn)往目標(biāo)單元，在滿足車輛容量約束的前提下對異常件進(jìn)行分批次運(yùn)輸，制定運(yùn)輸規(guī)則以確定同批次異常件運(yùn)送的優(yōu)先級，但該策略可能帶來異常件等待時(shí)間過長，完工時(shí)間增加等問題。李冬妮等[5]通過構(gòu)建時(shí)間窗對組批運(yùn)輸策略進(jìn)行了改進(jìn)，即通過限定某批次運(yùn)輸?shù)漠惓＜谝粋€(gè)合理時(shí)間窗內(nèi)來確保系統(tǒng)的完工時(shí)間。賈凌云等[6]對時(shí)間窗規(guī)則進(jìn)一步改進(jìn)，利用遺傳規(guī)劃產(chǎn)生新的時(shí)間窗規(guī)則，與固定等待時(shí)間的時(shí)間窗規(guī)則共同作為候選規(guī)則，對滿足容量約束下該時(shí)間窗內(nèi)的異常件進(jìn)行組批運(yùn)輸。上述運(yùn)輸能力受限的跨單元調(diào)度研究中，均考慮每個(gè)單元擁有一輛車，只負(fù)責(zé)所屬單元內(nèi)異常件的運(yùn)輸，無論是單件運(yùn)輸還是組批運(yùn)輸，都會(huì)造成空車返回，有時(shí)還會(huì)造成零件滯留，導(dǎo)致運(yùn)輸成本和完工時(shí)間增加。為減少空回程和運(yùn)輸成本，梅旭[7]提出一種運(yùn)輸車輛共享策略，即運(yùn)輸車輛由所有制造單元共享，可運(yùn)輸任一制造單元的異常件，但研究中車輛一次最多運(yùn)輸一個(gè)異常件，無法充分利用車輛運(yùn)輸能力。由此可見，采用運(yùn)輸策略解決跨單元調(diào)度中異常件運(yùn)輸問題時(shí)存在異常件等待時(shí)間過長、車輛運(yùn)輸效率低等問題，優(yōu)化效果有待進(jìn)一步提高。

由于跨單元調(diào)度優(yōu)化問題既包含生產(chǎn)調(diào)度問題，又包含異常件跨單元運(yùn)輸時(shí)的車輛路徑問題，其中異常件跨單元運(yùn)輸時(shí)的車輛運(yùn)輸路徑問題與取送貨問題(pickup and delivery problem，PDP)[8]相似，如VELASCO等[9]和LU等[10]先后建立了單車和多車PDP模型來解決人員和貨物的運(yùn)輸問題。運(yùn)輸工具沿途依次裝載和卸載人員或貨物，與異常件跨單元運(yùn)輸都存在車輛容量約束、取送貨點(diǎn)配對約束以及取送貨點(diǎn)的先后順序約束，因此，將跨單元調(diào)度中異常件的跨單元調(diào)度作為PDP問題進(jìn)行考慮。

目前尚未檢索到跨單元調(diào)度中生產(chǎn)調(diào)度及其異常件運(yùn)輸路徑集成優(yōu)化的相關(guān)文獻(xiàn)。而運(yùn)輸能力受限的跨單元調(diào)度問題中，生產(chǎn)調(diào)度與車輛路徑相互影響：生產(chǎn)調(diào)度計(jì)劃決定車輛路徑的起止單元，影響車輛行駛路徑，車輛行駛路徑又會(huì)影響異常件特殊工序的開工時(shí)間，從而影響調(diào)度計(jì)劃。因此，將二者進(jìn)行集成優(yōu)化是可行的。

本文提出將跨單元調(diào)度及其車輛路徑進(jìn)行集成優(yōu)化，建立以最小化最大完工時(shí)間和總成本為優(yōu)化目標(biāo)的運(yùn)輸能力受限的跨單元調(diào)度及其車輛路徑規(guī)劃的集成優(yōu)化模型。

1 集成優(yōu)化問題模型

1.1 問題描述及假設(shè)

假設(shè)單元制造系統(tǒng)由分布在不同地理位置的多個(gè)制造單元組成，每個(gè)單元中存在若干臺(tái)機(jī)器，但每臺(tái)機(jī)器僅屬于一個(gè)單元；每個(gè)工件有多道工序，異常件的跨單元制造存在柔性路徑(異常工序可以在除本單元外兩個(gè)或兩個(gè)以上單元進(jìn)行加工)；系統(tǒng)中的多輛容量相同且數(shù)量已知的運(yùn)輸車為所有制造單元共享使用，在滿足容量約束的前提下，可在途經(jīng)的制造單元中依次裝載多個(gè)異常件，車輛初始位置在車場，完成所有運(yùn)輸任務(wù)后返回車場。假設(shè)：①零件、機(jī)器和運(yùn)輸車輛在零時(shí)刻被釋放，零件不同工序之間存在先后加工順序約束；②同一時(shí)刻一個(gè)零件只能被一臺(tái)機(jī)器加工；③一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)零件；④每臺(tái)機(jī)器加工零件均為非中斷非搶占式；⑤忽略制造單元內(nèi)部零件的運(yùn)輸時(shí)間，僅考慮制造單元間零件運(yùn)輸時(shí)間；⑥每輛車從車場出發(fā)時(shí)負(fù)載為零，完成其所有運(yùn)輸任務(wù)后，零負(fù)載返回車場；⑦一輛車配備一名司機(jī)；⑧不考慮物料短缺、機(jī)器故障、運(yùn)輸車輛故障等意外因素。

1.2 目標(biāo)函數(shù)及約束條件

為了保證單元制造系統(tǒng)的高效性和經(jīng)濟(jì)性，以最大完工時(shí)間和總成本最小為優(yōu)化目標(biāo)。其中總成本由三部分組成，第一部分為零件的總加工成本；第二部分為車輛的總運(yùn)輸成本；第三部分為總?cè)斯こ杀荆粗Ц督o司機(jī)的工資與駕駛時(shí)間、等待時(shí)間以及裝卸異常件時(shí)間有關(guān)。如下式所示：

minTmax=max{fio} ?i∈N?o∈O

(1)

(2)

(3)

(4)

(5)

(6)

式(1)和式(2)的約束條件如下：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

fio=Sio+tio?i∈No∈O

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

2 基于分解的多目標(biāo)進(jìn)化算法MOEA/D

由于提出的多目標(biāo)集成優(yōu)化模型具有決策變量多、約束條件多的特點(diǎn)，求解時(shí)對算法的求解效率要求較高，基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition，MOEA/D)相比其他算法在求解多目標(biāo)優(yōu)化問題時(shí)具有計(jì)算復(fù)雜度低等優(yōu)勢，因此本文采用MOEA/D進(jìn)行求解。

2.1 五段式編碼

圖1 五段式編碼Fig.1 Five-segment chromosome

2.2 車輛路徑編碼調(diào)整方法

由于隨機(jī)生成初始解和交叉變異操作后可能存在車輛路徑編碼不可行的情況，違反異常件裝卸位置之間的先后順序約束，或者不滿足車輛容量約束，為此，分別設(shè)計(jì)了一種基于二叉樹的車輛路徑編碼調(diào)整方法以及車輛容量約束調(diào)整方法，對不可行的車輛路徑編碼進(jìn)行調(diào)整。

2.2.1基于二叉樹的車輛路徑編碼調(diào)整方法

為保證車輛路徑編碼滿足異常件裝卸位置之間的先后順序約束，根據(jù)TSENG[11]提出的基于二叉樹的不可行解調(diào)整方法，設(shè)計(jì)了一種基于二叉樹的車輛路徑編碼調(diào)整方法，步驟如圖2所示。根據(jù)異常件裝卸位置的先后順序約束建立優(yōu)先關(guān)系矩陣P=[pr，c]2p×2p，其中pr，c=1表示位置r需要在位置c之后被車輛訪問，否則pr，c=0；R和L分別表示二叉樹的根節(jié)點(diǎn)和左節(jié)點(diǎn)，C為車輛路徑編碼，Ch表示車輛路徑編碼C中從左到右第h個(gè)基因值，其中h∈{1，2，…，2p}。

2.2.2車輛容量約束調(diào)整方法

2.3 解碼

對染色體進(jìn)行解碼，可得到對應(yīng)的調(diào)度方案和車輛運(yùn)輸路徑。每道工序的開工時(shí)間Sio按下式計(jì)算：

(23)

完工時(shí)間fio按式(14)計(jì)算。最大完工時(shí)間和總成本按式(1)和式(2)計(jì)算。

2.4 交叉

工序編碼的交叉采用IPOX交叉[12]。單元編碼、機(jī)器編碼、車輛編碼的交叉均采用均勻交叉(uniform crossover，UX)[13]。為保證可行解，兩個(gè)父代車輛路徑編碼不交叉，而是在車輛編碼交叉后，重新隨機(jī)生成每輛車的路徑編碼，以保證解的多樣性，同時(shí)采用設(shè)計(jì)的車輛路徑編碼調(diào)整方法進(jìn)行調(diào)整，以保證解的可行性。

2.5 變異

工序編碼采用插入變異，在工序編碼中隨機(jī)選擇一個(gè)基因，并將它插入工序編碼中另一個(gè)隨機(jī)選取的位置，其他基因順序不變；單元編碼和機(jī)器編碼中每一個(gè)基因都是一一對應(yīng)的，為保證變異后編碼的可行性，同一位置上的單元編碼和機(jī)器編碼同時(shí)進(jìn)行單點(diǎn)變異，對每個(gè)零件都隨機(jī)選擇一道工序，從該工序的候選單元和機(jī)器中隨機(jī)選擇一個(gè)單元和機(jī)器替換原來的單元與機(jī)器基因；車輛編碼也使用單點(diǎn)變異，對每一個(gè)異常件都隨機(jī)選擇其車輛編碼中的一個(gè)非“0”基因，在候選車輛中重新隨機(jī)選擇車輛；車輛路徑編碼采用交換變異，隨機(jī)選擇車輛路徑編碼中的兩個(gè)基因交換位置，為保證可行性，采用設(shè)計(jì)的車輛路徑編碼調(diào)整方法對變異后的編碼進(jìn)行調(diào)整。圖3給出了三種變異操作的示意圖，深色部分表示變異位置。

圖3 插入、單點(diǎn)、交換變異示意圖Fig.3 Description of insert，single-point and exchange mutation

2.6 MOEA/D流程

圖4所示為MOEA/D流程，采用切比雪夫分解策略[14]作為多目標(biāo)進(jìn)化算法的分解策略。

圖4 MOEA/D流程圖Fig.4 Flow chart of MOEA/D

3 案例分析

3.1 案例描述及求解結(jié)果

由于跨單元調(diào)度問題沒有benchmark問題，故采用合作企業(yè)調(diào)研數(shù)據(jù)生成算例。為了驗(yàn)證跨單元調(diào)度及其車輛路徑集成優(yōu)化的效果，在具有4個(gè)制造單元、9個(gè)零件、2輛運(yùn)輸車輛的單元制造系統(tǒng)中進(jìn)行驗(yàn)證。單元制造系統(tǒng)中所有零件的加工單元、各工序候選機(jī)器及其加工時(shí)間和加工成本如表1所示，單元間距離以及車場與單元間距離如表2所示，制造單元中機(jī)器分布如表3所示。根據(jù)企業(yè)調(diào)研數(shù)據(jù)的實(shí)際情況與全國工資標(biāo)準(zhǔn)，設(shè)置異常件裝卸時(shí)間ts=8 min，車輛平均行駛速度v=30 km/h，車輛最大負(fù)載Qmax為3件，車輛單位距離運(yùn)輸成本ct=2元/km，司機(jī)單位時(shí)間的工資cd=0.33元/min。

表1 零件加工信息

表2 單元間的距離以及車場與單元間的距離

表3 機(jī)器與單元的關(guān)系及單元中機(jī)器分布

由圖6可知：車輛1在單元1先裝載異常件9和異常件6，再等待16 min后，裝載異常件2一同運(yùn)往單元3，于單元3依次卸載異常件9、異常件6和異常件2，再等待18 min后，裝載異常件9并運(yùn)往單元2，卸載異常件9后返回車場，導(dǎo)致圖5中異常件9工序2開工時(shí)間與工序1完工時(shí)間間隔130 min，工序3完工時(shí)間與工序4開工時(shí)間間隔81 min。異常件的異常工序在跨單元移動(dòng)后其最早開工時(shí)間受到其緊前工序的完工時(shí)間以及車輛運(yùn)輸和等待時(shí)間限制，因此異常工序開工時(shí)間與其緊前工序完工時(shí)間間隔較長。

圖5 集成優(yōu)化Pareto解1甘特圖Fig.5 Gantt chart of solution 1 from Pareto set under integrated optimization

圖6 集成優(yōu)化Pareto解集解1車輛路徑及負(fù)載變化示意圖Fig.6 Schematic diagram of transportation routes and loads of vehicles of solution 1 from Pareto set under integrated optimization

3.2 不同車輛運(yùn)輸策略結(jié)果比較

為驗(yàn)證提出的跨單元調(diào)度及其車輛路徑集成優(yōu)化的效果，對上述案例在相同條件下，采用常見運(yùn)輸策略[2]和運(yùn)輸車輛共享策略[7]求解，結(jié)果如表5和表6所示。

分別比較表4、表5、表6可知，提出的集成優(yōu)化方法無論完工時(shí)間或總成本均明顯優(yōu)于常見運(yùn)輸策略和車輛共享策略的結(jié)果，其中最大完工時(shí)間分別可縮短48.4%～53.3%和18.0%～47.7%、總成本可降低22.9%～29.7%和14.9%～17.9%，其中運(yùn)輸成本降低了38.4%～47.4%和27.7%～30.6%。因此，集成優(yōu)化方法可有效縮短跨單元調(diào)度優(yōu)化問題的最大完工時(shí)間和減少運(yùn)輸成本。

表4 集成優(yōu)化的Pareto解集

表5 常見運(yùn)輸策略的Pareto解集

表6 運(yùn)輸車輛共享策略的Pareto解集

為了進(jìn)一步說明集成優(yōu)化的效果，表7和表8分別對比了集成優(yōu)化策略與其他兩種運(yùn)輸策略Pareto解1中的異常件特殊工序的等待時(shí)間和車輛行駛數(shù)據(jù)。由表7結(jié)合圖5可知，集成優(yōu)化允許車輛1同時(shí)運(yùn)輸3個(gè)異常件，將異常件6特殊工序1的等待時(shí)間由51 min和171 min降低到了3 min，異常件2特殊工序4的等待時(shí)間從0和181 min降低到了0，其他異常件特殊工序的等待時(shí)間均有不同程度的縮短；由表8可知，相對于其他兩種運(yùn)輸策略，集成優(yōu)化通過對車輛路徑優(yōu)化，將車輛總行駛距離降低了41.2%和32.5%，車輛總的使用時(shí)間縮短了29.6%和17.9%，從而降低了異常件的跨單元運(yùn)輸成本。常見運(yùn)輸策略中，車輛等待時(shí)間是由車輛所屬單元沒有運(yùn)輸任務(wù)所導(dǎo)致的車輛閑置，閑置車輛無法運(yùn)輸其他單元需要運(yùn)輸?shù)漠惓＜菍囕v運(yùn)輸能力的浪費(fèi)，運(yùn)輸車輛共享策略中車輛可運(yùn)輸任一單元的異常件，因此不存在此類浪費(fèi)，其等待時(shí)間是當(dāng)前沒有運(yùn)輸任務(wù)造成的，而集成優(yōu)化中車輛等待時(shí)間是由運(yùn)輸計(jì)劃導(dǎo)致的，是為保證完工時(shí)間和總成本最小而做出的決策，雖然其等待時(shí)間大于車輛共享策略的等待時(shí)間，但是保證了完工時(shí)間和總成本的優(yōu)化。

表7 不同運(yùn)輸策略中零件等待時(shí)間(表4～表6中Pareto解1)

表8 不同運(yùn)輸策略中的車輛數(shù)據(jù)對比(表4～表6中Pareto解1)

集成優(yōu)化方法以及不同運(yùn)輸策略下，異常件數(shù)量不會(huì)改變，因此裝卸異常件的時(shí)間是相同的。集成優(yōu)化允許車輛裝載多個(gè)異常件，更加充分地利用了車輛的運(yùn)輸能力，允許運(yùn)輸車輛為任一單元服務(wù)，同時(shí)通過車輛路徑優(yōu)化，減少了運(yùn)輸次數(shù)，縮短了車輛行駛距離和使用時(shí)間，降低了零件等待時(shí)間，從而減少了完工時(shí)間和總成本。

4 結(jié)語

為了提高車輛裝載效率、縮短完工時(shí)間與降低成本，提出跨單元調(diào)度及其車輛路徑集成優(yōu)化模型，設(shè)計(jì)了基于工序、單元、機(jī)器、車輛選擇以及車輛路徑的五段式編碼；設(shè)計(jì)了基于分解的多目標(biāo)進(jìn)化算法，對不可行解提出了一種基于二叉樹的車輛路徑調(diào)整方法以及車輛容量約束調(diào)整方法，保證了車輛路徑編碼滿足零件工藝路線約束以及車輛容量約束。通過算例，將集成優(yōu)化結(jié)果與常見運(yùn)輸策略和車輛共享策略進(jìn)行對比，驗(yàn)證了集成優(yōu)化模型在縮短完工時(shí)間上和降低總成本上的優(yōu)勢。

由于跨單元調(diào)度及其車輛路徑集成優(yōu)化問題復(fù)雜度高，求解難度大，以及目前算法效率的不足，對求解實(shí)際生產(chǎn)中大規(guī)模問題是一個(gè)巨大挑戰(zhàn)，下一步工作中將對算法進(jìn)行改進(jìn)，以求解大規(guī)模跨單元調(diào)度及其車輛路徑集成優(yōu)化問題。