基于Dijkstra算法的航空兵器自動生產線動態調度算法的研究

劉震宇 汪越雷 周龐睿

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

關鍵詞：???? 自動化生產線; 動態調度; 優化算法; Dijkstra算法; MATLAB

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

0引言

工業4.0時代的航空兵器自動化生產線上， 很大一部分都采用了數字化無人車間， 車間中所用最多的就是智能車。 智能車運行軌跡的選擇對于提高生產線效率十分重要。 自動化生產線的智能車調度優化算法常結合計算機神經網絡進行分析。 圖1～2為智能車與自動化生產線系統示意圖。

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

1自動化加工生產線的數學模型

1.1問題理想化模型

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

1.2生產線加工情況的討論

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

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

1.3生產線發生故障的討論

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

2基于Dijkstra算法的智能車路徑優化

2.1算法思路

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

2.2生產線上Dijkstra算法的應用

2.2.1單工序模型： 生產流程的抽象與簡化

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

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

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

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

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

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

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

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

（1） 當K=1

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

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

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

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

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

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

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

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

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

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

3結論

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

參考文獻：

[1] 裴以建， 楊亮亮， 楊超杰. 基于一種混合遺傳算法的移動機器人路徑規劃[J/OL]. 現代電子技術， 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] 林偉民， 鄧三鵬， 祁宇明， 等. 基于蟻群算法的移動機器人路徑規劃研究[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處理軟件的實現[D].青島： 青島大學， 2006.

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

[4] 邢海濤. 基于時間Petri網的小組軟件過程仿真建模研究[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環境的Petri網的仿真方法[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）