基于貪心算法的智能RGV動(dòng)態(tài)調(diào)度研究

王涵

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

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

引言

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

1模型準(zhǔn)備

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

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

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

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

約束條件：

2模型建立

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

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

3模型求解

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

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

結(jié)論

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

參考文獻(xiàn)

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

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