基于蟻群—退火算法的RGV動態調度設計

金龍哲，張曉峰，曹維維，宋文韜，劉中南

(皖西學院，安徽 六安 237012)

0 引言

隨著現代社會的發展，智能工廠成為當今工業化生產的主流，其中，智能加工系統很大程度上決定工廠的生產效率。常見的工廠加工系統由數控機床(CNC)、在軌道上往復運作的自動小車(RGV)、小車工作的直線軌道、用于上下料的傳送帶等附屬設備組成。其中，RGV自動運作小車根據操作人員所下發的指令進行移動與轉向，一般的RGV小車攜帶1個機械手臂、2只機械手爪進行物料的抓取與投放，物料的清洗在RGV小車的清洗槽上完成。在目前市場上RGV調度中，往往采用人工實時監測及就近控線原則進行RGV調度控制，該控制方法對整個系統的預測性、生產效率較低。因此本文針對RGV智能調度問題，設計了1套合適的調度算法，與普通調度相比提高了整個RGV加工系統的工作效率。

1 RGV調度模型的建立

設有1個由8臺計算機數控機床(CNC)、1輛軌道式自動引導車(RGV)、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成的智能加工系統，RGV根據指令能自動控制移動方向和距離，并自帶1個機械手臂、2只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業任務。RGV排布如圖1所示。

圖1 RGV排布圖

RGV工作圖如圖2所示。已知CNC對同種物料的加工時間相等，RGV為同側CNC上下料及清洗的作業時間相同。因此在一定工時內，CNC的等待總時長越短，則CNC的利用率越高，加工的物料成品越多。可將CNC的等待時間最短的問題，轉化為RGV小車移動總路徑最短的問題。本文主要考慮無故障兩道工序加工的問題。無故障兩道工序加工指物料經過CNC有先后次序的兩次加工，使物料產出最大。

圖2 RGV工作圖

兩道加工工序首先要考慮CNC的分配問題，CNC的分配根據兩道加工工序的加工時間比例進行確定，確定了兩道加工工序分配到的CNC臺數后，要考慮怎樣進行安排，在安排時要考慮到RGV的移動距離以及兩側上下料的時間不同，安排完加工工序對應的CNC，要考慮RGV如何移動使系統效率最大化。

2 RGV調度算法設計

2.1 RGV基本調度原則

1)順序排隊算法[1]：在調度開始前，按照物料的完成時間從小到大排序，以此來調度小車。

2)就近算法：在原有的順序排隊算法的基礎上計算小車移動到加工物料的CNC的時間，將原有的物料完成時間與小車移動到加工物料的時間相加，得到在就近算法下，新的從小到大順序，即小車下一個會去接取時間最短的物料 。

3)CNC分配原則：由于第一道工序與第二道工序加工時間不同，所以在安裝加工刀具時應按照兩道工序的時間比例進行安裝。當時間比例在1左右時平均分配CNC數量，否則，需要時間長的工序分配較多數量CNC。

2.2 求解算法設計

2.2.1 目標函數的建立

在某調度下，CNC加工一批物料時，所有物料加工結束時的最大完工時間[2]。而這個時間越小，說明在此調度下加工這批物料的效率越高。因此，為了求得最優調度，需要將最大完成時間的目標函數設置為求其最小值，其數學表達式如下

Tk=min{max(Lk)}

(1)

Lk=tn

(2)

其中Lk表示在第k種調度下的最大完工時間，n表示一批次物料的數量，tn表示第n個物料完工的時間，公式(2)表示最大完工時間與最后一個物料的完工時間相等。由于物料個數、CNC臺數多，要求解Tk相當困難，并且Tk的解不止一種，對于目標多因素的求解方法，本文選擇運用基于蟻群算法改進的退火智能算法進行求解。

2.2.2 混合智能算法設計

模擬退火算法的優點是能以一定概率從局部最優解跳到全局最優解，但搜索效率不高，由于退火每輪只能保存1個相對最優解，在搜索結果的過程中容易困在歷史解中[3]。而群智能算法的優點是搜索效率高，搜索廣度大，搜索速度快，但群智能算法容易陷入局部最優解，難以找到真正的解。因此本文結合退火算法與群智能算法的優點，將蟻群算法與模擬退火算法結合得到新的混合算法，結合兩種特點，使搜索能力大幅度提高，解決RGV的動態調度問題。

本文模擬退火算法采用串行結構，蟻群算法采用并行搜索，從而提高了算法的優化性能，同時退火算法的概率突變性提升了蟻群算法的信息素更新能力，將搜索行為多樣化。具體步驟見圖3。

圖3 混合算法步驟圖

從圖3中可以看出，蟻群算法給整個算法流程圖提供初始接，模擬退火算法將得到的初始解進一步優化，依據Metropolis準則產生新解，蟻群算法隨著新街的變化產生新的信息素，最后整體算法進行最優解的搜索。可見，新的混合算法不但有群智能算法的高效率，也有模擬退火算法的搜索全局最優的特點。因此為了提高動態調度的算法效率，可以采用混合算法。

2.3 系統的仿真

設置第一道與第二道工序時間如表1所示。

表1 第一道與第二道工序時間比設置表

在確定好CNC分配個數后，將各個CNC的調度時間算出來，帶入混合智能算法，以公式(1)為目標函數，求解出調度原則，給出調度方案。將調度方案與普通方案進行對比，系統的作業效率可以為單位時間內系統加工物料數，經計算系統的作業效率見表2。

表2 系統的作業效率前后對比表

由表2可以看出系統的作業效率都有所提高，即本文的調度方案優于普通的就近原則調度。

3 結語

針對當前工業生產線上的加工系統，本文設計了一套基于蟻群-退火算法的RGV動態調度算法，并將傳統的就近原則調度方式的加工效率與本文的調度算法仿真后的加工效率進行對比，效率有明顯提高，可見本文算法的優越性。同樣本文的調度算法還可應用其他領域，例如：模具電極調度問題、公交車調度問題、港口貨物運輸問題等類型的動態調度問題。多維度的應用能力體現本文所涉及的調度算法極好的應變性與適應力。