基于混合優(yōu)化算法的RGV動(dòng)態(tài)調(diào)度策略方案

陳恩宏　劉陳帥　賈學(xué)勇

摘 要：本文以智能物料加工系統(tǒng)中軌道式自動(dòng)引導(dǎo)車(chē)（RGV）的最優(yōu)動(dòng)態(tài)調(diào)度問(wèn)題為研究背景，建立了基于動(dòng)態(tài)規(guī)劃—粒子群耦合算法的單工序調(diào)度模型，并結(jié)合自適應(yīng)遺傳算法得出多道工序的動(dòng)態(tài)調(diào)度方案，通過(guò)軟件仿真驗(yàn)證了模型的合理性和有效性 。對(duì)于一道工序的RGV動(dòng)態(tài)調(diào)度問(wèn)題，建立動(dòng)態(tài)規(guī)劃—粒子群算法模型。首先選取8小時(shí)內(nèi)RGV移動(dòng)的總距離最短作為目標(biāo)函數(shù)，根據(jù)RGV同一時(shí)間只能完成一個(gè)任務(wù)，數(shù)控機(jī)床（CNC）在某一時(shí)間只能加工一個(gè)物料以及RGV執(zhí)行任務(wù)的順序等原則確定約束條件。然后利用動(dòng)態(tài)規(guī)劃算法以時(shí)間軸為劃分原則，將整個(gè)調(diào)度過(guò)程轉(zhuǎn)化為若干個(gè)子過(guò)程，各子過(guò)程之間狀態(tài)函數(shù)相互關(guān)聯(lián)，最后結(jié)合粒子群算法尋找各子過(guò)程的最優(yōu)軌跡即可得出基于RGV移動(dòng)總距離最短的單目標(biāo)優(yōu)化的動(dòng)態(tài)調(diào)度策略。為了解決兩道工序的RGV動(dòng)態(tài)調(diào)度問(wèn)題，本文首先建立自適應(yīng)遺傳模型，對(duì)多目標(biāo)函數(shù)進(jìn)行優(yōu)化，并提出額外作業(yè)效率和修正系數(shù)的概念對(duì)模型進(jìn)行完善；然后增加模型的約束條件來(lái)達(dá)到明確兩道工序時(shí)間上的先后性的目的；采用自適應(yīng)理論對(duì)目標(biāo)函數(shù)的權(quán)重進(jìn)行確定，來(lái)達(dá)到減少遺傳算法迭代次數(shù)的目的；最后根據(jù)遺傳算法的尋優(yōu)過(guò)程來(lái)得出RGV具體的行走軌跡，進(jìn)而得到效率較高的動(dòng)態(tài)調(diào)度策略。

關(guān)鍵詞：動(dòng)態(tài)調(diào)度 動(dòng)態(tài)規(guī)劃—粒子群 自學(xué)習(xí)遺傳算法

模擬仿真

1. 引言

簡(jiǎn)易的智能加工系統(tǒng)由數(shù)控機(jī)床（CNC）、軌道式自動(dòng)引導(dǎo)車(chē)（RGV）、引導(dǎo)車(chē)直線軌道等其他附屬設(shè)備組成，其中RGV是一種自動(dòng)沿用軌道的自動(dòng)運(yùn)行，在軌道兩側(cè)傳送帶用于上料、下料，RGV可通過(guò)移動(dòng)到數(shù)控機(jī)床（CNC）旁，使用引導(dǎo)車(chē)自身帶有的機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，完成上、下料和物料清洗。

物料的加工作業(yè)大致可分為兩種情況，一是由一臺(tái)CNC就可以完成，二是由兩臺(tái)CNC完成，且兩臺(tái)機(jī)器的刀具不同。

2.基于兩道工序的RGV動(dòng)態(tài)調(diào)度模型

RGV對(duì)CNC上料需求的選擇若僅僅依靠就近原則，可能會(huì)造成多臺(tái)CNC的空閑和RGV長(zhǎng)時(shí)間停止等待任務(wù)的情況，這種簡(jiǎn)單的調(diào)度方式效率低，因此，基于兩道工序加工物料的RGV需考慮多個(gè)目標(biāo)函數(shù)。

2.1模型的準(zhǔn)備

將GRV作業(yè)過(guò)程中任意時(shí)刻的狀態(tài)進(jìn)行量化，以便后續(xù)約束條件和目標(biāo)函數(shù)的建立。根據(jù)表格中GRV系統(tǒng)作業(yè)參數(shù)，得出物料加工的第一、二道工序基本相等，所以將8個(gè)CNC平均分為兩部分，1#、3#、5#、7#可完成物料加工的第一道工序，中，；表示第個(gè)物料在任一個(gè)CNC上開(kāi)始加工的時(shí)刻，表示第個(gè)物料開(kāi)始加工第二道工序的時(shí)刻，。

其中，約束條件（7）表示一個(gè)物料的第一道工序完成總成第二道之前，目標(biāo)函數(shù)（8）表示RGV在工作時(shí)間8小時(shí)內(nèi)執(zhí)行次指令時(shí)移動(dòng)總路程的最小值；系統(tǒng)作業(yè)效率，目標(biāo)函數(shù)（12）表示RGV作業(yè)過(guò)程的最短總路徑和最大作業(yè)效率。

2.2自學(xué)習(xí)遺傳算法模型的建立

自學(xué)習(xí)遺傳算法避免傳統(tǒng)遺傳算法局部搜索的不敏感，可解決多個(gè)目標(biāo)函數(shù)的優(yōu)化問(wèn)題，算法中引入遺傳算子和妥協(xié)解自學(xué)習(xí)，提高了遺傳算法的局部收斂速度。

1.編碼、變異和交叉遺傳

遺傳染色體的編碼方式采用二進(jìn)制編碼方法，對(duì)一輛RGV工作狀態(tài)和作業(yè)進(jìn)度進(jìn)行編碼，組成染色體，具體編碼為：；

直線往復(fù)式RGV進(jìn)行作業(yè)時(shí)，實(shí)時(shí)自主變化的是作業(yè)任務(wù)點(diǎn)，隨之變化的是RGV的移動(dòng)路線，在遺傳變異中，采用多點(diǎn)交叉法，交叉位置為RGV小車(chē)等待狀態(tài)=0，交叉點(diǎn)數(shù)服從泊松分布：

（14）

2.自適應(yīng)交叉、變異概率

等研究人員提出改變算法遺傳變異中交叉概率和變異概率都不變的條件，提出遺傳適應(yīng)度自動(dòng)進(jìn)行改變和優(yōu)化，其中交叉概率，變異概率計(jì)算公式為：

其中，為種群最大、最小交叉概率；為種群最大、最小變異概率； 為種群的最大適應(yīng)值；為每代種群的平均適應(yīng)值；為兩個(gè)個(gè)體中較大的適應(yīng)度值。

減少時(shí)，種群中個(gè)體的適應(yīng)度高于平均適應(yīng)值，較小時(shí)，進(jìn)行遺傳變異時(shí)，將被保留下來(lái)，否則將被淘汰。

3.自適應(yīng)函數(shù)

由于軌道往復(fù)式小車(chē)的在不同時(shí)間的作業(yè)情況可能出現(xiàn)重復(fù)，引入知識(shí)專家種群模塊，當(dāng)出現(xiàn)相同的路徑選擇時(shí)直接調(diào)用庫(kù)中之前生成的種群收斂性最優(yōu)解，不僅提高迭代效率，在隨機(jī)種群的不斷生成中，更新知識(shí)專家?guī)?。妥協(xié)方法是通過(guò)不斷訓(xùn)練，隨著子代數(shù)的不斷增加，染色體發(fā)生遺傳和變異趨向穩(wěn)定，最終得出與實(shí)際中與理想條件最接近的最優(yōu)解。

總 結(jié)

動(dòng)態(tài)規(guī)劃—粒子群算法在優(yōu)化實(shí)現(xiàn)上迭代計(jì)算比遺傳算法容易，并且在優(yōu)化的結(jié)果上相較于動(dòng)態(tài)規(guī)劃計(jì)算結(jié)果精度顯著提高，該結(jié)合算法不易陷入局部最優(yōu)，保證了全局優(yōu)化結(jié)果的有效性，試用于大量難以全面研究的領(lǐng)域，例如航空航天領(lǐng)域、大型水庫(kù)蓄水量管理等等，可其中的部分粒子劃分為若干個(gè)階段，以局部粒子的最優(yōu)取向得出全局的發(fā)展趨勢(shì)。

本文中定義的RGV的作業(yè)時(shí)間是除原地等待以外所有的有效時(shí)間，在確保全局路徑在一定值的情況下，還需要借助效率目標(biāo)函數(shù)進(jìn)行最優(yōu)趨向引導(dǎo)，自適應(yīng)遺傳算法可同時(shí)設(shè)立多個(gè)目標(biāo)函數(shù)，求解各個(gè)目標(biāo)函數(shù)在執(zhí)行決策中的權(quán)重，能夠準(zhǔn)確的得出RGV動(dòng)態(tài)調(diào)度策略。并且CNC出現(xiàn)故障對(duì)于RGV路徑和作業(yè)時(shí)間的影響不同，通過(guò)公式得出理論修正系數(shù)也不同，多個(gè)目標(biāo)函數(shù)與其不同的修正系數(shù)匹配得到實(shí)際RGV調(diào)度策略和系統(tǒng)作業(yè)效率。

參考文獻(xiàn)

[1] 江唯，何非，童一飛，李東波. 基于混合算法的環(huán)形軌道RGV系統(tǒng)調(diào)度優(yōu)化研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2016，52（22）：242-247.

[2] 王曉寧. 直線往復(fù)式軌道穿梭車(chē)避讓策略仿真研究[D].北京郵電大學(xué)，2012.

[3] 吳孟達(dá). 數(shù)學(xué)建模教程[M]. 高等教育出版社， 2011.

[4] 唐猛. 自動(dòng)小車(chē)存取系統(tǒng)建模及調(diào)度優(yōu)化研究[D].武漢大學(xué)，2015.

[5] 聶峰. 自動(dòng)化立體倉(cāng)庫(kù)穿梭車(chē)系統(tǒng)控制方法與優(yōu)化調(diào)度研究[D].太原理工大學(xué)，2009.