基于Dijkstra算法的航空兵器自動(dòng)生產(chǎn)線動(dòng)態(tài)調(diào)度算法的研究

劉震宇 汪越雷 周龐睿

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

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

中圖分類號：??? ?TJ08 文獻(xiàn)標(biāo)識碼：??? A文章編號：??? ?1673-5048（2019）03-0094-05[SQ0]

0引言

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

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

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

1.1問題理想化模型

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

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

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

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

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

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

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

2.1算法思路

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

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

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

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

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

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

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

2.2.2多工序模型： 綜合評價(jià)參量K的確定與機(jī)床分配

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

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

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

（1） 當(dāng)K=1

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

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

（2） 當(dāng)K=5/3或3/5

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

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

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

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

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

2.2.4故障模型： 二項(xiàng)分布下的故障應(yīng)對方案

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

3結(jié)論

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

參考文獻(xiàn)：

[1] 裴以建， 楊亮亮， 楊超杰. 基于一種混合遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J/OL]. 現(xiàn)代電子技術(shù)， 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] 林偉民， 鄧三鵬， 祁宇明， 等. 基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 機(jī)械研究與應(yīng)用， 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改進(jìn)型算法的可視化TSP處理軟件的實(shí)現(xiàn)[D].青島： 青島大學(xué)， 2006.

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

[4] 邢海濤. 基于時(shí)間Petri網(wǎng)的小組軟件過程仿真建模研究[D].哈爾濱： 哈爾濱工程大學(xué)， 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]. 微計(jì)算機(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）