劉震宇 汪越雷 周龐睿

摘要：????? 在航空兵器自動化生產(chǎn)線上， 智能車運行軌跡的選擇對于提高生產(chǎn)線效率十分重要。 本文結(jié)合優(yōu)化算法數(shù)學模型的分析， 建立基于Dijkstra算法的自動尋路模型， 利用MATLAB對最優(yōu)結(jié)果進行求解。 最后， 就自動化物料加工過程中的復雜情形進行探討。

關鍵詞：???? 自動化生產(chǎn)線; 動態(tài)調(diào)度; 優(yōu)化算法; Dijkstra算法; MATLAB

中圖分類號：??? ?TJ08 文獻標識碼：??? A文章編號：??? ?1673-5048（2019）03-0094-05[SQ0]

0引言

工業(yè)4.0時代的航空兵器自動化生產(chǎn)線上， 很大一部分都采用了數(shù)字化無人車間， 車間中所用最多的就是智能車。 智能車運行軌跡的選擇對于提高生產(chǎn)線效率十分重要。 自動化生產(chǎn)線的智能車調(diào)度優(yōu)化算法常結(jié)合計算機神經(jīng)網(wǎng)絡進行分析。 圖1～2為智能車與自動化生產(chǎn)線系統(tǒng)示意圖。

目前， 國內(nèi)外許多研究人員已經(jīng)從模擬退火算法[1]、 蟻群算法[2]、 啟發(fā)式算法等神經(jīng)網(wǎng)絡典型算法研究移動機器人路徑規(guī)劃問題， 運用MATLAB建立移動機器人仿真系統(tǒng)， 輸入相應參數(shù)， 運行程序， 即可得到合理的機器人移動方案。 而自動化生產(chǎn)線上的智能車具有自身固有的特點： 移動路徑相對固定， 路徑方案與機床上下料時間和移動時間關系密切， 對于突發(fā)情況（如機床故障）具有臨時改變路徑的能力等， 因此需要有更加合理有效的神經(jīng)網(wǎng)絡算法對此類問題進行優(yōu)化。

1自動化加工生產(chǎn)線的數(shù)學模型

1.1問題理想化模型

機床加工生料時， 需要經(jīng)歷上料、 下料、 移動、 清洗等操作。 由于智能車勻速運動， 因此在機床間的移動時間與移動距離具有正比關系。 實際情況中， 上下料傳送帶既可以聯(lián)動， 也能獨立運動， 所以無需考慮送料擁堵問題; 由于程序設定一般已經(jīng)充分考慮了操作之間轉(zhuǎn)換的間隙， 因此也無需考慮時間間隔; 在開啟加工線之前， 認為各機床均處于閑置狀態(tài)， 智能車位于第一列機床兩側(cè)。

1.2生產(chǎn)線加工情況的討論

常見的自動化加工生產(chǎn)線中， 存在單工序生產(chǎn)線和多工序生產(chǎn)線兩種典型情況。 單工序生產(chǎn)線即為所有機床的加工工序一致， 智能車可以將生料移動到任何一臺機床上進行加工; 多工序生產(chǎn)線即為機床加工存在先后關系， 智能車需將生料依次放在多臺機床上進行加工才能完成任務。

根據(jù)以往研究工作得知[3]， 考慮到一臺智能車管理機床范圍有限， 至多只安排兩道工序同時進行加工， 因此將問題簡化為考察兩道工序下智能車的移動路徑優(yōu)化問題。

1.3生產(chǎn)線發(fā)生故障的討論

實際加工過程中， 常存在機器突發(fā)故障等問題， 需要臨時對智能車的行進路線進行調(diào)整， 以最大化提高生產(chǎn)效率。 為簡化問題， 考慮故障發(fā)生的概率服從二項分布， 在人工設置的故障點后用優(yōu)化算法進行擬合與調(diào)整， 得到相對最優(yōu)解。

2基于Dijkstra算法的智能車路徑優(yōu)化

2.1算法思路

Dijkstra算法由荷蘭計算機科學家狄克斯特拉于1959 年提出。 該算法是從一個頂點到其余各頂點的最短路徑算法， 解決的是有向圖中最短路徑問題。 該算法的主要特點是以起始點為中心向外層層擴展， 直到擴展到終點為止。 具體思路可以用圖3所示的流程圖表示。

2.2生產(chǎn)線上Dijkstra算法的應用

2.2.1單工序模型： 生產(chǎn)流程的抽象與簡化

單工序的智能車運行簡圖如圖4所示。 顯然， 智能車的調(diào)度有兩個子過程： 以“起始狀態(tài)+上料去程+空回程”為流程的初始上料過程; 以“下料去程+上料去程+空回程”為周期的上下料過程。

分別對兩個子過程建立初等數(shù)學模型[4]， 設過程1“起始狀態(tài)+上料去程+空回程”智能車總耗時Tp1; 設過程2“下料去程+上料去程+空回程”一個周期智能車總耗時Tp2; 設過程1+過程2為一個周期， 智能車總耗時Tp3;

顯然， 單工序加工的情況下， 智能車的運行軌跡具有周期性， 對于路徑優(yōu)化的限制條件相對較少。 單工序下不同加工系數(shù)T0/T1的值也會顯著改變生產(chǎn)線的加工效率， 具體表現(xiàn)如表2所示。

加工系數(shù)T0/T1代表平均上下料時間與平均移動時間之比， 運行效率代表機床的閑置率。 綜上， 需考慮將兩者的比值設置在合理區(qū)間內(nèi)， 可以使得單工序生產(chǎn)線的加工效率最高。

2.2.2多工序模型： 綜合評價參量K的確定與機床分配

對于多工序的流水線， 需要考慮機床數(shù)量和位置的分配問題。 建立數(shù)學模型， 通過比例因子K決定各工序使用機床的數(shù)量之比。 定義K=n1/n2， 即第一道工序與第二道工序使用機床數(shù)的比值。 從實際情況出發(fā)， 將連續(xù)的K離散化處理為5/3， 1， 3/5。

下面通過一個簡單的模型分析， 來確定最佳的第一、 第二道工序的分配方案。 為簡化問題， 可由T1和T2時間關系確定的機床數(shù)目分配， 以及這樣分配導致RGV在軌道上移動花費的實際時間mT。 定義兩個權重函數(shù)σ1和σ2， 且有σ1+σ2=1， σ1>0， σ2>0， 計算結(jié)果用綜合參數(shù)K表示：

對于m， 當n1=n2時有最小值， 而此時實際情況應該為T1和T2相差較大， 因此對這種情況的機器數(shù)目的分配比應當盡量靠近n1=n2， 即盡可能取距離最優(yōu)情況最近的分配比; 而當兩個工序在時間上相差較小時， 即T1和T2的比值較接近于1的時候， 考慮后者就少一些， 這個時候就可以近似而且合理地認為n1=n2為最優(yōu)解的存在前提。

（1） 當K=1

在K=1的情形下， 工序一和工序二均分配4臺機床。 根據(jù)排隊論理論， 為使系統(tǒng)空閑概率與逗留時間最短， 應使上端2， 4， 6， 8全部是同一種工序， 下端1， 3， 5， 7也全部是同一種工序。 這樣不難分析知， 流水線的工作效率與兩工序的加工時間有關。 設T2a， T2b分別為CNC加工完成第一道工序、 第二道工序所需時間， 一種方式是使偶數(shù)編號的機床加工工序一， 奇數(shù)編號的機床加工工序二， 其用時

T=2Te+5To+4Tc+3Tm1+T2a+T2b; 另一種方式是對調(diào)加工機床的工序， 其用時T=2To+5Te+4Tc+3Tm1+T2a+T2b， 因此得出結(jié)論： 先給處理時間長的機床下料。

（2） 當K=5/3或3/5

由于小車從1， 2之間出發(fā)， 且經(jīng)常往返于各節(jié)點之間， 因此在考慮依次排開的情況下， 優(yōu)先在2機床安排工序二的工件， 同時為了保證不同工序的機床交互的便利性， 考慮如圖6所示的排布方案。圖中矩形為工序一， 圓角矩形為工序二。

2.2.3多工序模型： 基于Dijkstra算法的多工序加工效率

完成了機床數(shù)量和位置的分配后， 便可以基于Dijkstra算法進行加工方案的設計了， 與單工序情況類似， 多工序需要考慮兩次加工過程和智能車轉(zhuǎn)移物料的時間。 當K=5/3時分別代入具體數(shù)據(jù)（T1=T2=15， Tm1=10）， 用MATLAB繪制多工序的智能車運行時空關系如圖7所示。

在多工序加工的情況下， 智能車的運行軌跡與加工時間以及智能車移動時間等參數(shù)有關， 對于路徑優(yōu)化的參數(shù)要求較高。 多工序下不同加工系數(shù)T2/T1的值也會顯著改變生產(chǎn)線的單位時間產(chǎn)出， 具體表現(xiàn)如表3所示。

T2/T1表示工序二和工序一的加工時間之比。 綜上， 需考慮將兩者的比值設置在合理區(qū)間內(nèi)， 可以使得單工序生產(chǎn)線的單位時間產(chǎn)出最高。

2.2.4故障模型： 二項分布下的故障應對方案

在實際加工過程中， 經(jīng)常由于機床故障需要臨時調(diào)整智能車的工作路線， 對于常見的故障模型， 考慮其發(fā)生的頻率為二項分布， 當故障發(fā)生頻率P～B（8， 0.01）時， 發(fā)生故障的概率可以近似如表4所示。

3結(jié)論

在工業(yè)4.0的背景之下， 除了航空兵器生產(chǎn)的質(zhì)量以外， 生產(chǎn)的效率也尤為關鍵， 本文以航空兵器的生產(chǎn)為背景， 討論了如何提高生產(chǎn)效率， 從航空兵器生產(chǎn)流水線的智能車調(diào)度問題入手， 著眼于方案優(yōu)化， 從單工序、 多工序和故障排查對簡單流水線的加工方案的確定給出了數(shù)學模型， 并基于Dijkstra算法進行計算機求解， 結(jié)果切實可行。

參考文獻：

[1] 裴以建， 楊亮亮， 楊超杰. 基于一種混合遺傳算法的移動機器人路徑規(guī)劃[J/OL]. 現(xiàn)代電子技術， 2019（2）： 183-186.（2019-01-22）[2019-03-04].https：∥doi.org/10.16652/j.issn.1004-373x.2019.02.042.

Pei Yijian， Yang Liangliang， Yang Chaojie. Path Planning of Mobile Robot Based on a Hybrid Genetic Algorithm [J/OL].? Modern Electronic Technology， 2019 （2）： 183-186. （2019-01-22）[2019-03-04].https：∥doi.org/10.16652/j.issn.1004-373x. 2019. 02.042.（in Chinese）

[2] 林偉民， 鄧三鵬， 祁宇明， 等. 基于蟻群算法的移動機器人路徑規(guī)劃研究[J]. 機械研究與應用， 2018， 31（4）： 144-145.

Lin Weimin， Deng Sanpeng， Qi Yuming， et al. Research on Path Planning of Mobile Robot Based on Ant Colony Algorithm[J].Machinery Research and Application， 2018， 31（4）： 144-145.（in Chinese）

[3] 于龍振.? 基于LinKernighan改進型算法的可視化TSP處理軟件的實現(xiàn)[D].青島： 青島大學， 2006.

Yu Longzhen. Implementation of Visualized TSP Processing Software Based on LinKernighan Improved Algorithm [D]. Qingdao： Qingdao University， 2006.（in Chinese）

[4] 邢海濤. 基于時間Petri網(wǎng)的小組軟件過程仿真建模研究[D].哈爾濱： 哈爾濱工程大學， 2005.

Xing Haitao. Research on Group Software Process Simulation Modeling Based on Time Petri Net[D]. Harbin： Harbin Engineering University， 2005.（in Chinese）

[5] 陳江紅， 李宏光. 基于Matlab環(huán)境的Petri網(wǎng)的仿真方法[J]. 微計算機信息， 2003（12）： 103-104.

Chen Jianghong， Li Hongguang. Simulation Method of Petri Net Based on Matlab Environment[J]. Microcomputer Information， 2003（12）： 103-104.（in Chinese）