貪心優(yōu)化的搜索算法在RGV動(dòng)態(tài)調(diào)度中的應(yīng)用

羅敏娜, 侍 嘯

(1. 沈陽師范大學(xué) 計(jì)算機(jī)與數(shù)學(xué)基礎(chǔ)教學(xué)部, 沈陽 110034; 2. 中國農(nóng)業(yè)科學(xué)院 農(nóng)業(yè)信息研究所, 北京 100081)

0 引 言

自動(dòng)化倉庫與制造系統(tǒng)是現(xiàn)代化的工業(yè)設(shè)備,隨著近年來控制工程、機(jī)械自動(dòng)化、人工智能等多個(gè)領(lǐng)域的飛速發(fā)展,物流等行業(yè)也開始向自動(dòng)化、智能化、無人化的方向發(fā)展,因此對(duì)智能加工系統(tǒng)工作效率的要求變得越來越高,同時(shí)對(duì)這類產(chǎn)品的需求也在不斷提升,在工廠制造與物流存儲(chǔ)等領(lǐng)域發(fā)揮著非常突出的作用。軌道引導(dǎo)車輛(rail guide vehicle, RGV)系統(tǒng)也因此出現(xiàn)。在整個(gè)系統(tǒng)中,環(huán)形軌道式導(dǎo)引小車系統(tǒng)[1]的工作運(yùn)輸效率是整個(gè)系統(tǒng)是否優(yōu)良的關(guān)鍵,優(yōu)良的調(diào)度策略,可以在極短的時(shí)間內(nèi)完成大量的工作,極大地節(jié)省人力與時(shí)間等資源。因此,優(yōu)良的動(dòng)態(tài)調(diào)度算法是整個(gè)系統(tǒng)的關(guān)鍵。

傳統(tǒng)用于解決自動(dòng)化系統(tǒng)的調(diào)度方法為先來先到算法[2],這種調(diào)度策略簡(jiǎn)單,快捷方便,并且能夠短時(shí)間選擇出較為合適的調(diào)度策略,但對(duì)于整個(gè)動(dòng)態(tài)系統(tǒng),其距離全局最優(yōu)調(diào)度策略相差甚遠(yuǎn),很難達(dá)到較高的最優(yōu)調(diào)度策略。用于尋找最優(yōu)解的算法有很多,最常見的算法比如廣度優(yōu)先搜索[3],通過對(duì)可能策略的不斷嘗試,直到尋找到最優(yōu)解,這種方法可以尋找到RGV在全局中的最優(yōu)調(diào)度,但對(duì)于一個(gè)需要長(zhǎng)時(shí)間運(yùn)行的RGV系統(tǒng),需要的計(jì)算量過大,有時(shí)超過了常規(guī)計(jì)算機(jī)的計(jì)算量,很難被實(shí)際應(yīng)用。因此,本文提出了一種使用貪心策略對(duì)廣度優(yōu)先搜索進(jìn)行優(yōu)化的新調(diào)度算法,通過貪心選擇最可能的情況,減少搜索的復(fù)雜度,從而在極短的時(shí)間內(nèi)完全調(diào)度,并盡可能地接近最優(yōu)狀態(tài)。在eM-Plant[4]平臺(tái)上進(jìn)行了仿真實(shí)驗(yàn),與先來優(yōu)先服務(wù)調(diào)度策略進(jìn)行比較,對(duì)貪心優(yōu)化算法的有效性進(jìn)行了充分的驗(yàn)證。

1 模型描述

以自動(dòng)化加工系統(tǒng)(圖1)為例,由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床(computer number controller,CNC)、1輛RGV、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。

圖1 自動(dòng)化加工系統(tǒng)示意圖Fig.1 Automated processing system schematic

RGV是一種無人操控駕駛、在固定軌道上自由運(yùn)作的智能車,RGV的通道可設(shè)計(jì)為任意長(zhǎng)度,從而提高整個(gè)倉庫的容量,并且操作時(shí)整個(gè)系統(tǒng)中無需叉車進(jìn)入,提高了整體的安全性[5]。利用其無需進(jìn)入巷道的優(yōu)勢(shì),再配合高速運(yùn)作在巷道中的小車,能夠有效地提高整個(gè)系統(tǒng)的效率。它根據(jù)指令能自動(dòng)控制移動(dòng)方向和距離,并自帶一個(gè)機(jī)械手臂、2只機(jī)械手爪和物料清洗槽,能夠完成上下料及清洗物料等作業(yè)任務(wù)[6]。因此,如何通過合理的調(diào)度規(guī)則,提高RGV的工作效率是急需解決的問題。

CNC又叫做電腦鑼,其實(shí)就是數(shù)控銑床,是新型加工技術(shù),主要工作是編制加工程序,即將原來手工活轉(zhuǎn)為電腦編程,可以在RGV將生料送達(dá)后,進(jìn)行加工。

主要解決的問題就是RGV小車在每個(gè)時(shí)間點(diǎn)進(jìn)行何種操作可以提高整個(gè)系統(tǒng)的效率。

2 貪心優(yōu)化的搜索算法

本文提出了一種基于貪心策略優(yōu)化后的搜索算法,可以在較短的時(shí)間內(nèi),接近最優(yōu)解的調(diào)度策略。算法過程如圖2所示。

2.1 相關(guān)準(zhǔn)備

2.1.1 先來先到服務(wù)

先來先到服務(wù)是一種傳統(tǒng)的計(jì)算機(jī)操作系統(tǒng)中的進(jìn)程調(diào)度算法,如果更早就緒的進(jìn)程位于緒隊(duì)列的前面,后就緒的進(jìn)程處在就緒隊(duì)列的尾部,那么先來先到服務(wù) (first come first service, FCFS)將就緒隊(duì)列的首進(jìn)程放入運(yùn)行狀態(tài)[7]。也就說,它只考慮進(jìn)程進(jìn)入就緒隊(duì)列的先后,而不考慮它的下一個(gè)CPU周期的長(zhǎng)短及其他因素。

圖2 貪心優(yōu)化的搜索調(diào)度流程圖Fig.2 Greedy optimization of the search scheduling flow chart

而其在RGV調(diào)度中的應(yīng)用,當(dāng)一個(gè)CNC處于未工作狀態(tài),其就向RGV發(fā)出請(qǐng)求,RGV根據(jù)請(qǐng)求的先后,先發(fā)出請(qǐng)求的優(yōu)先服務(wù)。

FCFS算法簡(jiǎn)單易行,是一種非搶占式策略,但性能卻不大好。

2.1.2 廣度優(yōu)先搜索

5E-APS智能全自動(dòng)制樣系統(tǒng)可實(shí)現(xiàn)自動(dòng)除鐵、輸送、稱重、破碎、縮分、干燥、制粉、廢樣回收、留樣轉(zhuǎn)運(yùn)及保證最小留樣質(zhì)量以上的各種煤樣的自動(dòng)封裝噴碼并對(duì)留樣稱重判別的功能，最終制樣出料樣品為一份6mm全水分煤樣、一份3mm存查樣、兩份0.2mm一般分析試樣,以上樣品均實(shí)現(xiàn)自動(dòng)封裝寫碼且存查樣、分析樣均通過各自轉(zhuǎn)運(yùn)皮帶機(jī)轉(zhuǎn)運(yùn)至樣品交接室，棄料自動(dòng)收集集中堆放。

寬度優(yōu)先搜索(又稱廣度優(yōu)先搜索)是最通用的圖遍歷搜索算法之一,同時(shí)很多著名的圖搜索算法也都是基于這一算法的改良。Dijkstra求單源最短路徑算法和Prim基于最小生成樹求最短路徑算法都采用了寬度優(yōu)先搜索的思想。寬度優(yōu)先搜索屬于一種盲目搜尋法[8],其核心思想是系統(tǒng)地展開圖中所有節(jié)點(diǎn)并且檢查,以找尋結(jié)果。它不再考慮某些節(jié)點(diǎn)的可能性,而是徹底地遍歷整張圖,直到找到結(jié)果為止。

廣度優(yōu)先搜索算法如今被廣泛的應(yīng)用在各類工業(yè)調(diào)度任務(wù)中。對(duì)于運(yùn)算規(guī)模較小的調(diào)度問題,廣度優(yōu)先搜索可以窮舉所有可能出現(xiàn)的情況,來選擇最優(yōu)解。但是廣度優(yōu)先搜索還是依賴與窮舉的思想,當(dāng)任務(wù)規(guī)模增大時(shí),所需要的時(shí)間也指數(shù)增大,在常見的調(diào)度任務(wù)中,例如汽車調(diào)度,人員調(diào)度等任務(wù)中,其可選擇的搜索路徑較少,廣度優(yōu)先搜索可以在很短的時(shí)間內(nèi)完成任務(wù)。但是本文解決的RGV調(diào)度中,每時(shí)每刻都有多種選擇,廣度優(yōu)先搜索無法在預(yù)期時(shí)間內(nèi)完成RGV的調(diào)度。

2.1.3 貪心算法

貪心算法(又稱貪婪算法)的基本思想是,在求解某一些問題時(shí),總是只看當(dāng)前情況,做出在目前最好的選擇[9]。在貪婪算法中,無需從整體最優(yōu)的目標(biāo)上加以考慮,需要求出的是某一時(shí)刻某種意義的局部最優(yōu)解。

由于考慮的片面性,貪心算法無法對(duì)所有問題求得整體最優(yōu)解[10]。算法核心是貪心策略的選擇,局部選擇的貪心策略需要獨(dú)立于其他狀態(tài),即當(dāng)前選擇與之前狀態(tài)無關(guān)且不影響之后的狀態(tài),只與當(dāng)前狀態(tài)有關(guān)。

2.2 貪心優(yōu)化分析

在計(jì)算機(jī)算法分析中,廣度優(yōu)先搜索的時(shí)間復(fù)雜度為O(V+E),其中V是節(jié)點(diǎn)的數(shù)目,E是變的數(shù)目,如圖3所示。

圖3 BFS在RGV調(diào)度中可能的情況Fig.3 Possible cases of BFS in RGV scheduling

BFS產(chǎn)生如此巨大計(jì)算量的原因是,RGV每次調(diào)度都有4種可選的新路徑,造成了時(shí)間指數(shù)增長(zhǎng)的情況,因此可以貪心選擇其中在全局動(dòng)態(tài)性上最可能成為最優(yōu)路徑的0～2條路徑(如圖4所示),作為下一步可能出現(xiàn)的情況。在圖4中,虛線部分為排除掉不進(jìn)行后續(xù)計(jì)算的路徑,這樣將大大減少計(jì)算耗時(shí),并且也能達(dá)到非常良好的效果[11]。

圖4 貪心選擇后可能出現(xiàn)的情況Fig.4 The case that may happen after greedy choice

2.3 貪心優(yōu)化

根據(jù)對(duì)每臺(tái)CNC當(dāng)前狀態(tài)與未來狀態(tài)之間關(guān)系的考慮,給每一個(gè)位置設(shè)計(jì)了一種對(duì)其最近2臺(tái)CNC未來狀態(tài)及周圍CNC的狀態(tài)進(jìn)行綜合考慮的性能評(píng)價(jià)標(biāo)準(zhǔn)[16]。在RGV每次操作后,更新4個(gè)位置的性能權(quán)值,權(quán)值基于2個(gè)超參數(shù)由其未來運(yùn)行后的狀態(tài)來定,即目標(biāo)最近2臺(tái)CNC的剩余時(shí)間減去運(yùn)動(dòng)花費(fèi)時(shí)間,再將其與做乘積運(yùn)算,最后加上與目標(biāo)附近4臺(tái)機(jī)器(對(duì)于1和4位置只有2臺(tái))運(yùn)動(dòng)后的狀態(tài)平均值的乘積[17]。超參數(shù)可以不斷擬合,使這種評(píng)價(jià)標(biāo)準(zhǔn)發(fā)揮良好的效果[12]。將上述的評(píng)價(jià)標(biāo)準(zhǔn)轉(zhuǎn)化為數(shù)學(xué)模型,即Wi的函數(shù)為

根據(jù)系統(tǒng)中RGV可能出現(xiàn)的路線進(jìn)行分析:

1) 當(dāng)RGV處于L時(shí), 并且距離其最近的2臺(tái)CNC上加工剩余時(shí)間為0的條件下, RGV原地不動(dòng)。

2) 當(dāng)距離RGV當(dāng)前位置最近的2臺(tái)CNC加工均未完成時(shí),RGV會(huì)在整個(gè)系統(tǒng)中選擇權(quán)重Wi最小的2條CNC路徑[13]。

3) 如果2)中選擇的2條路徑的權(quán)重Wi差值過大,將選擇權(quán)值較小的路徑。

基于此可得

如果abs(next 1-next 2)≥γ, next=max(next 1,next 2)

上述公式中各類參數(shù)說明如表1所示。

表1 符號(hào)說明表Table 1 Notation table

3 仿真與實(shí)驗(yàn)

基于本文提出的算法,利用eM-Plant進(jìn)行了仿真實(shí)驗(yàn)[14],仿真參數(shù)如表2所示。

將最終的調(diào)度方案與先來先到方案在8 h內(nèi)的產(chǎn)出量進(jìn)行了對(duì)比,如圖5所示。

表2 仿真參數(shù)Table 2 The simulation parameters

圖5 先來先到策略對(duì)比Fig.5 First come, first served to strategy comparison

從實(shí)驗(yàn)對(duì)比中可以發(fā)現(xiàn),2種策略在初期差距并不大,但由于先來先到屬于靜態(tài)策略,所以在調(diào)度系統(tǒng)中,當(dāng)前的狀態(tài)會(huì)對(duì)未來的狀態(tài)產(chǎn)生影響,屬于一種動(dòng)態(tài)系統(tǒng),系統(tǒng)長(zhǎng)時(shí)間運(yùn)行后,很難再達(dá)到較為理想的效果[18]。

先來先到模型,僅考慮了下一步操作最理想的狀態(tài),但當(dāng)前的最理想狀態(tài)對(duì)于全局來說可能并不優(yōu)秀,甚至有可能帶來負(fù)面影響,雖然其屬于非搶占式算法的簡(jiǎn)易型,但由于其不具有動(dòng)態(tài)與搶占能力,往往不是最好的選擇[19]。所以本文選擇了一種考慮了整個(gè)系統(tǒng)動(dòng)態(tài)性的貪心函數(shù)作為選擇的策略,并且結(jié)合搜索算法尋找到了非常接近最優(yōu)解的調(diào)度策略[15]。本文的貪心選擇函數(shù),很好地考慮了未來可能出現(xiàn)的情況對(duì)當(dāng)前的影響,并對(duì)當(dāng)前系統(tǒng)全局進(jìn)行了考慮,選擇了較為動(dòng)態(tài)的做法,因此可以達(dá)到更為優(yōu)秀的效果。

4 結(jié) 論

通過貪心優(yōu)化算法在RGV調(diào)度工作中進(jìn)行研究分析,智能自動(dòng)化系統(tǒng)不斷普及與智能自動(dòng)化技術(shù)的逐漸成熟,逐漸提高了自動(dòng)化系統(tǒng)性能的需求。因此,RGV系統(tǒng)的高效調(diào)度,對(duì)工業(yè)領(lǐng)域有著巨大幫助?；谶@些,提出了一種基于貪心思想優(yōu)化的搜索算法,并將其應(yīng)用在RGV調(diào)度系統(tǒng)中。通過對(duì)比實(shí)驗(yàn),分析了已有方法的缺點(diǎn)與本文的優(yōu)勢(shì),可以驗(yàn)證出在本問題的背景下,所提出的系統(tǒng)在效率與性能上明顯優(yōu)于已有的方法。

致謝:感謝2018年沈陽師范大學(xué)教學(xué)改革重點(diǎn)項(xiàng)目(JG2018-ZD23)的資助支持。