基于蟻群—退火算法的RGV動(dòng)態(tài)調(diào)度設(shè)計(jì)

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

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

0 引言

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

1 RGV調(diào)度模型的建立

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

圖1 RGV排布圖

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

圖2 RGV工作圖

兩道加工工序首先要考慮CNC的分配問題，CNC的分配根據(jù)兩道加工工序的加工時(shí)間比例進(jìn)行確定，確定了兩道加工工序分配到的CNC臺(tái)數(shù)后，要考慮怎樣進(jìn)行安排，在安排時(shí)要考慮到RGV的移動(dòng)距離以及兩側(cè)上下料的時(shí)間不同，安排完加工工序?qū)?yīng)的CNC，要考慮RGV如何移動(dòng)使系統(tǒng)效率最大化。

2 RGV調(diào)度算法設(shè)計(jì)

2.1 RGV基本調(diào)度原則

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

2)就近算法：在原有的順序排隊(duì)算法的基礎(chǔ)上計(jì)算小車移動(dòng)到加工物料的CNC的時(shí)間，將原有的物料完成時(shí)間與小車移動(dòng)到加工物料的時(shí)間相加，得到在就近算法下，新的從小到大順序，即小車下一個(gè)會(huì)去接取時(shí)間最短的物料 。

3)CNC分配原則：由于第一道工序與第二道工序加工時(shí)間不同，所以在安裝加工刀具時(shí)應(yīng)按照兩道工序的時(shí)間比例進(jìn)行安裝。當(dāng)時(shí)間比例在1左右時(shí)平均分配CNC數(shù)量，否則，需要時(shí)間長(zhǎng)的工序分配較多數(shù)量CNC。

2.2 求解算法設(shè)計(jì)

2.2.1 目標(biāo)函數(shù)的建立

在某調(diào)度下，CNC加工一批物料時(shí)，所有物料加工結(jié)束時(shí)的最大完工時(shí)間[2]。而這個(gè)時(shí)間越小，說明在此調(diào)度下加工這批物料的效率越高。因此，為了求得最優(yōu)調(diào)度，需要將最大完成時(shí)間的目標(biāo)函數(shù)設(shè)置為求其最小值，其數(shù)學(xué)表達(dá)式如下

Tk=min{max(Lk)}

(1)

Lk=tn

(2)

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

2.2.2 混合智能算法設(shè)計(jì)

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

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

圖3 混合算法步驟圖

從圖3中可以看出，蟻群算法給整個(gè)算法流程圖提供初始接，模擬退火算法將得到的初始解進(jìn)一步優(yōu)化，依據(jù)Metropolis準(zhǔn)則產(chǎn)生新解，蟻群算法隨著新街的變化產(chǎn)生新的信息素，最后整體算法進(jìn)行最優(yōu)解的搜索。可見，新的混合算法不但有群智能算法的高效率，也有模擬退火算法的搜索全局最優(yōu)的特點(diǎn)。因此為了提高動(dòng)態(tài)調(diào)度的算法效率，可以采用混合算法。

2.3 系統(tǒng)的仿真

設(shè)置第一道與第二道工序時(shí)間如表1所示。

表1 第一道與第二道工序時(shí)間比設(shè)置表

在確定好CNC分配個(gè)數(shù)后，將各個(gè)CNC的調(diào)度時(shí)間算出來，帶入混合智能算法，以公式(1)為目標(biāo)函數(shù)，求解出調(diào)度原則，給出調(diào)度方案。將調(diào)度方案與普通方案進(jìn)行對(duì)比，系統(tǒng)的作業(yè)效率可以為單位時(shí)間內(nèi)系統(tǒng)加工物料數(shù)，經(jīng)計(jì)算系統(tǒng)的作業(yè)效率見表2。

表2 系統(tǒng)的作業(yè)效率前后對(duì)比表

由表2可以看出系統(tǒng)的作業(yè)效率都有所提高，即本文的調(diào)度方案優(yōu)于普通的就近原則調(diào)度。

3 結(jié)語(yǔ)

針對(duì)當(dāng)前工業(yè)生產(chǎn)線上的加工系統(tǒng)，本文設(shè)計(jì)了一套基于蟻群-退火算法的RGV動(dòng)態(tài)調(diào)度算法，并將傳統(tǒng)的就近原則調(diào)度方式的加工效率與本文的調(diào)度算法仿真后的加工效率進(jìn)行對(duì)比，效率有明顯提高，可見本文算法的優(yōu)越性。同樣本文的調(diào)度算法還可應(yīng)用其他領(lǐng)域，例如：模具電極調(diào)度問題、公交車調(diào)度問題、港口貨物運(yùn)輸問題等類型的動(dòng)態(tài)調(diào)度問題。多維度的應(yīng)用能力體現(xiàn)本文所涉及的調(diào)度算法極好的應(yīng)變性與適應(yīng)力。