王涵

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

關(guān)鍵詞：智能RGV；貪心算法；回溯遍歷法；動態(tài)調(diào)度

引言

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

1模型準(zhǔn)備

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

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

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

目標(biāo)函數(shù)：min

約束條件：

2模型建立

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

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

3模型求解

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

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

結(jié)論

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

參考文獻(xiàn)

[1] 王雷，蔡勁草 .基于可變重調(diào)度區(qū)間的柔性作業(yè)車間動態(tài)調(diào)度策略[J] .南京航空航天大學(xué)學(xué)報，2018，50（3）：397-403 .

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