結(jié)合貪心策略的RGV動(dòng)態(tài)規(guī)劃調(diào)度模型

丁飛陽(yáng) 張逸博 邱洪斌 陳勇

（浙江工業(yè)大學(xué)機(jī)械工程學(xué)院 浙江省杭州市 310032）

隨著控制工程、信息技術(shù)、機(jī)電一體化等多個(gè)領(lǐng)域的快速發(fā)展，工業(yè)與新興制造業(yè)開(kāi)始向自動(dòng)化、無(wú)人化、智能化發(fā)展，RGV（railguidevehicle）軌道式自動(dòng)引導(dǎo)車作為一種集各種高新技術(shù)于一體可自主運(yùn)行的系統(tǒng)，被廣泛應(yīng)用于現(xiàn)代化生產(chǎn)流水線中。RGV可用于各類高密度儲(chǔ)存方式的倉(cāng)庫(kù)，其通道可設(shè)計(jì)成任意長(zhǎng)。使用RGV 可以提高整個(gè)倉(cāng)庫(kù)儲(chǔ)存量，并且代替?zhèn)鹘y(tǒng)叉車駛?cè)胂锏?，使其安全性更高。RGV 的應(yīng)用可以有效提高倉(cāng)庫(kù)的運(yùn)行效率，并且可以十分方便地與其他物流系統(tǒng)實(shí)現(xiàn)自動(dòng)連接，按照計(jì)劃進(jìn)行物料的輸送。

如何合理調(diào)度RGV，提高 RGV 系統(tǒng)的運(yùn)行效率，是促進(jìn)制造業(yè)高速發(fā)展的一個(gè)重要問(wèn)題。目前有劉豐瑞等人提出的基于各種模型而形成的高效率調(diào)度策略[1]；Liu YK 等人研究了RGV-CNC 系統(tǒng)的作業(yè)策略[2]；Dotoli M 和Fanti MP 研究了RGV 系統(tǒng)的死鎖[3]；馮倩倩等人針對(duì)兩道工序的調(diào)度問(wèn)題，以CNC 任務(wù)分配和RGV 路徑為決策變量，以物料剩余加工時(shí)間和RGV 狀態(tài)建立了對(duì)應(yīng)的數(shù)學(xué)模型[4]；江唯等人建立了以RGV 路徑最短和移動(dòng)過(guò)程中堵塞最少為目標(biāo)的優(yōu)化模型[5]；張明鵬等人以RGV 移動(dòng)用時(shí)最短和RGV等待與工作時(shí)間最短為目標(biāo)，得到了魯棒性較好的調(diào)度策略[6]；徐曉龍得出了RGV 在CNC 加工一道和兩道工序情況下的最優(yōu)路徑[7]。

針對(duì)本文相同或類似背景問(wèn)題，也已經(jīng)有許多人建立了各式的算法和模型。牛藝璇設(shè)計(jì)了混合編碼粒子群優(yōu)化的約束優(yōu)化模型，雖然求解速度塊，但是推廣性差，對(duì)于更為復(fù)雜的調(diào)度情況其搜索精度會(huì)下降，容易陷入局部最優(yōu)解或者無(wú)法得到可行解[8]；朱志斌等人設(shè)計(jì)了基于工序編碼的粒子群算法，但是求解得到一個(gè)班次內(nèi)的加工總數(shù)并不理想[9]；李昊哲基于對(duì)蟻群算法的優(yōu)化，提出了優(yōu)秀指標(biāo)的概念，利用指標(biāo)的歸一化協(xié)助判定最優(yōu)調(diào)度策略并構(gòu)建了模型，但是模型中的RGV 無(wú)法在CNC 完成前或完成時(shí)到達(dá)上下料處，造成了時(shí)間浪費(fèi)[10]；田繼宏等人利用最短作業(yè)優(yōu)先調(diào)度算法、遺傳算法以及輪盤賭算法設(shè)計(jì)了模型，最后得到的調(diào)度策略中優(yōu)先度僅依據(jù)單次作業(yè)執(zhí)行的時(shí)間排序，在一些特殊情況下RGV 可能會(huì)比實(shí)際需求耗費(fèi)多余的時(shí)間進(jìn)行移動(dòng)[11]；賈艷武等人使用最短路徑法，根據(jù)線性規(guī)劃建立了具有通用性的優(yōu)化模型，但是在模型中出于清洗環(huán)節(jié)耗時(shí)相對(duì)較短而將其忽略了，導(dǎo)致最后調(diào)度策略與實(shí)際存在偏差[12]。

本文通過(guò)引入最短距離原則和盡快響應(yīng)原則的貪心策略，對(duì)建立的動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型進(jìn)行改進(jìn)，加速了解空間的搜索進(jìn)程，在保證結(jié)果可靠性的同時(shí)加快了算法的求解效率，提高了模型的實(shí)用性。

1 問(wèn)題描述及分析

本文研究的問(wèn)題如下，有一個(gè)智能加工系統(tǒng)如圖1所示，由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（以下簡(jiǎn)稱CNC）、1 輛軌道式自動(dòng)引導(dǎo)車（以下簡(jiǎn)稱RGV）、1 條RGV 直線軌道、1 條上料傳送帶、1 條下料傳送帶等附屬設(shè)備組成。RGV 的軌道兩邊等距分布四臺(tái)數(shù)控機(jī)床。其中每臺(tái)CNC 只能同時(shí)加工一個(gè)物料。RGV 根據(jù)指令能自動(dòng)控制移動(dòng)方向和距離，并自帶一個(gè)機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，兩只機(jī)械手可各自抓取一個(gè)物料完成上下料作業(yè)，CNC 加工完成的熟料經(jīng)過(guò)清洗放至下料傳送帶即視為加工完成。RGV 在上下料、清洗過(guò)程中均不能移動(dòng)。本文研究在僅一道工序情況下使加工完成一定數(shù)量物料用時(shí)最短的RGV 調(diào)度策略。

圖1：智能加工系統(tǒng)示意圖

對(duì)RGV 工作流程進(jìn)行分析，可以發(fā)現(xiàn)：除了最開(kāi)始的階段只需要給8 臺(tái)CNC 上生料但不需要清洗環(huán)節(jié)，剩下的工作流程中，對(duì)于RGV 車而言始終都是上下料、清洗、等待（也可以不等待，即等待時(shí)間為0）、移動(dòng)四個(gè)流程的不斷重復(fù)，從而可根據(jù)每個(gè)成料加工完成的時(shí)刻將整個(gè)工作流程劃分為一個(gè)個(gè)相似的階段，每個(gè)階段都是一個(gè)子問(wèn)題。而這些子問(wèn)題滿足重疊性，因此可以嘗試采用動(dòng)態(tài)規(guī)劃的數(shù)學(xué)思想在給定一個(gè)初始階段的規(guī)劃方案后對(duì)后續(xù)的調(diào)度進(jìn)行規(guī)劃，找到最優(yōu)的調(diào)度策略。

2 建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型

2.1 模型假設(shè)

（1）假設(shè)RGV 車前一階段的狀態(tài)只對(duì)相鄰的后一階段的狀態(tài)產(chǎn)生影響，即無(wú)后效性。因?yàn)閷?shí)際生產(chǎn)過(guò)程中有較多不可控因素?zé)o法被狀態(tài)變量概括，從而使?fàn)顟B(tài)變量失去無(wú)后效性，導(dǎo)致動(dòng)態(tài)規(guī)劃模型失效；

（2）假設(shè)導(dǎo)軌兩側(cè)CNC 等距排列，間隔距離記為一個(gè)單位，且編號(hào)如圖1所示；

（3）假設(shè)作業(yè)過(guò)程中RGV 車和CNC 均不發(fā)生故障；

（4）假設(shè)RGV 車移動(dòng)過(guò)程不能中斷。

2.2 符號(hào)說(shuō)明

如表1所示。

表1：符號(hào)說(shuō)明表

2.3 階段劃分

設(shè)需要加工n 個(gè)物料，由此前的分析，RGV 車始終都是上下料、清洗、等待、移動(dòng)四個(gè)流程的不斷重復(fù)且每個(gè)階段都完成了一個(gè)物料的加工過(guò)程，從而可以將整個(gè)過(guò)程劃分為n 個(gè)階段。每個(gè)階段內(nèi)RGV 車都是完成上下料、清洗、等待、移動(dòng)四個(gè)流程，如圖2所示。

圖2：加工階段劃分示意圖

2.4 確定狀態(tài)變量

對(duì)于每一個(gè)階段，其狀態(tài)就是這個(gè)階段開(kāi)始時(shí)RGV 所在位置以及階段的起始時(shí)刻。這里不妨用RGV 車所在機(jī)床編號(hào)表示其位置。若RGV 車在第k 階段開(kāi)始時(shí)為第tk秒在i 號(hào)機(jī)床處，那么第k階段狀變量如下：

2.5 確定決策變量

這里用uk(sk)表示第k 階段當(dāng)狀態(tài)變量為sk時(shí)的決策變量。RGV 車在完成清洗作業(yè)后經(jīng)若干時(shí)長(zhǎng)等待后可選擇前往1 至8 號(hào)CNC 中的任意一個(gè)，即允許決策集合Dk(sk)={1,2,3,4,5,6,7,8}。各階段決策確定后，整個(gè)問(wèn)題決策序列就構(gòu)成一個(gè)可行策略p1,n{u1(s1),u2(s2),…, un(sn)}。

2.6 確定狀態(tài)轉(zhuǎn)移方程

這里下一個(gè)階段狀態(tài)中RGV 車的位置就是上一階段決策變量的值，起始時(shí)刻為上一階段起始時(shí)刻加上一階段所花時(shí)間。每一階段所花時(shí)間為上下料及清洗作業(yè)時(shí)長(zhǎng)、等待時(shí)長(zhǎng)、移動(dòng)時(shí)長(zhǎng)之和。由此可寫出狀態(tài)轉(zhuǎn)移方程如下：

其中，表示RGV 車從i 點(diǎn)移動(dòng)到j(luò) 點(diǎn)的所需時(shí)間，在本文所研究的情況下，RGV 車移動(dòng)時(shí)間與移動(dòng)距離有關(guān)，設(shè)tmx表示移動(dòng)x個(gè)單位所需時(shí)間，Δ t(i,j)可寫成如下表達(dá)式：

2.7 確定指標(biāo)函數(shù)

設(shè)RGV 車在第k 階段從sk出發(fā)，采用uk時(shí)的效益為：d(sk,uk)。由上述分析，這里的效益即時(shí)間，并且希望時(shí)間最短。因此d(sk, uk)為RGV 車在第k 階段上下料、清洗、等待、移動(dòng)所花時(shí)間之和：

設(shè)V1,k(sk, p1,k)表示從初始階段到第k 階段采取策略p1,k下的時(shí)間，若fk(sk)表示從初始狀態(tài)到第k 階段狀態(tài)sk所花的最短時(shí)間，則可得以下表達(dá)式：

設(shè)RGV 從第0 秒開(kāi)始工作，所以f1(s1)=0。

2.8 最終數(shù)學(xué)模型

綜上所述，以完成n 個(gè)物料加工時(shí)間最短為目標(biāo)的動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型如下：

3 引入貪心策略

上述模型理論上可以求解得到加工n 個(gè)物料用時(shí)最短的調(diào)度策略，但這是一個(gè)具有指數(shù)復(fù)雜度的問(wèn)題[13]，求解時(shí)間實(shí)測(cè)在1 小時(shí)以上。實(shí)際應(yīng)用中往往將調(diào)度求解耗時(shí)也算在工作時(shí)間內(nèi)，尤其在中途發(fā)生意外需要重新計(jì)算調(diào)度策略時(shí)，花費(fèi)大量時(shí)間求解得不償失。因此需要找一種求解效率較高并調(diào)度策略相對(duì)較優(yōu)的調(diào)度策略。

本文第二節(jié)已經(jīng)將整個(gè)問(wèn)題轉(zhuǎn)換為一個(gè)多階段決策問(wèn)題，在每一個(gè)階段能讓RGV 根據(jù)當(dāng)前CNC 狀態(tài)、RGV 自身所處位置以及調(diào)度規(guī)則直接做出一個(gè)在大多數(shù)情況下都是最優(yōu)的決策，是一個(gè)更加貼合實(shí)際情況的方案。為此基于貪心算法的思想，引入了對(duì)每一個(gè)階段內(nèi)的調(diào)度優(yōu)化策略。

（1）最短距離原則：若當(dāng)前有多個(gè)CNC 需要服務(wù)，則選擇最近的服務(wù)。因?yàn)檫x擇更遠(yuǎn)的會(huì)使RGV 移動(dòng)使用的總時(shí)間增加，導(dǎo)致CNC 等待時(shí)間變長(zhǎng)，使總體效率降低。

（2）盡快響應(yīng)原則：若當(dāng)前暫時(shí)沒(méi)有需要服務(wù)的CNC，則前往最早完工的CNC 處。這個(gè)原則在多數(shù)情況下確實(shí)是響應(yīng)最早完工的CNC 效率高。但出現(xiàn)以下情況：當(dāng)最早完工的CNC 離當(dāng)前的RGV位置很遠(yuǎn)，又有比較近的CNC 完工時(shí)間稍晚于最早的那個(gè)，在這種情況下選擇最早完工的CNC 可能并不是最優(yōu)解，在特定狀況下先去最近的CNC 可使CNC 總等待時(shí)間減少。但在實(shí)際過(guò)程中由于上下料也是由RGV 處理，正常情況下兩個(gè)CNC 完工時(shí)間差會(huì)大于CNC 的移動(dòng)時(shí)間，因此這種情況比較少見(jiàn)，盡快響應(yīng)原則仍然有效。

4 算法流程

4.1 初始狀態(tài)的確定

當(dāng)系統(tǒng)開(kāi)始運(yùn)行時(shí)，所有CNC 都沒(méi)有熟料，即RGV 剛啟動(dòng)時(shí)的唯一任務(wù)就是分別給8 臺(tái)CNC 上料。根據(jù)這一點(diǎn)，將啟動(dòng)后的這一段過(guò)程進(jìn)行分析，采用排列組合的方式求出RGV 給CNC 上料的所有組合。

剛啟動(dòng)時(shí)RGV 位于1 號(hào)和2 號(hào)CNC 之間，顯然應(yīng)該優(yōu)先給這兩臺(tái)CNC 中的一臺(tái)進(jìn)行上料，然后再去為剩余的CNC 上料，所以可得初始的組合方案數(shù)量為NUM：

4.2 算法流程

（1）對(duì)初始啟動(dòng)階段排列組合生成初始調(diào)度計(jì)劃，即通過(guò)排列組合的方式求解出初始8 個(gè)階段的狀態(tài)變量集合{s1, s2,…, s8};

（2）隨機(jī)選取一個(gè)初始狀態(tài)變量集合，根據(jù)“最短距離原則”求解出此種初始解條件下的所有可行調(diào)度策略；

（3）重復(fù)（2），找出所有可行的調(diào)度策略，完成第一輪調(diào)度；

（4）給定任意一個(gè)確定的成料數(shù)n，已完成確定數(shù)量的成料所需的總加工時(shí)間最短為目標(biāo)進(jìn)行優(yōu)化得到完成此數(shù)量的成料要求的最佳調(diào)度策略pk,n;

（5）重復(fù)步驟（4），且規(guī)定每次要求的成料數(shù)不同，計(jì)算不同成料數(shù)的最優(yōu)調(diào)度策略，比較這些策略，找到出現(xiàn)次數(shù)最多的策略作為最終的最優(yōu)調(diào)度策略;

算法的流程圖可見(jiàn)圖3。

圖3：算法流程示意圖

5 求解結(jié)果與對(duì)比分析

5.1 MATLAB求解結(jié)果

本文采用2018年高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B 題中附件的相關(guān)數(shù)據(jù)，使用MATLAB 進(jìn)行編程計(jì)算。得到的三組最優(yōu)調(diào)度策略結(jié)果如表2至表4所示。

表2：第一組求解結(jié)果

表3：第二組求解結(jié)果

表4：第三組求解結(jié)果

第一組調(diào)度結(jié)果中，最后剩余88 秒的加工時(shí)間未得到利用；CNC 加工順序按照1 →3 →5 →7 →8 →6 →4 →2 進(jìn)行循環(huán)。

第二組調(diào)度結(jié)果中，最后剩余188 秒的加工時(shí)間未得到利用；CNC 的加工順序同第一組，按照1 →3 →5 →7 →8 →6 →4 →2進(jìn)行循環(huán)。

第三組調(diào)度結(jié)果中，最后剩余52 秒的加工時(shí)間未得到利用；CNC 的加工順序依然按照1 →3 →5 →7 →8 →6 →4 →2 進(jìn)行循環(huán)。

綜上可得，通過(guò)該模型和算法流程得到的8 臺(tái)CNC 最佳調(diào)度策略，是按照1 →3 →5 →7 →8 →6 →4 →2 的策略進(jìn)行循環(huán)加工物料。

5.2 計(jì)算結(jié)果對(duì)比

史愛(ài)武等人也基于貪心算法設(shè)計(jì)針對(duì)相同問(wèn)題的調(diào)度算法[14]，他們通過(guò)不斷尋找局部最優(yōu)解來(lái)企圖獲取全局最優(yōu)；潘舒曼等人結(jié)合動(dòng)態(tài)調(diào)度，設(shè)計(jì)了純貪心和基于二分圖的貪心算法[15]。將上述兩種模型的求解結(jié)果和重復(fù)10000 次的蒙特卡洛仿真得到的平均結(jié)果與本文的計(jì)算結(jié)果進(jìn)行對(duì)比，詳見(jiàn)表5。由此表對(duì)比結(jié)果可知，本文提出的模型得到的RGV-CNC 調(diào)度方案效果更好。（本文利用Anylogic 仿真軟件實(shí)現(xiàn)蒙特卡羅仿真實(shí)驗(yàn)，詳見(jiàn)圖4和圖5。

圖4：Anylogic 仿真模型運(yùn)行過(guò)程示意圖

圖5：Anylogic 仿真邏輯示意圖

表5：求解結(jié)果對(duì)比

6 結(jié)論

本文針對(duì)一道工序的RGV-CNC 調(diào)度問(wèn)題，基于貪心策略和動(dòng)態(tài)規(guī)劃思想，建立了RGV 動(dòng)態(tài)調(diào)度的優(yōu)化模型。將本文的計(jì)算結(jié)果與其他使用同一數(shù)據(jù)集的論文結(jié)果以及蒙特卡羅仿真結(jié)果進(jìn)行對(duì)比，優(yōu)異的表現(xiàn)驗(yàn)證了本文所建立模型的實(shí)用性。

目前國(guó)內(nèi)智能車間布局逐步普遍，本文的研究對(duì)于RGV-CNC系統(tǒng)的動(dòng)態(tài)調(diào)度策略的制定具有一定的實(shí)際參考意義。