羅敏娜, 侍 嘯

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

0 引 言

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

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

1 模型描述

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

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

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

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

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

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

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

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

2.1.1 先來先到服務(wù)

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

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

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

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

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

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

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

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

2.1.3 貪心算法

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

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

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

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

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

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

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

2.3 貪心優(yōu)化

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

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

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

2) 當(dāng)距離RGV當(dāng)前位置最近的2臺CNC加工均未完成時,RGV會在整個系統(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 符號說明表Table 1 Notation table

3 仿真與實驗

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

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

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

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

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

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

4 結(jié) 論

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

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