基于貪心算法的智能RGV的動態調度策略

李勝成

摘? 要：一種智能加工系統由8臺計算機數控機床（CNC）、1輛軌道式自動引導車（RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成。文章通過研究RGV的選擇判斷規律，以一道工序無故障情況為例，在RGV需要選擇去向時采用貪心算法，這體現為RGV每次選擇去向時選擇運動時間與上下料時間之和最小的目標，將該過程定為所有判斷的原則。故可得出動態調度后每個CNC的總等待時間最少，將機床工作效率最大化。從而給出最優動態調度策略。

關鍵詞：動態調度;貪心算法;靈敏性分析

中圖分類號：O221 文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2020）06-0016-02

Abstract： An intelligent machining system consists of 8 computer numerical control （CNC） machine tools， 1 rail guide vehicle（RGV）， 1 RGV linear track， 1 feeding conveyor belt， 1 cutting conveyor belt and other ancillary equipment. In this paper， the selection and judgment rule of RGV is studied. Taking a working procedure with no fault as an example， greedy algorithm is adopted when RGV needs to select the direction， which is reflected in the minimum sum of movement time and loading and unloading time when RGV selects the direction， and this process is set as the principle of all judgments. Therefore， it can be concluded that the total waiting time of each CNC after dynamic scheduling is the least， and the working efficiency of the machine is maximized. The optimal dynamic scheduling strategy is given.

Keywords： dynamic scheduling; greedy algorithm; sensitivity analysis

1 概述

對智能加工系統建立RGV動態調度模型[1]，需使用

matlab軟件編程，通過判斷語句和循環語句實現RGV的狀態轉換和系統時間的推進，程序模擬的信息世界變量轉換要遵循現實世界不同情況下物體運行規律，通過matlab程序仿真實現過程和結果的輸出，并通過優化RGV工作狀態轉換原則來改善動態調度模型。

2 一道工序無故障情況

2.1 模型的建立

RGV具有的四個工作階段為：移動階段M、上下料階段F、清洗階段W、停止階段S[2]。

通過附件一所給系統作業流程，可總結出在一道工序無故障情況下各階段完成后可供選擇的階段線路圖（如圖1所示），系統總運行過程應由若干該子圖拼接而成。

RGV的移動階段M后必定為上下料階段F，上下料階段F后必定為清洗階段W，這兩個階段不需要進行判斷。RGV在清洗階段W后有兩種可能的情況：

（1）完成清洗階段的時間點沒有需求信號，RGV進入停止階段。

（2）若此時有需求信號，根據此時RGV的位置和信號位置判斷，又分為以下兩種情況：

若此時RGV與需求信號在同一列上，即可直接進行上下料工作。

若此時RGV與需求信號不在同一列，通過判斷決定接下來移動的方向與距離。

智能加工系統通電后，RGV位于CNC1和CNC2正中間的初始位置，所有CNC都處于空閑狀態。故RGV的第一步應為對所有CNC進行上料操作。我們發現上料側CNC一次上下料所需時間明顯小于下料側CNC，故優先對上料側CNC進行上料操作，則對CNC初始上料操作的先后順序如圖2所示。

在此基礎上，我們利用貪心算法[1]，建立一道工序無故障情況下RGV動態調度模型。

貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇，也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。故我們通過確定各個子階段的局部最優解來進行RGV的動態調度，即在RGV的清洗階段W和停止階段S完成后接收到物料已完成信號時進行動態調度。[3]

該動態調度的決策僅考慮當前情況且該決策無后效性。設某時刻RGV的位置為X0，RGV在該時刻同時接收到m個已完成信號，此時RGV進行去向判斷，判斷方法應為RGV到達該點的移動時間與上下料時間之和最小。設第p個已完成信號的橫向位置為xp，則該信號與RGV的距離i=X0-xp，即本次移動時間為tMi=t，RGV為該CNC一次上下料的時間為tFp=tF奇，上料側CNC

tF偶，下料側CNC。則RGV下一步的去向應為當tM+tF=mint+tFp時信號的發出地，子流程的決策完成。

基于該去向判斷方法可知，當優先于某物料下料的物料數為s，則一個CNC完成一個物料所需的等待時間twait=mint+tFp。當一個CNC八小時一共完成了n個成料和n'個半成品物料時，該CNC所需的總等待時間T為：

該情況下動態調度原則為每個CNC的總等待時間最少：

T=min

設tr為第r次上下料開始時間點，則tr+1表示第RGV執行上下料操作開始的時間點，他們之間相隔時間至少為：一次上下料時間+加工時間+清洗時間+移動時間，可用該遞推式表示tr+1?tr+tF1+tP+tW+tM。

各CNC八小時總工作過程的約束條件為：

其中n'為平均每個CNC完成的半成料數量。

2.2 模型的求解

定義一個需求矩陣[x]2×4，元素為0表示物料無下料需求，1表示有下料需求。在初始上料完成后[x]2×4為全0矩陣。n為完成的成料數，初值為0。迭代求解程序流程圖如圖3所示：

最終可求得當程序內的總時間到達八小時后，成料數n及各物料的上、下料時間。

3 結束語

本文針對一道工序的情況，建立了基于貪心算法的數學模型，并且利用matlab[4]求解了該模型。經過該方法調度后每個CNC的總等待時間最少，從而效率將最大化。對生產實際具有一定的借鑒作用。

參考文獻：

[1]周正昱.智能RGV的動態調度策略模型[J].南方農機，2018（23）：55-56.

[2]董軍軍.動態規劃算法與貪心算法的比較與分析[J].軟件導刊，2008（02）：129-130.

[3]王建玲，齊紫茜，何璐.基于蟻群算法的車輛調度問題[J].交通科技與經濟，2014，16（6）：37-39，94.

[4]卓金武，等.MATLAB在數學建模中的應用[M].北京：北京航空航天大學出版社，2011.