基于貪心算法的智能RGV動態調度研究

王涵

摘 要：本文針對智能RGV的動態調度問題，根據貪心算法和回溯遍歷法在某種特殊情況下的動態調度模型和相應的求解算法。由于每個物料都只需一道工序而且可以在任意一臺CNC上完成加工，為了計算出RGV的最優動態調度方案，需要使得一定時間內加工系統加工出的物料數量最多，即使得加工一定數量的物料所需時間最短。采用貪心算法和回溯遍歷法，得到RGV的每一次工作指令都是局部最優解，即是使得完成當前各CNC的上料需求時間最短的調度方案。對每一步都采用局部最優解，在選擇的貪心策略不會對以后的狀態產生影響的條件下，即可得到全局最優解。

關鍵詞：智能RGV；貪心算法；回溯遍歷法；動態調度

引言

RGV，是有軌制導車輛（Rail Guided Vehicle）的英文縮寫，又叫有軌穿梭小車，RGV小車可用于各類高密度儲存方式的倉庫，小車通道可設計任意長，可提高整個倉庫儲存量，并且在操作時無需叉車駛入巷道，使其安全性會更高。在利用叉車無需進入巷道的優勢，配合小車在巷道中的快速運行，有效提高倉庫的運行效率。本文是研究RGV在直線軌道上往返的動態調度問題，并且考慮了多種情況，如CNC加工的物料只有一道工序、CNC加工的物料有兩道工序以及發生故障之后如何調度使得加工的物料最多等。

1模型準備

本文解決的問題是在一道工序物料加工作業，每臺CNC安裝同樣的刀具，物料可以在任一臺CNC上加工完成的情況下，在一定的時間T內最多可以加工多少物料。那么在考慮RGV動態規劃的情況下，對于目標函數和約束條件的給出較為困難。因此，為簡化模型，本文假設在生產第 個物件的情況下要在第i個階段對熟料進行上下料操作，這時需要考慮每一次RGV移動的時間和其上下料的時間之和 。

首先，可能在某一時刻有多個CNC需要進行上下料，必須對這些CNC的上下料順序進行排列，以達到Ti最少的目的。

其次，由于給奇數CNC上下料的時間與給偶數CNC上下料的時間不同，因此當與上述考慮上下料時間的和為最小時，即考慮局部最優的情況下，那么給定的T就是由局部最優的時間加上清洗熟料的時間、初始上料的時間以及VG可能等待的空閑時間之和。因此，在這種情況下，局部最優就可以代表的全局最優，實現RGV的動態規劃。下面給出最優規劃模型：

目標函數：min

約束條件：

2模型建立

由于模型中的約束條件所包含的情況較為復雜，為了求解出目標函數的最優解，采用貪心算法將對全局最優解的計算轉化為對所求問題的各個子問題的局部最優解的尋找。貪心算法采用逐步逼近最優解的思想，在選擇的貪心策略不會對以后的狀態產生影響的條件下，做出當前狀態下的局部最優策略，當RGV收到k臺CNC的上料需求信號，要對滿足這k臺CNC上料需求的所有可能次序安排所花費的移動時間以及上下料時間進行比較，選取最少的一種次序安排作為該子問題的局部最優解。通過每一步的貪心選擇，可得到整體的最優解，即加工完成數量n的物件所需的最短時間。

為了求出每個時刻的子問題的最優解，采用回溯遍歷法和MATLAB軟件得出使得RGV的移動時間及上下料時間之和最短的安排作為RGV對各CNC的上下料作業次序，即為RGV的動態調度方案。

3模型求解

根據表1中各組的作業參數，將其帶入建立的模型中，可以計算得出加工物料CNC的編號的循環路徑以及上下料的開始時間，結果如下表：

圖1到圖2表示的是三種情況下每一個CNC處的一個周期下的加工情況，縱坐標的每一個數字對應與第m個CNC，橫坐標為時間，單位為秒。

結論

本文解決的問題是在一道工序物料加工作業，每臺CNC安裝同樣的刀具，物料可以在任一臺CNC上加工完成的情況下，在一定的時間T內最多可以加工多少物料，將其簡化為求局部最優的問題，而這個局部最優的問題最后可以轉化為全局最優，如果直接考慮全局最優的化會使模型十分復雜。

參考文獻

[1] 王雷，蔡勁草 .基于可變重調度區間的柔性作業車間動態調度策略[J] .南京航空航天大學學報，2018，50（3）：397-403 .

[2] 吳云高.王萬良 基于遺傳算法的混合Flowshop.浙江工業大學