朱天一,呂雅瓊,張樹(shù)柱

(1.武漢理工大學(xué) 交通物流工程學(xué)院,湖北 武漢 430070;2.浙江財(cái)經(jīng)大學(xué) 信息管理與人工智能學(xué)院,浙江 杭州 310018)

智能制造要求傳統(tǒng)車(chē)間提高自動(dòng)化水平,加快物料流轉(zhuǎn),降低生產(chǎn)成本,提高經(jīng)濟(jì)效益。在工件的排程問(wèn)題中,劉蓉等[1]針對(duì)具有批處理的柔性制造車(chē)間,提出了改進(jìn)遺傳算法并進(jìn)行有效調(diào)度。AGV的調(diào)度極大地影響了智能車(chē)間加工效率,范媛等[2]在多AGV的倉(cāng)儲(chǔ)空間里完成了車(chē)輛的合理配置。多AGV的智能車(chē)間的系統(tǒng)性能優(yōu)化,即是對(duì)具有更高計(jì)算復(fù)雜度的AGV與機(jī)器聯(lián)合調(diào)度問(wèn)題的方案進(jìn)行優(yōu)化。

近年來(lái),學(xué)者就AGV與機(jī)器集成調(diào)度展開(kāi)研究,針對(duì)機(jī)器資源與路徑資源的分配,遺傳算法[3]、粒子群算法[4-5]、差分進(jìn)化算法[6]等進(jìn)化算法被證明是行之有效的,并且可以結(jié)合啟發(fā)規(guī)則[7]。但這些研究假設(shè)AGV的運(yùn)行速度可變,不能完成對(duì)系統(tǒng)的實(shí)時(shí)控制。

Petri網(wǎng)(PN)的形式化語(yǔ)言適用于大型FMS中經(jīng)常出現(xiàn)的異步觸發(fā)、阻塞、并發(fā)和其他動(dòng)態(tài)行為[8]。Petri網(wǎng)構(gòu)建系統(tǒng)模型獲得初始狀態(tài),通過(guò)狀態(tài)-變遷-狀態(tài)的形式獲得AGV生產(chǎn)系統(tǒng)中的全部解空間。Petri網(wǎng)模型可通過(guò)遺傳等進(jìn)化算法[9-10]獲得確定問(wèn)題下的最優(yōu)變遷序列,實(shí)現(xiàn)最優(yōu)調(diào)度決策。在AGV路徑規(guī)劃問(wèn)題上,李圣男等[11]采用分解子網(wǎng)方式實(shí)現(xiàn)AGV的無(wú)沖突運(yùn)行?；赑etri網(wǎng)的方法不僅可以在機(jī)器調(diào)度上具備優(yōu)勢(shì),還可以獲得每個(gè)時(shí)間點(diǎn)AGV的運(yùn)行狀態(tài),以便進(jìn)一步優(yōu)化系統(tǒng)。因此,筆者將采用基于Petri網(wǎng)的機(jī)器調(diào)度與路徑規(guī)劃兩階段求解方法,采用有色時(shí)間Petri網(wǎng)縮小網(wǎng)絡(luò)規(guī)模,并通過(guò)遺傳算法與A*算法實(shí)現(xiàn)調(diào)度方案。

1 問(wèn)題描述

具有AGV系統(tǒng)的智能生產(chǎn)車(chē)間聯(lián)合調(diào)度優(yōu)化問(wèn)題通?？梢悦枋鰹?已知工件集J={J1,J2,…,JN},M={M1,M2,…,MM},AGV集R={R1,R2,…,RR},每個(gè)工件需要操作OPi={Pi1,Pi2,…,Pi|OPi|},|OPi|為工件i的操作數(shù)量,i∈J。假設(shè)每個(gè)工序的加工機(jī)器已知,且工件在不同機(jī)器上加工需要AGV配送,其運(yùn)輸時(shí)間由選擇的路線決定,要求完成所有工件的加工任務(wù)的完工時(shí)間最小。

為了使研究問(wèn)題更為完備,做出以下假設(shè):①初始時(shí)刻所有AGV與機(jī)器可用,所有加工零件存放于裝卸站;②AGV運(yùn)輸速度恒定且裝卸時(shí)間不計(jì);③機(jī)器的坐標(biāo)已知,體積忽略不計(jì),所有AGV的初始位置已知。

2 Petri網(wǎng)建模

2.1 Petri網(wǎng)模型

模型分為生產(chǎn)與物流兩部分,需要通過(guò)資源庫(kù)所將不同的子模型進(jìn)行鏈接。軌道模型將節(jié)點(diǎn)變?yōu)閹?kù)所,AGV在節(jié)點(diǎn)上的移動(dòng)通過(guò)變遷實(shí)現(xiàn)。加工過(guò)程模型則以變遷映射一個(gè)加工行為。對(duì)只有4個(gè)節(jié)點(diǎn)、2臺(tái)加工機(jī)器、1輛AGV的場(chǎng)景,完成2件工件加工的聯(lián)合模型如圖1所示,該模型存在19個(gè)庫(kù)所、20個(gè)變遷,因此有必要對(duì)其進(jìn)行簡(jiǎn)化。

圖1 機(jī)器與AGV聯(lián)合調(diào)度及建模

2.2 有色時(shí)間Petri網(wǎng)

為了降低Petri網(wǎng)模型規(guī)模,分別對(duì)零件加工過(guò)程與AGV系統(tǒng)展開(kāi)語(yǔ)義拓展。拓展的Petri網(wǎng)語(yǔ)義包括T-變遷、P-變遷、C-變遷、C-庫(kù)所和D-庫(kù)所[12],詳細(xì)解釋如表1所示。采用拓展語(yǔ)義構(gòu)建基本模型,對(duì)工件活動(dòng)分別構(gòu)建加工過(guò)程模型和運(yùn)輸過(guò)程模型,基本結(jié)構(gòu)如圖2(a)和圖2(b)所示,對(duì)AGV的活動(dòng)進(jìn)行建模,基本結(jié)構(gòu)如圖2(c)所示。

表1 拓展Petri網(wǎng)圖形解釋

圖2 拓展語(yǔ)義在基本結(jié)構(gòu)中的應(yīng)用

3 算例分析

3.1 算例描述

具有2輛AGV的FMS調(diào)度車(chē)間需要6臺(tái)機(jī)器完成6種工件的加工,加工車(chē)間場(chǎng)景布局如圖3所示,其中Mi表示具有輸入緩沖區(qū)和輸出緩沖區(qū)的加工機(jī)器;AGV初始位置在?？空?編號(hào)為0,其通過(guò)每條邊所需要時(shí)間為1;UL為裝載站,零件的原材料與產(chǎn)成品的存放處。工件的加工時(shí)間如表2所示。

圖3 車(chē)間布局圖

表2 工件的加工時(shí)間

3.2 面向算例的CTPN模型

簡(jiǎn)化后的CTPN聯(lián)合調(diào)度模型如圖4所示。其中,加工流程考慮AGV空載運(yùn)行、AGV負(fù)載運(yùn)輸、機(jī)器加工3類(lèi)具體動(dòng)作,其中JIi,j、JOi,j分別表示工件i在機(jī)器j的輸入與輸出緩存區(qū),ULi、Ti,j,k、Pi,j分別表示工件i的裝卸動(dòng)作、由j配送至k的動(dòng)作、在機(jī)器j加工的動(dòng)作。每個(gè)資源以不同種類(lèi)顏色存在于庫(kù)所中,如UL中存在6種顏色的令牌,顏色標(biāo)識(shí)的解釋如表3所示。

表3 加工模型顏色描述

圖4 加工過(guò)程的CTPN模型

對(duì)案例的求解則是在CTPN模型中確定一組(Ti,j,k,Pi,j)構(gòu)成的變遷序列,表示配送和加工的順序。當(dāng)Pi,j為工件i的第一道工序時(shí),該動(dòng)作變?yōu)?Ti,O,UL,Ti,UL,k,Pi,1),其中Ti,O,UL為AGV從當(dāng)前節(jié)點(diǎn)前往裝卸站UL的動(dòng)作,Ti,UL,k表示AGV從UL到目標(biāo)機(jī)器k的動(dòng)作。AGV與機(jī)器的占用由函數(shù)Φ確定,Φ(Ri)=1表示機(jī)器Mi被占用,否則為空閑;同理,Φ(Ri)=1表示AGV集中Ri被占用,否則為空閑。求得完成所有的變遷動(dòng)作所需要的時(shí)間最小,即為最佳任務(wù)分配方案。

3.3 實(shí)驗(yàn)分析

采用遺傳算法與A*的聯(lián)合算法求解算例,并與禁忌搜索算法進(jìn)行對(duì)比分析。對(duì)于遺傳算法,將每個(gè)染色體編碼為加工序列,生成配送任務(wù),再通過(guò)A*算法中求解每個(gè)AGV的最短路徑。測(cè)試使用Python作為開(kāi)發(fā)工具,設(shè)置遺傳算法的種群規(guī)模為100,迭代次數(shù)為100次,交叉概率為0.6,變異概率為0.1。每個(gè)染色體為一個(gè)任務(wù)列表,傳入運(yùn)輸模型,通過(guò)A*算法依次計(jì)算完成每個(gè)任務(wù)的時(shí)間,使總?cè)蝿?wù)完工時(shí)間最小。

算法優(yōu)化曲線如圖5所示,縱坐標(biāo)為每一代的最短完工時(shí)間,橫坐標(biāo)為迭代步數(shù)。從圖5可以看出,基于遺傳與A*的聯(lián)合算法在第20代時(shí)開(kāi)始收斂,而禁忌搜索算法則需要迭代90代才開(kāi)始收斂。為了進(jìn)一步說(shuō)明所提算法的可行性,統(tǒng)計(jì)了10次計(jì)算結(jié)果進(jìn)行對(duì)比,具體結(jié)果如表4所示,可以看出筆者算法與禁忌搜索算法皆可以獲得最優(yōu)調(diào)度方案,但筆者算法所需的平均計(jì)算時(shí)間更短。

圖5 算法優(yōu)化曲線對(duì)比

表4 實(shí)驗(yàn)結(jié)果對(duì)比

在選擇的案例中,獲得的調(diào)度結(jié)果如圖6和圖7所示。圖6為AGV運(yùn)行狀態(tài)圖,表示每個(gè)時(shí)間點(diǎn)每輛AGV所在的位置。圖7為聯(lián)合調(diào)度甘特圖,每個(gè)有色矩形表示加工過(guò)程或配送過(guò)程,顏色代表了這一時(shí)間段內(nèi)機(jī)器與AGV所攜帶的工件類(lèi)型。

圖6 AGV運(yùn)行狀態(tài)圖

圖7 聯(lián)合調(diào)度甘特圖

4 結(jié)論

(1)提出了一種基于遺傳算法與A*優(yōu)化的CTPN模型,通過(guò)求解最優(yōu)變遷序列獲得聯(lián)合調(diào)度決策?；谶z傳算法與A*的聯(lián)合優(yōu)化算法在雙資源調(diào)度問(wèn)題上具備優(yōu)勢(shì),收斂速度快,計(jì)算結(jié)果準(zhǔn)確,且所提方法可以觀測(cè)AGV的運(yùn)行狀態(tài),為基于AGV的多目標(biāo)優(yōu)化奠定基礎(chǔ)。

(2)Petri網(wǎng)圖形化的表達(dá)方式能夠直觀反映車(chē)間生產(chǎn)活動(dòng)中的并發(fā)、沖突行為。

(3)所提出的建模方法有效縮減了普通Petri網(wǎng)表征系統(tǒng)時(shí)的規(guī)模,可讀性大大加強(qiáng),調(diào)度結(jié)果準(zhǔn)確,可作為一種可靠的雙資源調(diào)度優(yōu)化模型。

(4)盡管算例依據(jù)提出的方法得到了有效調(diào)度方案,但仍有很多方面值得拓展改進(jìn)。研究中算例規(guī)模較小,且忽略了AGV彼此之間的影響,在未來(lái)的研究中將擴(kuò)大問(wèn)題規(guī)模,并具體考慮更符合實(shí)際場(chǎng)景中的多AGV路徑?jīng)_突、搶占、死鎖等約束。