混合分布估計(jì)算法求解考慮同步性和準(zhǔn)時(shí)性的三階段裝配集成調(diào)度問題

鄧 超 胡 蓉 錢 斌

(1.昆明理工大學(xué)機(jī)電工程學(xué)院,云南昆明 650500;2.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南昆明 650500)

1 引言

裝配制造業(yè)的生產(chǎn)過程包含從加工到裝配形成最終產(chǎn)品的整個(gè)流程,將生產(chǎn)過程中各個(gè)階段集成可有效地從整體層面進(jìn)行資源配置,是裝配制造業(yè)生產(chǎn)過程優(yōu)化調(diào)度中非常重要的環(huán)節(jié).因此,研究面向裝配制造業(yè)的集成調(diào)度具有重要意義.目前,對裝配制造企業(yè)車間集成調(diào)度研究主要針對含加工、裝配的兩階段裝配集成調(diào)度問題(two-stage assembly integrated scheduling problem,2sAISP)[1–2]和含加工、運(yùn)輸、裝配的三階段裝配集成調(diào)度問題(three-stage assembly integrated scheduling problem,3sAISP).3sAISP在2sAISP的加工和裝配階段之間進(jìn)一步增加運(yùn)輸階段,但現(xiàn)有大量研究均假設(shè)運(yùn)輸階段各工件的運(yùn)輸時(shí)間為常數(shù)[3–5],即運(yùn)輸車輛數(shù)量無限或載重?zé)o限,這與現(xiàn)實(shí)問題存在較大差距.因此,文獻(xiàn)[6]進(jìn)一步考慮運(yùn)輸車輛數(shù)量和車載重量有限會(huì)導(dǎo)致工件需按批量分別運(yùn)輸?shù)膶?shí)際情況,研究帶工件批量運(yùn)輸?shù)?sAISP.該問題研究極為有限且更符合實(shí)際,故對其及相關(guān)擴(kuò)展問題開展研究具有重要的理論和實(shí)際意義.

同步性和準(zhǔn)時(shí)性是企業(yè)物流中兩個(gè)關(guān)鍵的因素[7].同步性可有效利用企業(yè)資源,建立與市場需求同步、連續(xù)的產(chǎn)品流.同步生產(chǎn)能夠更好地滿足生產(chǎn)中產(chǎn)品的多樣性需求,有利于減少在制品庫存[8].準(zhǔn)時(shí)性是在客戶需要的時(shí)間和地點(diǎn),生產(chǎn)所需要數(shù)量和質(zhì)量的產(chǎn)品和服務(wù).裝配制造業(yè)常將生產(chǎn)和交貨整合在一起做出運(yùn)營決策以提高準(zhǔn)時(shí)性[9].大量文獻(xiàn)把交貨期(due date)作為衡量準(zhǔn)時(shí)性的目標(biāo)進(jìn)行研究,使生產(chǎn)任務(wù)盡可能在各產(chǎn)品設(shè)定的交貨期完成,從而提升客戶滿意度[10–12].然而,與準(zhǔn)時(shí)性相比,同步性在現(xiàn)實(shí)生產(chǎn)中大都被忽略,結(jié)果導(dǎo)致生產(chǎn)資源浪費(fèi)及成品(在制品)庫存增加,同時(shí)也影響訂單交付的準(zhǔn)時(shí)性.因此,生產(chǎn)中考慮同步性具有重要現(xiàn)實(shí)意義.

目前,在生產(chǎn)調(diào)度中同步性的研究已開始得到重視.Li等[13]研究了不含加工階段的裝配–運(yùn)輸同步問題,以最小化供應(yīng)鏈總成本為目標(biāo),建立整數(shù)線性規(guī)劃模型求解問題.Zandieh等[14]研究了不含裝配階段的加工–運(yùn)輸同步問題,以最小化供應(yīng)鏈總成本為目標(biāo),建立數(shù)學(xué)規(guī)劃模型對問題進(jìn)行求解.Tang等[15]研究了和文獻(xiàn)[14]同樣的問題,以最小化運(yùn)營成本為目標(biāo),構(gòu)建了數(shù)學(xué)規(guī)劃模型,并根據(jù)問題性質(zhì)提出了基于拉格朗日松弛分解的兩層決策框架,最后用啟發(fā)式方法和遺傳算法對問題進(jìn)行求解.Chen等[16]研究了不含運(yùn)輸階段的加工–裝配同步問題,以最小化生產(chǎn)同步性和交貨準(zhǔn)時(shí)性加權(quán)和為目標(biāo)函數(shù),構(gòu)建了數(shù)學(xué)規(guī)劃模型,并用改進(jìn)的遺傳算法對問題進(jìn)行求解.通過以上文獻(xiàn)調(diào)研可知,考慮加工–運(yùn)輸–裝配三階段的同步問題目前尚無人進(jìn)行研究.然而,在實(shí)際生產(chǎn)過程中,加工–運(yùn)輸–裝配同步性對產(chǎn)品生產(chǎn)連續(xù)性、在制品實(shí)際庫存及交貨準(zhǔn)時(shí)性有很大影響.通過提升各階段的同步性,可提高裝配制造企業(yè)生產(chǎn)效率,增強(qiáng)企業(yè)市場競爭力.因此,本文研究以加工–運(yùn)輸–裝配同步性和交貨準(zhǔn)時(shí)性加權(quán)和為優(yōu)化目標(biāo)的三階段裝配集成調(diào)度問題(3sAISP with synchronization and punctuality,3sAISP_SP)的建模與求解,具有較大工程意義.此外,在計(jì)算復(fù)雜度上,2sAISP已被證明為具有非確定多項(xiàng)式難(non-deterministic polynomial hard,NP?hard)的屬性[1],該問題可歸約為3sAISP,而3sAISP又可歸約為3sAISP_SP,故3sAISP_SP亦為NP–hard.這表明研究3sAISP_SP也具有重要理論意義.

在已有文獻(xiàn)中調(diào)度問題模型主要包括數(shù)學(xué)規(guī)劃模型和排列模型.數(shù)學(xué)規(guī)劃模型采用運(yùn)籌學(xué)方法求解,譬如很多文獻(xiàn)中采用基于分支定界、分支定價(jià)等方法的商用求解器GUROBI 或CPLEX求解.由于這些運(yùn)籌學(xué)方法遍歷或部分遍歷解空間,故較短時(shí)間內(nèi)(即幾分鐘內(nèi))只能求解小規(guī)模問題.排列模型一般采用智能優(yōu)化方法求解.排列模型將問題解空間壓縮為一個(gè)極度扁平的空間,使得優(yōu)化目標(biāo)函數(shù)值的范圍遠(yuǎn)小于問題解或排列的數(shù)量,大量不同解對應(yīng)相同目標(biāo)函數(shù)值.同時(shí),智能優(yōu)化算法是在帶保優(yōu)的隨機(jī)搜索基礎(chǔ)上加入特定的進(jìn)化尋優(yōu)機(jī)制.這使得智能優(yōu)化算法在短時(shí)間內(nèi)只搜索排列模型解空間的很小區(qū)域,卻能在目標(biāo)函數(shù)值上搜索到明顯多于運(yùn)籌學(xué)方法的較好區(qū)域,從而可有效求解不同規(guī)模問題.這是智能優(yōu)化調(diào)度算法近年快速發(fā)展的主要原因.因此,本文設(shè)計(jì)智能優(yōu)化算法求解不同規(guī)模的3sAISP_SP(對應(yīng)排列模型),同時(shí)采用基于運(yùn)籌學(xué)方法的GUROBI 獲取小規(guī)模3sAISP_SP(對應(yīng)數(shù)學(xué)規(guī)劃模型)的最優(yōu)解,以驗(yàn)證所提算法的近似最優(yōu)性.

分布估計(jì)算法(estimation of distribution algorithm,EDA)是一種基于統(tǒng)計(jì)學(xué)的新興進(jìn)化算法,以統(tǒng)計(jì)的方式對種群中的優(yōu)質(zhì)個(gè)體進(jìn)行學(xué)習(xí)并構(gòu)造概率模型,然后對概率模型進(jìn)行采樣產(chǎn)生新種群,從而引導(dǎo)算法的搜索方向,具有較好的全局搜索能力.EDA在生產(chǎn)調(diào)度領(lǐng)域已開展較多研究.李子輝等[17]考慮3sAISP問題,以平均完成時(shí)間和延遲時(shí)間加權(quán)和為優(yōu)化目標(biāo),提出一種自適應(yīng)EDA求解.該算法通過設(shè)計(jì)基于信息熵的概率分布模型自適應(yīng)更新機(jī)制和保留優(yōu)良模式的新種群采樣生成方法來增強(qiáng)全局搜索能力,同時(shí)提出基于插入(insert)操作的鄰域搜索來增強(qiáng)算法的局部搜索能力.Qian等[18]考慮可重入流水線調(diào)度問題,以最小化最大完工時(shí)間(makespan)為優(yōu)化目標(biāo),提出基于COPULA函數(shù)的EDA求解.該算法利用各變量的邊緣分布和COPULA函數(shù)構(gòu)造變量聯(lián)合分布概率模型,同時(shí)提出基于關(guān)鍵路徑的塊結(jié)構(gòu)性質(zhì),并基于該性質(zhì)構(gòu)造局部搜索.Wang等[19]考慮柔性制造系統(tǒng)的調(diào)度問題,以makespan為優(yōu)化目標(biāo),提出了一種混合EDA求解.該算法提出變量鄰域搜索的方式產(chǎn)生后代個(gè)體,從而在其鄰域中獲得更好的解以提高算法性能.Li等[20]考慮帶序相關(guān)設(shè)置時(shí)間的多目標(biāo)作業(yè)車間調(diào)度問題,以makespan和總設(shè)置費(fèi)用為優(yōu)化目標(biāo),提出遺傳算法和EDA融合的算法求解.該算法構(gòu)建新穎的雙種群協(xié)同進(jìn)化框架,有利于引導(dǎo)搜索發(fā)現(xiàn)優(yōu)質(zhì)解區(qū)域.雖然EDA已在多種生產(chǎn)調(diào)度問題上取得成功應(yīng)用,但針對3sAISP_SP的研究處于空白狀態(tài).

本文研究以生產(chǎn)–運(yùn)輸–裝配同步性和交貨準(zhǔn)時(shí)性的加權(quán)和為優(yōu)化目標(biāo)的三階段裝配集成調(diào)度問題(3sAISP_SP),并基于問題特點(diǎn)設(shè)計(jì)混合分布估計(jì)算法(hybrid estimation of distribution algorithm,HEDA)進(jìn)行求解.首先,分別建立3sAISP_SP的數(shù)學(xué)規(guī)劃模型和排列模型.其次,在對問題模型特點(diǎn)分析的基礎(chǔ)上,提出求解3sAISP_SP 的HEDA.在HEDA中,設(shè)計(jì)合理的編碼和解碼規(guī)則,同時(shí)利用基于概率模型的全局搜索以發(fā)現(xiàn)問題解空間存在優(yōu)質(zhì)解的區(qū)域.為進(jìn)一步提高算法性能,設(shè)計(jì)3種局部搜索策略對優(yōu)質(zhì)解區(qū)域進(jìn)行細(xì)致搜索.然后,在小規(guī)模問題下,將HEDA得到的較優(yōu)解與GUROBI得到的最優(yōu)解進(jìn)行比較,驗(yàn)證HEDA的求解結(jié)果接近最優(yōu)解;在較大規(guī)模問題下,將HEDA與其他有效智能優(yōu)化算法進(jìn)行比較,驗(yàn)證HEDA的求解性能.最后,討論裝配同步性和交貨準(zhǔn)時(shí)性的合理權(quán)重組合及裝配同步性對半成品庫存的影響.

2 問題數(shù)學(xué)模型

2.1 問題總體描述

設(shè)產(chǎn)品集為P,z∈P,P={1,2,…,HP};車輛集為T,t∈T,T={1,2,…,HTR};零件集為Q,零件總數(shù)為q,j∈Q,Q={1,2,…,q},組成第z個(gè)產(chǎn)品的工件數(shù)為Pz;工序集為O,工序總數(shù)為HO,i∈O,O={1,2,…,HO};加工階段設(shè)備集為M.加工階段設(shè)備數(shù)為m1臺,M={1,2,…,m1},裝配階段組裝設(shè)備數(shù)為1.每種產(chǎn)品由多個(gè)工件組成,每個(gè)工件的不同工序需要按先后順序在加工階段m1臺滿足加工約束的設(shè)備上加工,完成加工后由運(yùn)輸階段HTR輛車在車載額定載重VT限制條件下運(yùn)輸?shù)窖b配階段等待組裝.車輛可來回w趟,其中w1.t-tran為車輛t的運(yùn)輸時(shí)間.各產(chǎn)品對應(yīng)的工件按加工順序依次經(jīng)過3個(gè)階段進(jìn)行處理;加工階段的任一加工設(shè)備在同一時(shí)刻只能加工一種工件,不同零件帶釋放時(shí)間;裝配階段的組裝設(shè)備在同一時(shí)刻只能組裝同一種產(chǎn)品,不同產(chǎn)品間設(shè)置時(shí)間為零.

完成的每個(gè)產(chǎn)品都有其單獨(dú)的交貨截止日期Dz,任何早于或晚于Dz完成的產(chǎn)品將受到提前或遲到的處罰.此外,受車輛額定載荷及運(yùn)輸效率限制,工件在加工階段完工之后并非立刻被車輛運(yùn)輸走,若不夠裝滿一輛車或者需要等待車輛往返運(yùn)輸,完工工件需要放入中轉(zhuǎn)區(qū)域等待,從而產(chǎn)生了完工工件庫存.由此可見,在滿足裝配同步性和運(yùn)輸準(zhǔn)時(shí)性的同時(shí)使產(chǎn)品在恰當(dāng)?shù)臅r(shí)間完成生產(chǎn)以滿足交貨期.3sAISP_SP模型圖如圖1所示.

圖1 3sAISP_SP模型圖Fig.1 The model of 3sAISP_SP

2.2 優(yōu)化目標(biāo)加權(quán)和函數(shù)

以同步性為目標(biāo)的生產(chǎn)調(diào)度問題通常運(yùn)用工件完成時(shí)間與基準(zhǔn)之間的平均差異來衡量[21].然而,平均差異衡量方法在某些情形下容易發(fā)生補(bǔ)償效應(yīng)而不能客觀反映同步性.因此,本文選用最長裝配等待時(shí)間WT來衡量同步性,即屬于同一產(chǎn)品的工件最早到達(dá)裝配中心時(shí)間與最晚到達(dá)裝配中心時(shí)間之間的間隔,并提出平均最長等待時(shí)間指標(biāo)fs來衡量裝配同步性,即

以滿足準(zhǔn)時(shí)性為目標(biāo)的調(diào)度問題通常以基于時(shí)間和基于成本的這兩種指標(biāo)來衡量.基于成本的方式是通過乘以懲罰系數(shù)得出提前或遲到時(shí)間的懲罰成本,但受到一些隱含的因素影響較難準(zhǔn)確確定懲罰系數(shù)[22].因此,本文采用平均提前和遲到時(shí)間作為交貨準(zhǔn)時(shí)性目標(biāo)函數(shù)fp,即其中CA表示產(chǎn)品的三階段總完工時(shí)間.

將兩個(gè)目標(biāo)通過一定的權(quán)重合并成為單個(gè)目標(biāo),即f=ωsfs+ωpfp.其中,同步性的權(quán)重為ωs,準(zhǔn)時(shí)性的權(quán)重為ωp,且ωs+ωp=1.

2.3 問題模型

2.3.1 3sAISP_SP數(shù)學(xué)規(guī)劃模型

1)關(guān)于本節(jié)所涉及的數(shù)學(xué)符號及定義如下:

參數(shù):

Qj:工件j的工序總數(shù);

Oi,j:工件j的第i個(gè)工序;

Mij:對Oi,j可加工的機(jī)器;

tw:車輛t來回運(yùn)輸?shù)奶藬?shù);

A:一個(gè)很大的數(shù);

Pijk:Oi,j在機(jī)器k上的加工時(shí)間;

Rjk:工件j首次到達(dá)第k臺加工設(shè)備的時(shí)間,即釋放時(shí)間;

Vj:工件j的載荷;

Az:產(chǎn)品z的裝配時(shí)間.

中間變量:

SPijk:Oi,j在機(jī)器k上的開始加工時(shí)間;

CPij:Oi,j的完工時(shí)間;

CPj:工件j在加工階段的完工時(shí)間;

STjtw:工件j在車輛t第w趟的開始運(yùn)輸時(shí)間;

STtw:車輛t第w趟的開始運(yùn)輸時(shí)間;

CTtw:車輛t第w趟的結(jié)束運(yùn)輸時(shí)間;

CTj:工件j的結(jié)束運(yùn)輸時(shí)間;

SAz:產(chǎn)品z開始裝配時(shí)間;

CAz:產(chǎn)品z裝配完工時(shí)間.

布爾變量:

2)數(shù)學(xué)規(guī)劃模型:

式(1)為目標(biāo)函數(shù);約束(2)?(6)為工件首次加工有釋放時(shí)間;約束(7)為工件的前一操作完成后才能進(jìn)行后一個(gè)操作;約束(8)為工件在機(jī)器上的完工時(shí)間;約束(9)為工件的每個(gè)操作可從可選加工機(jī)器集中選出一臺機(jī)器進(jìn)行加工;約束(10)?(11)為每臺可加工機(jī)器在同一時(shí)間只能進(jìn)行一次操作;約束(12)為工件加工階段完工時(shí)間;約束(14)?(15)為每個(gè)工件只能被車輛運(yùn)送一次;約束(16)為裝入每輛車的工件總載荷不超過車輛額定載荷;約束(17)?(18)為工件按工件序列分配給運(yùn)輸車輛且只分配一次;約束(19)為工件開始運(yùn)輸時(shí)間;約束(20)為工件完工運(yùn)輸時(shí)間受裝入該車輛中工件的完工時(shí)間限制;約束(21)為工件開始運(yùn)輸時(shí)間受裝入該車輛前一趟運(yùn)輸開始時(shí)間限制;約束(22)為運(yùn)輸結(jié)束時(shí)間;約束(23)?(24)為產(chǎn)品按順序依次安排到裝配機(jī)器上進(jìn)行裝配;約束(25)為屬于同一產(chǎn)品的所有工件到達(dá)后才能進(jìn)行裝配;約束(26)為裝配機(jī)器在同一時(shí)間只能裝配一個(gè)產(chǎn)品.

2.3.2 3sAISP_SP排列模型

1)加工階段:帶釋放時(shí)間的多工序異構(gòu)并行機(jī)調(diào)度問題(HPMP_RT).為所有工件的工序在加工階段的排列.加工設(shè)備k上加工工序的數(shù)量為Hk,πk=為工件的工序在加工階段加工設(shè)備k上的排列,為πk中第i個(gè)位置的工件的工序.的加工時(shí)間,為πk中第i個(gè)位置的工件首次到達(dá)第k臺加工設(shè)備的時(shí)間,即釋放時(shí)間.前一次加工工序的設(shè)備號,前一個(gè)工序在設(shè)備號為上的排列表示為若工件首次加工,則在第k臺機(jī)器上加工時(shí)該臺機(jī)器上前一次加工的工件工序,工件工序在排列中的位置記為若加工的機(jī)器為首次加工工件,則的完成時(shí)間計(jì)算如下:

2)運(yùn)輸階段:帶車輛載重約束的多車輛單點(diǎn)配送問題.wt為表示車輛t來回運(yùn)輸?shù)奶藬?shù),wt1.Vt為車輛t的額定載荷(定值).t_tran為表示車輛的運(yùn)輸時(shí)間(定值).為所有工件在運(yùn)輸階段的排列,為πTR中第j個(gè)位置的工件.為πTR中第j個(gè)位置的工件加工階段的完工時(shí)間.為πTR中第j個(gè)位置的工件的重量.為πTR中第j個(gè)位置的工件在第t臺車輛的開始運(yùn)輸時(shí)間.為運(yùn)輸階段第wt趟裝載在車輛t里πTR中第j個(gè)位置的工件的完工時(shí)間,πTR中第j個(gè)位置的工件在運(yùn)輸階段的運(yùn)輸完成時(shí)間計(jì)算如下:

4)優(yōu)化目標(biāo).優(yōu)化目標(biāo)為在所有產(chǎn)品所組成的工件從加工、運(yùn)輸?shù)窖b配三階段順序的集合Π中找到一個(gè)最優(yōu)排序π?=(πK,πTR,πP),使得準(zhǔn)時(shí)性fp與同步性fs的加權(quán)和f最小.其中:為產(chǎn)品的交貨截止日期;為產(chǎn)品的交貨截止日期與實(shí)際完成時(shí)間的差值;為屬于同一產(chǎn)品的工件最早到達(dá)裝配中心時(shí)間與最遲到達(dá)裝配中心時(shí)間之間的間隔.

2.3.3 兩類模型的特點(diǎn)

與絕大部分組合優(yōu)化問題一樣,3sAISP_SP的常用模型包括數(shù)學(xué)規(guī)劃模型和排列模型.由于該問題為NP?hard問題,不存在獲取最優(yōu)解的多項(xiàng)式時(shí)間算法.

從第2.3.1節(jié)可知,3sAISP_SP 的數(shù)學(xué)規(guī)劃模型由目標(biāo)函數(shù)(即式(1))和一系列顯式不等式和等式約束(即式(2)至式(29))組成,屬于0?1混合整數(shù)規(guī)劃問題,具有非凸特性.該類模型主要采用運(yùn)籌學(xué)方法求解.數(shù)學(xué)規(guī)劃模型包含大量不等式或等式約束.譬如,對于50個(gè)工件、5道工序、5臺機(jī)器的中等規(guī)模問題,僅式(6)就含近1250個(gè)不等式約束.這些約束式可較全面刻畫問題結(jié)構(gòu),但其龐大的數(shù)量明顯增加了算法確定可行解區(qū)域和在該區(qū)域發(fā)現(xiàn)最優(yōu)解或近似最優(yōu)解的難度,使得算法求解質(zhì)量取決于具體問題的復(fù)雜度以及算法設(shè)計(jì)者對該問題結(jié)構(gòu)(特別是幾何結(jié)構(gòu))的理解程度.對于中大規(guī)模問題,算法(如分支定界法、分支切割法)要在較短時(shí)間獲取問題滿意解的難度大.

從第2.3.2節(jié)可知,該問題的排列模型(即式(30)至式(47))由各工序加工完工時(shí)間、工件運(yùn)輸完成時(shí)間、產(chǎn)品裝配完成時(shí)間的計(jì)算公式組成,約束隱式包含在這些公式和解的編碼、解碼(見第3.2.1節(jié))中.該類模型多采用智能優(yōu)化算法求解.排列模型的約束不顯式出現(xiàn),容易設(shè)計(jì)有效的編碼、解碼和搜索操作來避免違反約束,使得算法搜索集中在可行解區(qū)域進(jìn)行.同時(shí),該類模型把問題解空間壓縮為一個(gè)極為扁平、緊湊的空間,其目標(biāo)值變化范圍遠(yuǎn)小于解空間規(guī)模,大量不同的解具有相同目標(biāo)值.因此,采用排序模型可使算法僅需搜索解空間中極小可行區(qū)域就能覆蓋目標(biāo)值較大區(qū)域,有利于算法快速獲取較大規(guī)模問題的滿意解.

綜上,為使算法能對不同規(guī)模的3sAISP_SP進(jìn)行有效求解,本文采用問題的排列模型,并設(shè)計(jì)智能優(yōu)化算法HEDA求解.

2.4 問題示例

本節(jié)通過一個(gè)例子來說明3sAISP_SP.考慮一個(gè)三階段裝配集成調(diào)度問題,第1階段為3臺異構(gòu)并行機(jī),第2階段為2輛具有相同載重的運(yùn)輸車輛,第3階段為1臺裝配機(jī)器,需要加工裝配完成3個(gè)產(chǎn)品.產(chǎn)品構(gòu)成如圖2所示,3個(gè)產(chǎn)品由多個(gè)工件裝配而成,每個(gè)工件具有多個(gè)工序,每個(gè)工序可在多臺機(jī)器上加工.產(chǎn)品各階段數(shù)據(jù)見表1,車輛運(yùn)輸時(shí)間為t_tran=200,權(quán)重為ωs=ωp=0.5.該示例形成的甘特圖如圖3所示.

在圖3中:V1?1表示第1輛運(yùn)輸車輛的第1趟.該車輛在滿足載荷的前提下運(yùn)送屬于P1,P2產(chǎn)品的J5,J1,J4三個(gè)工件,且CT51=CT11=CT41=614;V2?1車輛運(yùn)送屬于P1,P3產(chǎn)品的J2,J3,J9工件,CT22=CT32=CT92=692,屬于P1的工件全部到達(dá)開始裝配,則WT1=692?614=78.此時(shí)兩輛運(yùn)輸車輛均已在途,剩余加工完的工件需要等待車輛往返方能被運(yùn)送,故V1?2車輛運(yùn)送屬于P2,P3產(chǎn)品的J8,J7,J6三個(gè)工件,CT81=CT71=CT61=1014,則

圖2 示例產(chǎn)品構(gòu)成Fig.2 An example of products composition

表1 產(chǎn)品各階段數(shù)據(jù)Table 1 Data of each stage of the product

圖3 3sAISP_SP的甘特圖Fig.3 A Gantt chart of 3sAISP_SP

3 求解3sAISP_SP的HEDA算法設(shè)計(jì)

3.1 3sAISP_SP的特點(diǎn)分析

1)整體性和系統(tǒng)性.3sAISP_SP并非為3個(gè)階段子問題的簡單疊加(見圖3),前一個(gè)階段的調(diào)度結(jié)果直接影響后一個(gè)階段的優(yōu)化.因此,設(shè)計(jì)求解算法時(shí)應(yīng)從整體優(yōu)化出發(fā).

2)優(yōu)化目標(biāo)與各階段之間的聯(lián)系.優(yōu)化目標(biāo)中的同步性和準(zhǔn)時(shí)性均用時(shí)間來度量.同步性貫穿于各個(gè)階段并影響準(zhǔn)時(shí)性,前一階段同步性是后一階段同步性的基礎(chǔ);準(zhǔn)時(shí)性由裝配階段產(chǎn)品完工時(shí)間最終確定.

3)問題解空間復(fù)雜.3sAISP_SP是多階段耦合的調(diào)度問題,其問題解空間非常復(fù)雜,故需分析和利用問題特點(diǎn)來合理縮小搜索空間.

結(jié)合1)和2)的分析提出以下3條規(guī)則:

規(guī)則1屬于同一產(chǎn)品的工件在加工階段分配相同的優(yōu)先級有利于提高同步性.

規(guī)則2屬于同一產(chǎn)品的工件在滿足車輛裝載約束下盡量放入同一輛車有利于提高同步性.

規(guī)則3交貨期越早的產(chǎn)品盡早裝配以提高交貨的準(zhǔn)時(shí)性.

通過3)的分析可知,設(shè)計(jì)算法時(shí)要盡量減小搜索范圍,以提高搜索效率,同時(shí)需合理構(gòu)造搜索操作,以實(shí)現(xiàn)對復(fù)雜解空間的有效搜索.

綜上,為提高算法求解3sAISP_SP的效率,本文的HEDA不采用常規(guī)對整個(gè)問題的編碼和解碼,而采用分階段的編碼和解碼,并在此基礎(chǔ)上只對加工階段執(zhí)行基于智能優(yōu)化的搜索以確定對應(yīng)子問題的解,而對運(yùn)輸和裝配階段采用結(jié)合規(guī)則的解碼直接確定對應(yīng)子問題的解.

3.2 求解3sAISP_SP的HEDA算法設(shè)計(jì)

本文設(shè)計(jì)的HEDA只對加工階段的子問題(即帶釋放時(shí)間的多工序異構(gòu)并行機(jī)調(diào)度問題)解空間進(jìn)行搜索,在此基礎(chǔ)上在運(yùn)輸和裝配階段依據(jù)問題性質(zhì)設(shè)計(jì)相關(guān)策略得出優(yōu)化目標(biāo)函數(shù)值.具體來說,HEDA求解3sAISP_SP包含以下環(huán)節(jié):1)根據(jù)加工階段的編碼生成相應(yīng)的種群,然后利用所設(shè)計(jì)的算法操作來執(zhí)行進(jìn)化并實(shí)現(xiàn)搜索;2)在計(jì)算個(gè)體或解對應(yīng)的優(yōu)化目標(biāo)值時(shí),首先根據(jù)解中工件具體排列,利用加工階段的解碼計(jì)算各工件完工時(shí)間;然后設(shè)計(jì)相關(guān)操作分別對運(yùn)輸及裝配階段進(jìn)行編碼和解碼;最后依據(jù)相應(yīng)權(quán)重獲得整個(gè)問題的優(yōu)化目標(biāo)值.

3.2.1 編碼及解碼

1)加工階段編碼及解碼.

編碼:第1部分為加工階段基于工序的排列,其長度是由產(chǎn)品層?工件層?工序?qū)哟_定,即產(chǎn)品對應(yīng)工件集合Pz及工件對應(yīng)工序集合Qzj確定,z∈P,j∈Q.如第2.4節(jié)示例所示Pz={3,3,3}表示有3個(gè)產(chǎn)品,每個(gè)產(chǎn)品都由3個(gè)工件組成,總工件數(shù)為3+3+3=9,表示產(chǎn)品P1對應(yīng)3個(gè)工件的工序數(shù)為[2,1,3],產(chǎn)品P2對應(yīng)3個(gè)工件的工序數(shù)為[3,3,3],產(chǎn)品P3對應(yīng)3個(gè)工件的工序數(shù)為[2,3,2],第1段編碼可表示為{1,7,4,6,8,9,4,5,2,8,9,3,6,5,3,7,5,3,4,6,1,8}.

解碼:加工階段是三階段的開始也是核心,解的質(zhì)量直接影響后兩個(gè)階段.因此,本文設(shè)計(jì)最早完工時(shí)間(earliest completion time,ECT)規(guī)則[17]與插空相結(jié)合的形式進(jìn)行解碼,確定各個(gè)工序的開始加工時(shí)間并完成機(jī)器分配.

2)運(yùn)輸階段編碼及解碼.

編碼:第2段編碼為運(yùn)輸階段基于工件的排序,按照工件在加工階段完工時(shí)間非降序得到對應(yīng)編碼πTR.如工件在加工階段完工時(shí)間分別為

則工件排序?yàn)閧6,3,1,9,8,2,4,5,7}(見圖4).

圖4 編碼方式Fig.4 Encoding

解碼:πPD為產(chǎn)品按交貨期非降序得到的排列,為πPD中第z個(gè)位置的產(chǎn)品;V[t]為第t輛車當(dāng)前載重.根據(jù)規(guī)則2?3對運(yùn)輸階段進(jìn)行解碼,具體步驟如下:

Step 1從工件排列πTR中從左到右依次選出屬于產(chǎn)品的工件

Step 2將選出的工件在滿足VT的條件下依次裝入車輛t,當(dāng)滿足>VT則將工件j放入車輛t+1中,并更新和待運(yùn)輸工件集合,轉(zhuǎn)入Step 3.

Step 3檢驗(yàn)待運(yùn)輸工件集合中是否存在工件滿足若滿足則將工件放入車輛t中,更新V[t],直至更新待運(yùn)輸工件集合,t=t+1,z=z+1.

Step 4轉(zhuǎn)入Step 1,直至待運(yùn)輸工件集合為空.

3)裝配階段編碼及解碼.

編碼:第3段編碼為裝配階段基于產(chǎn)品的排序,按照組成產(chǎn)品所有工件中最晚到達(dá)裝配階段的時(shí)間非降序排列得到對應(yīng)產(chǎn)品編碼πP.如組成產(chǎn)品P1,P2,P3最后一個(gè)工件到達(dá)裝配車間的時(shí)間分別為21,34,17,則產(chǎn)品排序?yàn)閧3,1,2}(見圖4).

解碼:考慮到交貨準(zhǔn)時(shí)性,按照最小交貨時(shí)間優(yōu)先規(guī)則進(jìn)行解碼,從而確定各產(chǎn)品完工時(shí)間.

3.2.2 權(quán)重的設(shè)置

如果決策者依據(jù)偏好給出權(quán)重組合,則將問題搜索方向固定在一維目標(biāo)空間中.如果沒有給出權(quán)重偏好,則將對權(quán)重進(jìn)行調(diào)整以確定最佳權(quán)重組合.本文采用一種線性調(diào)整權(quán)重方式來實(shí)現(xiàn)[16].n為運(yùn)行的總次數(shù),為當(dāng)前運(yùn)行數(shù),1nF;ωs(n),ωp(n)分別為當(dāng)前運(yùn)行數(shù)下的權(quán)重,則ωs(n)=(n?1)/F,ωp(n)=1?ωs(n),0ωs(n)1.權(quán)重變化頻率通過F調(diào)整,但F不能太高,這樣會(huì)消耗太多的計(jì)算時(shí)間.因此,在第5節(jié)中運(yùn)行10次以獲得最佳權(quán)重權(quán)衡是相對合理的.

4 HEDA求解3sAISP_SP

4.1 HEDA全局搜索

4.1.1 初始化種群及概率模型

根據(jù)規(guī)則1,令種群規(guī)模為popsize,本文設(shè)計(jì)按產(chǎn)品聚合(product aggregation,PA)的方式產(chǎn)生η×popsize個(gè)體,剩余個(gè)體隨機(jī)產(chǎn)生來初始化種群.PA規(guī)則為先隨機(jī)生成產(chǎn)品序列,以產(chǎn)品為基礎(chǔ)隨機(jī)生成組成該產(chǎn)品的工件序列,再對應(yīng)工件的工序,隨機(jī)生成工件基于工序的排列作為初始化種群.

種群隨機(jī)產(chǎn)生的過程具體如圖5所示(示例第2.4節(jié)).按照PA規(guī)則可使組成產(chǎn)品的工件較為集中,加工階段集中加工完后,能較快的較為集中被運(yùn)輸?shù)窖b配階段,從而縮小了中間庫存,提高裝配同步性.

圖5 按PA規(guī)則隨機(jī)生成初始種群Fig.5 Randomly generate initial population according to PA rules

根據(jù)第3.2.1節(jié)的編碼方式采用加工階段基于工序排列矩陣ρ作為概率模型ρi,j.為盡可能保證算法對解空間均勻搜索,概率模型采用均勻分布,即ρi,j(0)=

4.1.2 概率矩陣更新

在每次迭代中選取種群中φ%的優(yōu)質(zhì)個(gè)體更新概率模型.Ii,j表示統(tǒng)計(jì)工件j出現(xiàn)在工序排列向量第i位上或是之前的次數(shù).Ei,j(g)表示第g次迭代中通過優(yōu)質(zhì)解統(tǒng)計(jì)出來得到的概率.由此可通過更新ρi,j(g),其中γ∈(0,1)為學(xué)習(xí)速率.

4.1.3 采樣方式

算法在后續(xù)的每次迭代中,新種群通過采樣概率矩陣生成.采樣方式是根據(jù)問題性質(zhì)1而設(shè)計(jì)的,目的是使屬于同一個(gè)產(chǎn)品的工件有更大的概率聚合在一起,產(chǎn)生較為優(yōu)質(zhì)的個(gè)體,但每次的采樣均選用輪盤賭操作,在一定程度上保證了種群的多樣性.一旦產(chǎn)生新個(gè)體便構(gòu)成了下一次迭代的新種群.

4.2 局部搜索策略

通過概率矩陣采樣出種群新個(gè)體后用優(yōu)質(zhì)個(gè)體來更新概率矩陣,為了更好引導(dǎo)全局搜索方向,本節(jié)結(jié)合規(guī)則1,設(shè)計(jì)3種情形下的局部搜索策略,有利于避免一些無效搜索,在提高解的質(zhì)量的同時(shí)能夠較好的保留原有解的結(jié)構(gòu).

從選擇的φ%×popsize優(yōu)質(zhì)個(gè)體組成集合ψ={π1,π2,π3,…,πm},對ψ中個(gè)體πr,其中r=1,2,…,m隨機(jī)選取兩個(gè)位置u,v(uv),πr(u)表示個(gè)體πr第u個(gè)位置的工件編碼.

情形1若πr(u)=πr(v),表明這兩個(gè)位置上為同一工件,swap操作將無效,此時(shí)進(jìn)行insert操作.若u

情形2若πr(u)πr(v),表明這兩個(gè)位置上為不同工件,若屬于同一產(chǎn)品,進(jìn)行一種基于insert和swap變鄰域局部搜索混合操作.具體步驟如下:

情形3若且不屬于同一產(chǎn)品,令x=max(u,v)?min(u,v),表 示所有產(chǎn)品的工序總數(shù),即個(gè)體πr的加工階段的長度,HP為產(chǎn)品總數(shù)),若滿足xk,則進(jìn)行Swap操作,生成新個(gè)體

4.3 種群多樣性判定及控制機(jī)制

隨著算法的不斷迭代,種群多樣性會(huì)降低,種群中的個(gè)體變得非常相似,這樣會(huì)導(dǎo)致算法陷入局部最優(yōu).為了解決這個(gè)問題,本文采用文獻(xiàn)[23]方法計(jì)算當(dāng)代種群的多樣性值θdiv.給定一個(gè)多樣性閾值δ,當(dāng)滿足θdivδ時(shí),對當(dāng)前種群進(jìn)行調(diào)整,保留當(dāng)代種群中前φ×popsize/3個(gè)優(yōu)質(zhì)個(gè)體,用PA規(guī)則隨機(jī)生產(chǎn)φ×popsize/3個(gè)個(gè)體,剩下隨機(jī)產(chǎn)生.

4.4 HEDA

由第4節(jié)可知,HEDA在算法操作層面,不僅采用概率模型學(xué)習(xí)優(yōu)質(zhì)解信息并引導(dǎo)算法全局搜索,同時(shí)利用第3.1節(jié)對問題分析得到的規(guī)則,設(shè)計(jì)3種情形下基于鄰域操作的局部搜索,對全局搜索發(fā)現(xiàn)的優(yōu)質(zhì)區(qū)域進(jìn)行細(xì)致搜索,從而使算法在全局和局部搜索之間達(dá)到良好平衡,可實(shí)現(xiàn)對復(fù)雜解空間的有效搜索.HEDA的算法框架如圖6所示.

5 仿真實(shí)驗(yàn)結(jié)果與分析

本節(jié)分為3部分:第1部分依據(jù)第2節(jié)構(gòu)建的數(shù)學(xué)規(guī)劃模型與排列模型,對小規(guī)模問題分別用優(yōu)化求解器GUROBI與HEDA進(jìn)行求解,以驗(yàn)證HEDA求解結(jié)果的近似最優(yōu)性,同時(shí)對較大規(guī)模問題用HEDA和其他有效智能算法求解,以驗(yàn)證HEDA的求解性能;第2部分研究了在兩個(gè)指標(biāo)下,同步性與準(zhǔn)時(shí)性的權(quán)重設(shè)置問題;第3部分討論了同步性對半成品庫存的影響.

5.1 HEDA算法比較

所有的測試問題都是基于三階段裝配集成系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)的,測試數(shù)據(jù)請具體參見(https://pan.baidu.com/s/1Vsd4xBpBE50TbyF6w78fHg).3sAISP_SP 每個(gè)產(chǎn)品所組成的工件數(shù)及工件所對應(yīng)工序數(shù)在[2,5]和[1,3]隨機(jī)生成,各工件工序加工時(shí)間及每個(gè)產(chǎn)品的裝配時(shí)間在[20,80]和[100,200]隨機(jī)生成,每個(gè)工件的載荷在[20,50]隨機(jī)生成,每個(gè)產(chǎn)品的交貨期由最大平均完工時(shí)間的[50%,100%]均勻分布產(chǎn)生.運(yùn)輸車輛數(shù)對每個(gè)測試問題有不同的影響,本文列舉的測試問題表達(dá)為P_M_T.所有算法和測試程序均用Delphi 2010編程實(shí)現(xiàn),操作系統(tǒng)為WinXP.所有算法在相同的測試時(shí)間下獨(dú)立運(yùn)行10次.

圖6 HEDA算法框架Fig.6 The algorithm framework of HEDA

5.1.1 小規(guī) 模 問題 下GUROBI與HEDA算法 實(shí)驗(yàn)結(jié)果比較

本文用優(yōu)化求解器GUROBI求解第2.3.1節(jié)中的數(shù)學(xué)規(guī)劃模型,同時(shí)用HEDA求解第2.3.2節(jié)中的排列模型.表2為權(quán)重ωs=ωp=0.5,在小規(guī)模問題下分別采用GUROBI和HEDA求解結(jié)果比較.表中第1列表示工件數(shù)J,第2列P_M _T為對應(yīng)問題規(guī)模,隨后兩列表示GUROBI求得對應(yīng)問題規(guī)模的最優(yōu)解(optimal solution,OPS)和時(shí)間,其余列分別表示HEDA對測試問題分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)的最好值Best、平均值A(chǔ)VG、平均相對偏差值RPDs、平均絕對偏差值MADs和運(yùn)行時(shí)間.從表中數(shù)據(jù)可知RPDs均值和MADs均值相對較低,且求解時(shí)間明顯低于GUROBI,這說明所提算法獲得的解非常接近問題的最優(yōu)解,具有良好的近似最優(yōu)性.

表2 GUROBI和HEDA比較(ωs=ωp=0.5)Table 2 Comparison of GUROBI and HEDA(ωs=ωp=0.5)

5.1.2 HEDA與其他智能算法實(shí)驗(yàn)結(jié)果比較

為了進(jìn)一步驗(yàn)證HEDA的性能,本節(jié)針對17個(gè)中大規(guī)模問題,將HEDA與近年國際期刊中的有效算法GA[2]進(jìn)行對比.其中:HEDA 的參數(shù)設(shè)置為:popsize=120,η=0.6,γ=0.15,φ=0.3;GA[2]的參數(shù)設(shè)置為:popsize=150,pc=0.3,pm=0.6.兩種算法所選擇的參數(shù)均為參數(shù)實(shí)驗(yàn)后得到的最好參數(shù).HEDA運(yùn)行200代,GA運(yùn)行時(shí)間與HEDA相同,兩種算法的對比結(jié)果如表3所示,測試指標(biāo)包括最好值Best、最差值Worst、平均值A(chǔ)VG、方差SD.從表3中可以看出,HEDA在大多數(shù)問題上優(yōu)于GA,且SD值占優(yōu),這表明HEDA可有效求解3sAISPSP問題.

表3 HEDA與GA[2]比較(ωs=ωp=0.5)Table 3 Comparison of HEDA and GA[2](ωs=ωp=0.5)

5.2 權(quán)重設(shè)置對同步性和準(zhǔn)時(shí)性的影響分析

在實(shí)際生產(chǎn)過程中企業(yè)的資源是有限,即加工機(jī)器和運(yùn)輸車輛一定,針對在不同產(chǎn)品數(shù)(訂單)情況下,進(jìn)一步研究不同權(quán)重組合對同步性和準(zhǔn)時(shí)性的影響,為企業(yè)決策者提供較好的參考.

本節(jié)考慮加工階段有5臺異構(gòu)并行機(jī),3輛運(yùn)輸車輛,產(chǎn)品數(shù)選取3,5,7,9,用本文第3.2.2節(jié)權(quán)重取值方法,令F=10確定11種權(quán)重組合ωs,ωp,求得在HEDA下同步性FS(fs)、準(zhǔn)時(shí)性FP(fp)兩個(gè)指標(biāo)的數(shù)據(jù)(見表4).

表4 權(quán)重設(shè)置實(shí)驗(yàn)結(jié)果Table 4 Results of weight trade-off

為了直觀地比較FS,FP不同規(guī)模下不同權(quán)重組合的變化趨勢,對表4的結(jié)果進(jìn)行歸一化處理,FS,FP在不同規(guī)模下的結(jié)果見圖7?8.由圖可知,FS,FP在不同規(guī)模下的結(jié)果見圖7?8.由圖可知,FS隨ωs減少而增加,FP隨ωp減少而增加,說明在WSM目標(biāo)函數(shù)中考慮同步性及準(zhǔn)時(shí)性可以給生產(chǎn)帶來顯著改善.從權(quán)重組合(0.5,0.5)到(0,1),FS,FP斜率變化都變緩.盡管針對不同的測試問題有不同優(yōu)先權(quán)重組合,但在(0.5,0.5)到(0,1),之間FS,FP達(dá)到了相對平衡,差異度最小.因此,對決策者來應(yīng)優(yōu)先從(0.5,0.5)到(0,1)范圍內(nèi)選擇權(quán)重組合較為合理.

圖7 FS數(shù)值Fig.7 The value of FS

圖8 FP數(shù)值Fig.8 The value of FP

5.3 同步性對半成品庫存的影響

庫存是企業(yè)非常重要的要素之一.工件從加工階段完工后受到運(yùn)輸車輛的裝載限制不能馬上被運(yùn)輸走,需要對工件進(jìn)行暫時(shí)存儲稱為半成品庫存(semi-finished inventory,SI).本節(jié)將比較在上節(jié)4種問題規(guī)模下的權(quán)重組合為(1,0),(0,1)及優(yōu)先權(quán)重組合(0.5,0.5)3種情況下的SI.其中,CPj).每個(gè)情況在不同規(guī)模下進(jìn)行10次獨(dú)立實(shí)驗(yàn).每個(gè)規(guī)模均取優(yōu)先權(quán)重組合運(yùn)行100代,而在其他權(quán)重組合的運(yùn)行時(shí)間與其相同.

具體結(jié)果如表5所示.

表5 3種權(quán)重組合下SI數(shù)據(jù)比較Table 5 Comparison of SI data with three weight combinations

從表中數(shù)據(jù)可知,權(quán)重組合為(1,0)和(0.5,0.5)都優(yōu)于(0,1).這表明側(cè)重考慮同步性這一目標(biāo)可有效地降低SI水平.此外,還可看出權(quán)重組合為(1,0)的SI值小于(0.5,0.5),這是由于(1,0)的權(quán)重更大.但這一結(jié)果并不影響決策者對優(yōu)先權(quán)重的選擇,若半成品庫存較大超過可接受的范圍,可多派運(yùn)輸車輛等策略以降低SI水平.

6 結(jié)語

本文針對以加工–運(yùn)輸–裝配同步性和交貨準(zhǔn)時(shí)性加權(quán)和為目標(biāo)的三階段裝配集成調(diào)度問題研究相應(yīng)的問題建模、求解算法和目標(biāo)權(quán)重設(shè)置.在建模方面,建立問題的數(shù)學(xué)規(guī)劃模型和排列模型,并闡述兩類模型的聯(lián)系和區(qū)別,指出排列模型結(jié)構(gòu)簡單、約束隱式包含在解的編碼中,適合設(shè)計(jì)智能優(yōu)化算法求解.在求解算法方面,結(jié)合問題特點(diǎn)設(shè)計(jì)合理的編碼和解碼規(guī)則,利用EDA概率模型學(xué)習(xí)優(yōu)質(zhì)解信息并引導(dǎo)算法全局搜索,以發(fā)現(xiàn)解空間中存在優(yōu)質(zhì)解的區(qū)域,同時(shí)基于多種鄰域操作設(shè)計(jì)局部搜索對優(yōu)質(zhì)解區(qū)域進(jìn)行深入搜索,以增強(qiáng)算法的局部搜索能力,進(jìn)而提出混合分布估計(jì)算法(HEDA).通過在不同規(guī)模問題上的仿真實(shí)驗(yàn)和算法比較,驗(yàn)證HEDA可有效求解3sAISP_SP.在目標(biāo)權(quán)重設(shè)置方面,進(jìn)一步分析同步性和準(zhǔn)時(shí)性的合理權(quán)重組合及同步性對半成品庫存的影響,并得到以下幾個(gè)結(jié)論:1)考慮同步性對減少半成品庫存起著重要作用;2)不能一味的追求準(zhǔn)時(shí)性,可能會(huì)嚴(yán)重影響同步性;3)決策者可優(yōu)先從(0.5,0.5)到(0,1)范圍內(nèi)選擇權(quán)重組合以達(dá)到兩目標(biāo)間的較好平衡.下一步的研究將在此模型基礎(chǔ)上進(jìn)一步考慮裝配–配送同步問題,并提出更加有效的算法進(jìn)行求解.