孟芳汀 李慶祥 付輝

摘 要：本文運(yùn)用有向線段旅行商，動(dòng)態(tài)規(guī)劃，組合調(diào)度等方法解決了題RGV動(dòng)態(tài)調(diào)度模型的問題。分析了故障影響生產(chǎn)結(jié)果的情況，進(jìn)行對靜態(tài)模型的分析，對動(dòng)態(tài)模型的仿真，根據(jù)動(dòng)態(tài)靜態(tài)模型的分析，確定所述情況下的調(diào)度模型。

關(guān)鍵詞：向線段旅行商；動(dòng)態(tài)規(guī)劃；組合調(diào)度；matlab仿真求解

隨著科技的進(jìn)步，生產(chǎn)過程的自動(dòng)化程度越來越高，更多的大型企業(yè)傾向于選擇智能加工系統(tǒng)代替人力進(jìn)行生產(chǎn)加工，智能RGV就是典型的工業(yè)機(jī)器人中的一種。RGV通過接受數(shù)控機(jī)床的指令進(jìn)行移動(dòng)，并完成上下料和清洗作業(yè)的機(jī)器。本文RGV是一種裝載有機(jī)械手，清洗槽的智能有軌制導(dǎo)小車，本文是針對較為簡單的工業(yè)加工流程進(jìn)行數(shù)學(xué)模型求解，即一臺RGV為8臺CNC服務(wù)，且每次作業(yè)的物料只需要在一臺CNC進(jìn)行一道加工工序；兩道工序的物料加工作業(yè)情況，每個(gè)物料的第一和第二道工序分別由兩臺不同的CNC依次加工完成，以下是對數(shù)學(xué)模型的具體求解過程。

首先對所述問題進(jìn)行分類討論。在只有一道加工的情況下，通過有向線段旅行商和對比分析的方法給出RGV路線的最短時(shí)間路線。通過運(yùn)用單片機(jī)的仿真發(fā)現(xiàn)并不是簡單循環(huán)結(jié)構(gòu)，RGV是在收到信號后才會到有需求的數(shù)控機(jī)床的位置，這樣必然會導(dǎo)致一個(gè)時(shí)間差，致使前一個(gè)數(shù)控機(jī)床與后一個(gè)數(shù)控機(jī)床的開始進(jìn)行操作的時(shí)間會越來越大。再一次對模型進(jìn)行討論，在確定初始順序的基礎(chǔ)上，添加插隊(duì)機(jī)制，即RGV取去最先發(fā)出需求指令的數(shù)控機(jī)床。兩道加工工序的情況，取各自加工時(shí)間的倒數(shù)作為節(jié)拍，進(jìn)行同期化處理，安排機(jī)器的分布，進(jìn)而得出調(diào)度安排?？紤]到工序的先后關(guān)系，子問題在一次路線中被多次考慮，建立目標(biāo)調(diào)度優(yōu)化模型。目標(biāo)函數(shù)為Z=min max（ek）， ，xik為0/1變量，表示工序wk是否選擇CNC#i進(jìn)行加工。

1、一道工序的物料加工作業(yè)的討論求解

首先采用動(dòng)態(tài)規(guī)劃[1]的方法進(jìn)行理論分析。第二個(gè)等待的時(shí)間等于上一個(gè)的總時(shí)間加上它上下料的時(shí)間和清洗作業(yè)的時(shí)間再加上RGV移動(dòng)一個(gè)單位長度的時(shí)間，即tk+1=tk+ur+tm1（其中ur=t上下料+t清洗作業(yè)），所求的最短時(shí)間設(shè)為A（tq，0），兩個(gè)階段的傳遞最短時(shí)間為T=（tk+1，tk），所以A（tq，0）=min{T=（tk+1，tk），tk}。

RGV在完成一項(xiàng)作業(yè)任務(wù)后，立即判別執(zhí)行下一個(gè)作業(yè)指令。如果沒有接到其他的作業(yè)指令，則RGV就在原地等待直到下一個(gè)作業(yè)指令。再基于任務(wù)1的分析可知，智能小車RGV只需要在CNC#1發(fā)出換料的信號之前，回到初始位置即可，這樣CNC#1需要等待的時(shí)間是最小值，然后CNC#2—CNC#8因?yàn)樯舷铝系臅r(shí)間差依次發(fā)出信號。

從CNC#1出發(fā)，最后依據(jù)CNC#2發(fā)出信號，智能小車回到初始位置的路線有很多種方式。在此基礎(chǔ)上只需要滿足在RGV給8個(gè)數(shù)控機(jī)床完成換料的時(shí)間，小于CNC#1對物件操作的時(shí)間即可。

實(shí)際上，RGV運(yùn)動(dòng)的形式可以分為兩大類：閉環(huán)圈型或按照CNC的編號順序，直線式的回到初始位置。對于第一種閉環(huán)圈型的路線，可以舉個(gè)簡單的例子闡述，假如RGV的路線按環(huán)形排布，將#3和#6交換，易知初始位置到#3的順序路線，比到6#的路線短，同樣的邏輯，將#7與#4交換，路線也會更短，最后得到效果最好的結(jié)果，即路徑最短。

第二種按編號的路線，第二種方式從初始位置開始，對兩側(cè)的數(shù)控機(jī)床進(jìn)行分配。這種方式，可以看作是在初始點(diǎn)開始進(jìn)行路線，把剩余的運(yùn)作點(diǎn)，看作隨機(jī)分布。初始點(diǎn)最先上料，則初始點(diǎn)應(yīng)最先發(fā)出信號，將RGV從它終止的點(diǎn)召回。因此，采用有向線段的旅行商算法[2]進(jìn)行計(jì)算，得出等待時(shí)間最少的結(jié)論：RGV小車從#1出發(fā)，依次經(jīng)過#2，#3，#4，#5，#6，#7，#8，然后#1優(yōu)先完成，RGV收到信號，回到初始點(diǎn)（#1）。

對兩種不同的調(diào)度路線分析以后，發(fā)現(xiàn)按照編號順序的路線進(jìn)行安排，這種方式的等待時(shí)間是最小值，但是很明顯，RGV小車收到初始點(diǎn)的數(shù)控機(jī)床發(fā)出的信號，再從最遠(yuǎn)的位置，花費(fèi)最長的時(shí)間是不合理的。因此，大膽假設(shè)，假設(shè)數(shù)控機(jī)床第一次布料為人工布料，布料順序?yàn)?1，#3，#4，#5，#6，#7，#8，#2。這種方式既利用了等待時(shí)間最小，RGV智能小車也不用接受信號后從最遠(yuǎn)位置開始移動(dòng)。因?yàn)榧庸は到y(tǒng)的調(diào)度特性與單片機(jī)相同，所以對數(shù)控機(jī)床按路線設(shè)計(jì)優(yōu)先級。即使出現(xiàn)數(shù)控機(jī)床同時(shí)對RGV發(fā)出需求指令（即中斷請求信號）的情況，也不會打亂原始路線安排。

值得注意的一點(diǎn)是，在這里僅考慮了RGV行走路線不同造成的差異。

運(yùn)用單片機(jī)仿真效果圖可以發(fā)現(xiàn)，按照固定的順序進(jìn)行循環(huán)，循環(huán)的周期是逐漸增大的

再次對模型進(jìn)行分析，發(fā)現(xiàn)無論路線安排怎么被安排，時(shí)間的消耗不會是簡單的循環(huán)結(jié)構(gòu)。小車對不同的數(shù)控機(jī)床操作的時(shí)候，由于RGV是在收到信號后才會到有需求的數(shù)控機(jī)床的位置，這樣必然會導(dǎo)致一個(gè)時(shí)間差，致使前一個(gè)數(shù)控機(jī)床與后一個(gè)數(shù)控機(jī)床的開始進(jìn)行操作的時(shí)間會越來越大，更加不滿足循環(huán)的要求。

2、兩道工序的物料加工作業(yè)的討論求解

對于只有一道加工工序的問題，只需要考慮時(shí)間安排進(jìn)行調(diào)度，不多過多論述，下面對于需要兩道加工工序的問題進(jìn)行進(jìn)一步求解。由問題分析可知，此問題運(yùn)用動(dòng)態(tài)規(guī)劃最為合適。首先考慮工序存在的先后關(guān)系。物件必須經(jīng)歷第一道工序才可以經(jīng)過第二道工序，而是否經(jīng)歷第二道工序?qū)Φ谝坏拦ば虿]有關(guān)系，即后無效性，后面的決策對不會影響前面的。其次，存在重疊子問題，子問題在一次一次的路線行走過程中會多次被使用。此種情況建立調(diào)度目標(biāo)優(yōu)化模型[3]。設(shè)目標(biāo)函數(shù)為 = min max（ek）， ，xik為0/1變量，表示工序wk是否選擇 進(jìn)行加工。易知，兩道加工工序的時(shí)間函數(shù)為ek = sk + Tik，且時(shí)間函數(shù)具有約束：Ek ≤ sk + 1。

兩道工序加工的問題流程其實(shí)很明顯，對數(shù)控機(jī)床進(jìn)行上料以后，首先需要經(jīng)歷第一道工序，其次第二道工序，最后清洗作業(yè)下料。

令S1={進(jìn)行第一道工序的數(shù)控機(jī)床}，S2={進(jìn)行第二一道工序的數(shù)控機(jī)床}依次尋找配對關(guān)系，每個(gè)工序的節(jié)拍為Ri = 1/ti（ti為工序進(jìn)行的時(shí)間， 取1，2）使一二道工序的節(jié)拍相等或成倍，即工藝同期化。為了不使一二道工序之間的半成品出現(xiàn)堆積情況，影響生產(chǎn)，則假設(shè)第二道工序有略比第一道工序高的優(yōu)先等級。因此得出一二道工序兩和的分布關(guān)系，以此為基準(zhǔn)進(jìn)行接下來的機(jī)械化生產(chǎn)。

總結(jié)：

本文中運(yùn)用了matlab軟件對所收集到的數(shù)據(jù)進(jìn)行了初步檢驗(yàn)，主要使用了有向線段旅行商算法和動(dòng)態(tài)規(guī)劃的方法，再結(jié)合組合調(diào)度的方法，較為合理地研究了RGV動(dòng)態(tài)調(diào)度模型的建立問題，給出了比較客觀的結(jié)論，為智能加工系統(tǒng)的合理安排提供了科學(xué)的理論依據(jù)，雖然文章中針對問題有較為全面的論述，但是卻還依然存在一些問題，例如未考慮機(jī)器故障的情況，此外，實(shí)際情況中有許多復(fù)雜的情況，所述的模型也就具有局限性。

參考文獻(xiàn)

[1] 姜啟源，謝金星.數(shù)學(xué)模型（第四版）：高等教育出版社.2010年。

[2] 司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用：國防工業(yè)出版社.2011年。

[3] 韓中庚.數(shù)學(xué)建模方法及其應(yīng)用（第二版）：高等教育出版社.2005年。