高 健，龍 偉，田大慶，李炎炎

（四川大學(xué) 制造科學(xué)與工程學(xué)院，成都 610065）

0 引言

航空發(fā)動機(jī)再制造不同于傳統(tǒng)的航空發(fā)動機(jī)生產(chǎn)制造，其具有多品種，小批量等特點(diǎn)，尤其對于發(fā)動機(jī)主件和附件的再制造，其工藝工序的多樣性程度和復(fù)雜程度十分突出，這與傳統(tǒng)的剛性離散制造系統(tǒng)依據(jù)輸入/輸出來作決策有著本質(zhì)的區(qū)別。當(dāng)我們把眾多型號發(fā)動機(jī)的傳統(tǒng)生產(chǎn)方式轉(zhuǎn)化為規(guī)?；芍貥?gòu)的制造模式時(shí)，這就要求其生產(chǎn)組織形態(tài)必須適應(yīng)經(jīng)常變化的作業(yè)過程。目前，面向系統(tǒng)的可重構(gòu)研究主要集中在以機(jī)器為模塊進(jìn)行制造系統(tǒng)的重構(gòu)[1]。

自動導(dǎo)航車(Automated Guided Vehicles,AGV)是一種自動化的無人駕駛的智能化搬運(yùn)設(shè)備,屬于移動式機(jī)器人系統(tǒng),能夠沿預(yù)先設(shè)定的路徑行駛,是現(xiàn)代計(jì)算機(jī)集成制造系統(tǒng)中的關(guān)鍵設(shè)備之一[2]?？芍貥?gòu)制造系統(tǒng)就是利用AGV的循跡特點(diǎn)進(jìn)行生產(chǎn)組織形態(tài)的重組，從而使得航空發(fā)動機(jī)再制造車間能夠適應(yīng)經(jīng)常變化的加工流程。目前這方面研究集中在AGV本身技術(shù)以及AGV作業(yè)規(guī)劃調(diào)度方面。

對于復(fù)雜再制造系統(tǒng)，其車間作業(yè)調(diào)度路徑的拓?fù)浣Y(jié)構(gòu)可以有多種選擇，其算法主要解決的是AGV小車從起點(diǎn)到目標(biāo)點(diǎn)的路徑問題[3]，主要有狀態(tài)空間法[4]、神經(jīng)網(wǎng)絡(luò)法[5]、柵格法[6,7]、免疫網(wǎng)絡(luò)算法[8]、粒子群算法[9]和遺傳算法[10]等。

但是，現(xiàn)有的拓?fù)湟?guī)劃理論和調(diào)度策略普遍存在著難以解決多目標(biāo)，多約束，很少涉及實(shí)時(shí)調(diào)度，依賴輸入/輸出進(jìn)行決策等問題：因此，研究探索能夠快速響應(yīng)生產(chǎn)形態(tài)變化和過程決策傳導(dǎo)的作業(yè)規(guī)劃調(diào)度理論是航空發(fā)動機(jī)再制造系統(tǒng)實(shí)現(xiàn)可重構(gòu)的重點(diǎn)和難點(diǎn)。

1 基于超立方路徑規(guī)劃的新方法

1.1 超立方的概念

本文提出的超立方路徑規(guī)劃思想，源于數(shù)學(xué)物理上的“超立方體”概念[11]，超立方體描述方法是尋找一個(gè)聚類的最小外接立方體，使其包含數(shù)據(jù)集中所有的數(shù)據(jù)點(diǎn)[12]。我們從超立方體中抽取一個(gè)胞粒作為基本立方體，如圖1（a）所示，由于它的八個(gè)角點(diǎn)可以通過多條路徑相連，于是可將每個(gè)角點(diǎn)都規(guī)為一個(gè)加工工位、倉儲貨架等。當(dāng)需要并行協(xié)同加工工位或倉儲貨架之間的作業(yè)流程時(shí)，我們可按一定的規(guī)則來定義連接在立方體上的角點(diǎn)。

圖1 在物流作業(yè)路徑中引入超立方概念

設(shè)兩個(gè)相鄰角點(diǎn)的連接為一個(gè)鏈接語句，并以“面”為基本單元，如圖1（a）中 0-1-2-3 的上平面和 4-5-6-7 的下平面。如果把一個(gè)鏈接語句，定義成兩個(gè)角點(diǎn)連接的“鏈接閥”，則一個(gè)基面四個(gè)角點(diǎn)的兩兩互連，可用圖1（b）的鏈接展開圖來表示。同時(shí)，第一平面的每一個(gè)角點(diǎn)都可以與第二平面的任一角點(diǎn)相連且每一種鏈接方式都有唯一展開圖與之對應(yīng)。如用圖1（a）所示的角點(diǎn)3和角點(diǎn) 4 之間的連線，將立方體上下兩基面連接起來，我們便可得到一種如圖2所示的立方體角點(diǎn)鏈接展開圖。

圖2 單胞粒上下基面角點(diǎn)的連接路徑

1.2 鏈接算法的簡單介紹

現(xiàn)規(guī)定：

設(shè)定一 設(shè)鏈接語句函數(shù)式為 link(x，y)，x為起始角點(diǎn)值，y為終止角點(diǎn)值，它們的三位二進(jìn)制表達(dá)式為：

設(shè)定二 設(shè) Box(i，j)為超立方角點(diǎn)鏈接閥，它的狀態(tài)對應(yīng)于鏈接語句link(x，y)的“位”狀態(tài)值，并定義：

當(dāng) Box(i，j)＝0 時(shí)，則表示i與i直鏈，或j與j直鏈；

當(dāng) Box(i，j)＝1時(shí)，則表示i與j交鏈，或j與i交鏈；

于是，link(x，y) 的位狀態(tài)可表示為：

例如，當(dāng)角點(diǎn) 0與角點(diǎn)1的鏈接，其 link(0,1)＝[10]，則有：

可見，Box(0,1)＝1，表示角點(diǎn)0與角點(diǎn)1交鏈；Box(0,1)＝0，表示角點(diǎn)0與角點(diǎn)1直鏈。

設(shè)定三 設(shè)鏈接語句的運(yùn)算規(guī)則為二進(jìn)制的“位加”運(yùn)算，即兩個(gè)二進(jìn)制同位相加后取其個(gè)位的值，并用運(yùn)算符“”來表示。根據(jù)定義，我們對圖2中上虛框所表示的第一基面角點(diǎn)的鏈接算法推導(dǎo)如下：

1）相同角點(diǎn)的直鏈語句：

2）不同角點(diǎn)的直鏈語句：

例如：

3）間隔角點(diǎn)的鏈接語句：

由于不同角點(diǎn)的直鏈語句具有可逆性，因而可以用它來生成間隔角點(diǎn)的鏈接狀態(tài)，即把相鄰角點(diǎn)的首尾狀態(tài)值連接后消去，可用“⊙”表示。通常，間隔角點(diǎn)的鏈接具有多條路徑可以選擇，如：

4）交叉角點(diǎn)的鏈接語句：

對于圖2中下虛框所表示的第二基面角點(diǎn)的鏈接算法，只需將角點(diǎn)值減去(k-1)×4 后（k 為立方體的基面數(shù)），套用上平面的鏈接算法，然后將上下兩個(gè)基面的鏈接值帶入交叉鏈接語句即可。其他基面也照此類推。

1.3 引入估價(jià)函數(shù)

由上述算法介紹得知，兩角點(diǎn)之間時(shí)常存在多條鏈接路徑，因此存在路徑最優(yōu)問題，選擇的依據(jù)通常有時(shí)間因素，距離因素，擁堵因素以及直角拐點(diǎn)因素等[13]，為方便起見，本文只引入距離估價(jià)函數(shù)以取得最優(yōu)解。引入笛卡爾坐標(biāo)系，保存每個(gè)角點(diǎn)的坐標(biāo)值。估價(jià)函數(shù)形式：

上述算法，我們把它定義為“基于超立方模型的路徑鏈接算法”。

2 調(diào)度流程

如圖3所示，根據(jù)車間實(shí)際情況設(shè)置節(jié)點(diǎn)布置位置，并提取節(jié)點(diǎn)笛卡爾坐標(biāo)值，設(shè)置不連通路徑，當(dāng)AGV小車接受任務(wù)時(shí)應(yīng)先根據(jù)任務(wù)的起始和終止點(diǎn)求出兩節(jié)點(diǎn)分別所在基面，以便得出鏈接路徑中共有多少交叉角點(diǎn)鏈接。

圖3 調(diào)度流程

根據(jù)調(diào)度算法求出的路徑不一定都符合車間的實(shí)際情況，此時(shí)就需要剔除原先設(shè)定的不連通路徑。每一條符合要求的路徑均由若干節(jié)點(diǎn)組成，每依次相鄰節(jié)點(diǎn)間均有一估價(jià)函數(shù)值，而這條路徑的估價(jià)函數(shù)值是所有節(jié)點(diǎn)函數(shù)值的總和，最優(yōu)路徑就是依據(jù)最小估價(jià)函數(shù)值來選擇。

3 調(diào)度算法模型與物理形態(tài)的轉(zhuǎn)換

我們可進(jìn)一步將圖2所示的鏈接規(guī)則，轉(zhuǎn)換為相應(yīng)的制造物流作業(yè)路徑連接的物理形態(tài)，為方便可行，我們將工位 2 與工位 3 的位置互換，將工位 6 與工位 7 的位置互換，圖 4就是采用交鏈語句來連接上下兩個(gè)基面的多工位路徑鏈接的物理形態(tài)示意圖。

圖4 超立方路徑的物理結(jié)構(gòu)

對于多基面問題，我們只需要在圖4的基礎(chǔ)上加以順延即可，如圖5所示。

圖5 多重超立方路徑的物理結(jié)構(gòu)

在此基礎(chǔ)上，根據(jù)航空發(fā)動機(jī)再制造車間特點(diǎn)，本文給出了車間布局的示意圖，如圖6所示。

圖6 航空發(fā)動機(jī)再制造車間布局示意圖

4 算例

例如某一航空發(fā)動機(jī)再制造車間布局如圖7所示。其中0-3節(jié)點(diǎn)為航空發(fā)動機(jī)主體再制造單元，4-11節(jié)點(diǎn)為物料配送中心入倉口，12-18節(jié)點(diǎn)為航空發(fā)動機(jī)控制器再制造區(qū)，現(xiàn)物流小車調(diào)度任務(wù)為從貨架3上取一零件送至工位11處。

具體處理方法如下：

1）提取每個(gè)角點(diǎn)坐標(biāo)信息，如表1所示，根據(jù)車間實(shí)際擺放情況，設(shè)定第一基面和第二基面之間只有0和4以及2和6可通，在同一基面內(nèi)各節(jié)點(diǎn)都可通；

表1 各角點(diǎn)笛卡爾坐標(biāo)

2）對于起始角點(diǎn)3，求的K=1，即在第一基面，終止角點(diǎn)4，求的K=2，即在第二基面；

3）起始角點(diǎn)和終止角點(diǎn)不在同一基面，且其中含有一個(gè)交叉角點(diǎn)鏈接；

4）剔除步驟1中設(shè)定的不連通路徑，根據(jù)超立方理論模型，共得出6種鏈接路徑，如表2所示；

表2 枚舉鏈接路徑

5）利用估價(jià)函數(shù)，求的每種路徑的函數(shù)值如表3所示；

表3 估計(jì)函數(shù)值

6）由表3得最優(yōu)路徑為第2種，其二進(jìn)制表述為：

其中：

link(3,4)=link[link(3,0) (1)]

link(3,0)=link(3,1)⊙link(1,0)=[0101]

所以link(3,4)=[01011]。

5 結(jié)論

盡管人們在互聯(lián)網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、集成電路、通信技術(shù)等領(lǐng)域，對超立方體拓?fù)浣Y(jié)構(gòu)及路徑理論進(jìn)行了大量研究，但本質(zhì)上大都側(cè)重在超立方體的全域“聚類點(diǎn)基元”的大規(guī)模并行處理的理論技術(shù)局面，需要進(jìn)行復(fù)雜的數(shù)學(xué)運(yùn)算處理。本文研究，通過“面基元”來構(gòu)造與可重構(gòu)制造物流模態(tài)相對應(yīng)的“網(wǎng)格結(jié)構(gòu)”，并提出了“超立方路徑的鏈接算法”，為航空發(fā)動機(jī)再制造車間的作業(yè)過程提供了實(shí)時(shí)調(diào)度，傳導(dǎo)敏化的新方法，本算法避免了全域搜索所帶來的計(jì)算量大的問題，利用人為設(shè)置路徑通斷，既進(jìn)一步增強(qiáng)了系統(tǒng)的可重構(gòu)性也強(qiáng)調(diào)了過程決策，但是更加普適，通用的超立方理論及其傳導(dǎo)模態(tài)還需要進(jìn)一步研究。

[1] 王曉勇,臧鐵鋼,陳富林.制造系統(tǒng)可重構(gòu)控制技術(shù)研究[J].制造業(yè)自動化,2007,11(29):23-27.

[2] 徐清.自動導(dǎo)引小車系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].蘇州:蘇州大學(xué),2006.

[3] 孫奇.AGV系統(tǒng)路徑規(guī)劃技術(shù)研究[D].浙江,浙江大學(xué),2012.

[4] 胡正興,李一民,詹躍東.自動導(dǎo)引小車局部智能避障的A*算法[J].昆明理工大學(xué)學(xué)報(bào),2005,30(5):51.

[5] 肖本賢,齊東流,劉海霞,等.動態(tài)環(huán)境中基于模糊神經(jīng)網(wǎng)絡(luò)的AGV路徑規(guī)劃[J].系統(tǒng)仿真學(xué)報(bào),2006,18(9):2401.

[6] 鄧高峰,張雪萍,劉彥萍.一種障礙環(huán)境下機(jī)器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用,2009,26(s),879-883.

[7] 李天成,孫樹棟,高揚(yáng).基于扇形柵格地圖的移動機(jī)器人全局路徑規(guī)劃[J].機(jī)器人,2010,32(4),547-552.

[8] 方慶館,黃建中.基于環(huán)境地圖的AGV路徑規(guī)劃免疫網(wǎng)絡(luò)算法研究[J].起重運(yùn)輸機(jī)械,2010,20(3):42-4.

[9] 邊培瑩,李德信,包寶軍,路燕.粒子群算法在生產(chǎn)物流調(diào)度中的應(yīng)用研[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(17):220-223.

[10] ZHAN Y u-dong,LUO Y ing.The goods-f low ing system AGV technology of Yuxi cigarette factory and the developmental research of AGV nationalization technology[C]∥IEEE International Vehicle Electronics Conference. Piscataway:IEEE Press,1999:425-428.

[11] 林崔琴,超立方圖和超立方有向圖的同構(gòu)因子分解[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),1992,32(3):24-29.

[12] 劉英帆,崔江濤.基于聯(lián)合聚類的超立方體高維索引[J].計(jì)算機(jī)科學(xué)與探索,2012,06(00).

[13] 賀麗娜.AGV 系統(tǒng)運(yùn)行路徑優(yōu)化技術(shù)研究[D].南京,南京航空航天大學(xué),2012.