鄧 超 胡 蓉 錢(qián) 斌

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

1 引言

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

同步性和準(zhǔn)時(shí)性是企業(yè)物流中兩個(gè)關(guān)鍵的因素[7].同步性可有效利用企業(yè)資源,建立與市場(chǎng)需求同步、連續(xù)的產(chǎn)品流.同步生產(chǎn)能夠更好地滿足生產(chǎn)中產(chǎn)品的多樣性需求,有利于減少在制品庫(kù)存[8].準(zhǔn)時(shí)性是在客戶需要的時(shí)間和地點(diǎn),生產(chǎn)所需要數(shù)量和質(zhì)量的產(chǎn)品和服務(wù).裝配制造業(yè)常將生產(chǎn)和交貨整合在一起做出運(yùn)營(yíng)決策以提高準(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)及成品(在制品)庫(kù)存增加,同時(shí)也影響訂單交付的準(zhǔn)時(shí)性.因此,生產(chǎn)中考慮同步性具有重要現(xiàn)實(shí)意義.

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

在已有文獻(xiàn)中調(diào)度問(wèn)題模型主要包括數(shù)學(xué)規(guī)劃模型和排列模型.數(shù)學(xué)規(guī)劃模型采用運(yùn)籌學(xué)方法求解,譬如很多文獻(xiàn)中采用基于分支定界、分支定價(jià)等方法的商用求解器GUROBI 或CPLEX求解.由于這些運(yùn)籌學(xué)方法遍歷或部分遍歷解空間,故較短時(shí)間內(nèi)(即幾分鐘內(nèi))只能求解小規(guī)模問(wèn)題.排列模型一般采用智能優(yōu)化方法求解.排列模型將問(wèn)題解空間壓縮為一個(gè)極度扁平的空間,使得優(yōu)化目標(biāo)函數(shù)值的范圍遠(yuǎn)小于問(wèn)題解或排列的數(shù)量,大量不同解對(duì)應(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ī)模問(wèn)題.這是智能優(yōu)化調(diào)度算法近年快速發(fā)展的主要原因.因此,本文設(shè)計(jì)智能優(yōu)化算法求解不同規(guī)模的3sAISP_SP(對(duì)應(yīng)排列模型),同時(shí)采用基于運(yùn)籌學(xué)方法的GUROBI 獲取小規(guī)模3sAISP_SP(對(duì)應(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ì)的方式對(duì)種群中的優(yōu)質(zhì)個(gè)體進(jìn)行學(xué)習(xí)并構(gòu)造概率模型,然后對(duì)概率模型進(jìn)行采樣產(chǎn)生新種群,從而引導(dǎo)算法的搜索方向,具有較好的全局搜索能力.EDA在生產(chǎn)調(diào)度領(lǐng)域已開(kāi)展較多研究.李子輝等[17]考慮3sAISP問(wèn)題,以平均完成時(shí)間和延遲時(shí)間加權(quán)和為優(yōu)化目標(biāo),提出一種自適應(yīng)EDA求解.該算法通過(guò)設(shè)計(jì)基于信息熵的概率分布模型自適應(yīng)更新機(jī)制和保留優(yōu)良模式的新種群采樣生成方法來(lái)增強(qiáng)全局搜索能力,同時(shí)提出基于插入(insert)操作的鄰域搜索來(lái)增強(qiáng)算法的局部搜索能力.Qian等[18]考慮可重入流水線調(diào)度問(wèn)題,以最小化最大完工時(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)度問(wèn)題,以makespan為優(yōu)化目標(biāo),提出了一種混合EDA求解.該算法提出變量鄰域搜索的方式產(chǎn)生后代個(gè)體,從而在其鄰域中獲得更好的解以提高算法性能.Li等[20]考慮帶序相關(guān)設(shè)置時(shí)間的多目標(biāo)作業(yè)車(chē)間調(diào)度問(wèn)題,以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)度問(wèn)題上取得成功應(yīng)用,但針對(duì)3sAISP_SP的研究處于空白狀態(tài).

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

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

2.1 問(wèn)題總體描述

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

完成的每個(gè)產(chǎn)品都有其單獨(dú)的交貨截止日期Dz,任何早于或晚于Dz完成的產(chǎn)品將受到提前或遲到的處罰.此外,受車(chē)輛額定載荷及運(yùn)輸效率限制,工件在加工階段完工之后并非立刻被車(chē)輛運(yùn)輸走,若不夠裝滿一輛車(chē)或者需要等待車(chē)輛往返運(yùn)輸,完工工件需要放入中轉(zhuǎn)區(qū)域等待,從而產(chǎn)生了完工工件庫(kù)存.由此可見(jià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)度問(wèn)題通常運(yùn)用工件完成時(shí)間與基準(zhǔn)之間的平均差異來(lái)衡量[21].然而,平均差異衡量方法在某些情形下容易發(fā)生補(bǔ)償效應(yīng)而不能客觀反映同步性.因此,本文選用最長(zhǎng)裝配等待時(shí)間WT來(lái)衡量同步性,即屬于同一產(chǎn)品的工件最早到達(dá)裝配中心時(shí)間與最晚到達(dá)裝配中心時(shí)間之間的間隔,并提出平均最長(zhǎng)等待時(shí)間指標(biāo)fs來(lái)衡量裝配同步性,即

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

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

2.3 問(wèn)題模型

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

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

參數(shù):

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

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

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

tw:車(chē)輛t來(lái)回運(yùn)輸?shù)奶藬?shù);

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

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

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

Vj:工件j的載荷;

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

中間變量:

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

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

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

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

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

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

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

SAz:產(chǎn)品z開(kāi)始裝配時(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ī)器集中選出一臺(tái)機(jī)器進(jìn)行加工;約束(10)?(11)為每臺(tái)可加工機(jī)器在同一時(shí)間只能進(jìn)行一次操作;約束(12)為工件加工階段完工時(shí)間;約束(14)?(15)為每個(gè)工件只能被車(chē)輛運(yùn)送一次;約束(16)為裝入每輛車(chē)的工件總載荷不超過(guò)車(chē)輛額定載荷;約束(17)?(18)為工件按工件序列分配給運(yùn)輸車(chē)輛且只分配一次;約束(19)為工件開(kāi)始運(yùn)輸時(shí)間;約束(20)為工件完工運(yùn)輸時(shí)間受裝入該車(chē)輛中工件的完工時(shí)間限制;約束(21)為工件開(kāi)始運(yùn)輸時(shí)間受裝入該車(chē)輛前一趟運(yùn)輸開(kāi)始時(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)度問(wèn)題(HPMP_RT).為所有工件的工序在加工階段的排列.加工設(shè)備k上加工工序的數(shù)量為Hk,πk=為工件的工序在加工階段加工設(shè)備k上的排列,為πk中第i個(gè)位置的工件的工序.的加工時(shí)間,為πk中第i個(gè)位置的工件首次到達(dá)第k臺(tái)加工設(shè)備的時(shí)間,即釋放時(shí)間.前一次加工工序的設(shè)備號(hào),前一個(gè)工序在設(shè)備號(hào)為上的排列表示為若工件首次加工,則在第k臺(tái)機(jī)器上加工時(shí)該臺(tái)機(jī)器上前一次加工的工件工序,工件工序在排列中的位置記為若加工的機(jī)器為首次加工工件,則的完成時(shí)間計(jì)算如下:

2)運(yùn)輸階段:帶車(chē)輛載重約束的多車(chē)輛單點(diǎn)配送問(wèn)題.wt為表示車(chē)輛t來(lái)回運(yùn)輸?shù)奶藬?shù),wt1.Vt為車(chē)輛t的額定載荷(定值).t_tran為表示車(chē)輛的運(yùn)輸時(shí)間(定值).為所有工件在運(yùn)輸階段的排列,為πTR中第j個(gè)位置的工件.為πTR中第j個(gè)位置的工件加工階段的完工時(shí)間.為πTR中第j個(gè)位置的工件的重量.為πTR中第j個(gè)位置的工件在第t臺(tái)車(chē)輛的開(kāi)始運(yùn)輸時(shí)間.為運(yùn)輸階段第wt趟裝載在車(chē)輛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 兩類(lèi)模型的特點(diǎn)

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

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

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

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

2.4 問(wèn)題示例

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

在圖3中:V1?1表示第1輛運(yùn)輸車(chē)輛的第1趟.該車(chē)輛在滿足載荷的前提下運(yùn)送屬于P1,P2產(chǎn)品的J5,J1,J4三個(gè)工件,且CT51=CT11=CT41=614;V2?1車(chē)輛運(yùn)送屬于P1,P3產(chǎn)品的J2,J3,J9工件,CT22=CT32=CT92=692,屬于P1的工件全部到達(dá)開(kāi)始裝配,則WT1=692?614=78.此時(shí)兩輛運(yùn)輸車(chē)輛均已在途,剩余加工完的工件需要等待車(chē)輛往返方能被運(yùn)送,故V1?2車(chē)輛運(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è)階段子問(wèn)題的簡(jiǎn)單疊加(見(jiàn)圖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í)間來(lái)度量.同步性貫穿于各個(gè)階段并影響準(zhǔn)時(shí)性,前一階段同步性是后一階段同步性的基礎(chǔ);準(zhǔn)時(shí)性由裝配階段產(chǎn)品完工時(shí)間最終確定.

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

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

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

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

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

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

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

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

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

3.2.1 編碼及解碼

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

編碼:第1部分為加工階段基于工序的排列,其長(zhǎng)度是由產(chǎn)品層?工件層?工序?qū)哟_定,即產(chǎn)品對(duì)應(yīng)工件集合Pz及工件對(duì)應(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對(duì)應(yīng)3個(gè)工件的工序數(shù)為[2,1,3],產(chǎn)品P2對(duì)應(yīng)3個(gè)工件的工序數(shù)為[3,3,3],產(chǎn)品P3對(duì)應(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}.

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

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

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

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

圖4 編碼方式Fig.4 Encoding

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

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

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

Step 3檢驗(yàn)待運(yùn)輸工件集合中是否存在工件滿足若滿足則將工件放入車(chē)輛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í)間非降序排列得到對(duì)應(yīng)產(chǎn)品編碼πP.如組成產(chǎn)品P1,P2,P3最后一個(gè)工件到達(dá)裝配車(chē)間的時(shí)間分別為21,34,17,則產(chǎn)品排序?yàn)閧3,1,2}(見(jiàn)圖4).

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

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

如果決策者依據(jù)偏好給出權(quán)重組合,則將問(wèn)題搜索方向固定在一維目標(biāo)空間中.如果沒(méi)有給出權(quán)重偏好,則將對(duì)權(quán)重進(jìn)行調(diào)整以確定最佳權(quán)重組合.本文采用一種線性調(diào)整權(quán)重方式來(lái)實(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)重變化頻率通過(guò)F調(diào)整,但F不能太高,這樣會(huì)消耗太多的計(jì)算時(shí)間.因此,在第5節(jié)中運(yùn)行10次以獲得最佳權(quán)重權(quán)衡是相對(duì)合理的.

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)生來(lái)初始化種群.PA規(guī)則為先隨機(jī)生成產(chǎn)品序列,以產(chǎn)品為基礎(chǔ)隨機(jī)生成組成該產(chǎn)品的工件序列,再對(duì)應(yīng)工件的工序,隨機(jī)生成工件基于工序的排列作為初始化種群.

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

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

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

4.1.2 概率矩陣更新

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

4.1.3 采樣方式

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

4.2 局部搜索策略

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

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

情形1若πr(u)=πr(v),表明這兩個(gè)位置上為同一工件,swap操作將無(wú)效,此時(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的加工階段的長(zhǎng)度,HP為產(chǎn)品總數(shù)),若滿足xk,則進(jìn)行Swap操作,生成新個(gè)體

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

隨著算法的不斷迭代,種群多樣性會(huì)降低,種群中的個(gè)體變得非常相似,這樣會(huì)導(dǎo)致算法陷入局部最優(yōu).為了解決這個(gè)問(wèn)題,本文采用文獻(xiàn)[23]方法計(jì)算當(dāng)代種群的多樣性值θdiv.給定一個(gè)多樣性閾值δ,當(dāng)滿足θdivδ時(shí),對(duì)當(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é)對(duì)問(wèn)題分析得到的規(guī)則,設(shè)計(jì)3種情形下基于鄰域操作的局部搜索,對(duì)全局搜索發(fā)現(xiàn)的優(yōu)質(zhì)區(qū)域進(jìn)行細(xì)致搜索,從而使算法在全局和局部搜索之間達(dá)到良好平衡,可實(shí)現(xiàn)對(duì)復(fù)雜解空間的有效搜索.HEDA的算法框架如圖6所示.

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

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

5.1 HEDA算法比較

所有的測(cè)試問(wèn)題都是基于三階段裝配集成系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)的,測(cè)試數(shù)據(jù)請(qǐng)具體參見(jiàn)(https://pan.baidu.com/s/1Vsd4xBpBE50TbyF6w78fHg).3sAISP_SP 每個(gè)產(chǎn)品所組成的工件數(shù)及工件所對(duì)應(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)輸車(chē)輛數(shù)對(duì)每個(gè)測(cè)試問(wèn)題有不同的影響,本文列舉的測(cè)試問(wèn)題表達(dá)為P_M_T.所有算法和測(cè)試程序均用Delphi 2010編程實(shí)現(xiàn),操作系統(tǒng)為WinXP.所有算法在相同的測(cè)試時(shí)間下獨(dú)立運(yùn)行10次.

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

5.1.1 小規(guī) 模 問(wèn)題 下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ī)模問(wèn)題下分別采用GUROBI和HEDA求解結(jié)果比較.表中第1列表示工件數(shù)J,第2列P_M _T為對(duì)應(yīng)問(wèn)題規(guī)模,隨后兩列表示GUROBI求得對(duì)應(yīng)問(wèn)題規(guī)模的最優(yōu)解(optimal solution,OPS)和時(shí)間,其余列分別表示HEDA對(duì)測(cè)試問(wèn)題分別進(jìn)行10次獨(dú)立實(shí)驗(yàn)的最好值Best、平均值A(chǔ)VG、平均相對(duì)偏差值RPDs、平均絕對(duì)偏差值MADs和運(yùn)行時(shí)間.從表中數(shù)據(jù)可知RPDs均值和MADs均值相對(duì)較低,且求解時(shí)間明顯低于GUROBI,這說(shuō)明所提算法獲得的解非常接近問(wèn)題的最優(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é)針對(duì)17個(gè)中大規(guī)模問(wèn)題,將HEDA與近年國(guó)際期刊中的有效算法GA[2]進(jìn)行對(duì)比.其中: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相同,兩種算法的對(duì)比結(jié)果如表3所示,測(cè)試指標(biāo)包括最好值Best、最差值Worst、平均值A(chǔ)VG、方差SD.從表3中可以看出,HEDA在大多數(shù)問(wèn)題上優(yōu)于GA,且SD值占優(yōu),這表明HEDA可有效求解3sAISPSP問(wèn)題.

表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è)置對(duì)同步性和準(zhǔn)時(shí)性的影響分析

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

本節(jié)考慮加工階段有5臺(tái)異構(gòu)并行機(jī),3輛運(yùn)輸車(chē)輛,產(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ù)(見(jiàn)表4).

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

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

庫(kù)存是企業(yè)非常重要的要素之一.工件從加工階段完工后受到運(yùn)輸車(chē)輛的裝載限制不能馬上被運(yùn)輸走,需要對(duì)工件進(jìn)行暫時(shí)存儲(chǔ)稱(chēng)為半成品庫(kù)存(semi-finished inventory,SI).本節(jié)將比較在上節(jié)4種問(wèn)題規(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é)果并不影響決策者對(duì)優(yōu)先權(quán)重的選擇,若半成品庫(kù)存較大超過(guò)可接受的范圍,可多派運(yùn)輸車(chē)輛等策略以降低SI水平.

6 結(jié)語(yǔ)

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