基于CTPN的智能車間雙資源調(diào)度研究

朱天一,呂雅瓊,張樹柱

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

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

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

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

1 問題描述

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

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

2 Petri網(wǎng)建模

2.1 Petri網(wǎng)模型

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

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

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

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

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

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

3 算例分析

3.1 算例描述

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

圖3 車間布局圖

表2 工件的加工時間

3.2 面向算例的CTPN模型

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

表3 加工模型顏色描述

圖4 加工過程的CTPN模型

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

3.3 實驗分析

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

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

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

表4 實驗結(jié)果對比

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

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

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

4 結(jié)論

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

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

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

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