陳恩宏 劉陳帥 賈學勇
摘 要:本文以智能物料加工系統(tǒng)中軌道式自動引導車(RGV)的最優(yōu)動態(tài)調度問題為研究背景,建立了基于動態(tài)規(guī)劃—粒子群耦合算法的單工序調度模型,并結合自適應遺傳算法得出多道工序的動態(tài)調度方案,通過軟件仿真驗證了模型的合理性和有效性 。對于一道工序的RGV動態(tài)調度問題,建立動態(tài)規(guī)劃—粒子群算法模型。首先選取8小時內RGV移動的總距離最短作為目標函數(shù),根據(jù)RGV同一時間只能完成一個任務,數(shù)控機床(CNC)在某一時間只能加工一個物料以及RGV執(zhí)行任務的順序等原則確定約束條件。然后利用動態(tài)規(guī)劃算法以時間軸為劃分原則,將整個調度過程轉化為若干個子過程,各子過程之間狀態(tài)函數(shù)相互關聯(lián),最后結合粒子群算法尋找各子過程的最優(yōu)軌跡即可得出基于RGV移動總距離最短的單目標優(yōu)化的動態(tài)調度策略。為了解決兩道工序的RGV動態(tài)調度問題,本文首先建立自適應遺傳模型,對多目標函數(shù)進行優(yōu)化,并提出額外作業(yè)效率和修正系數(shù)的概念對模型進行完善;然后增加模型的約束條件來達到明確兩道工序時間上的先后性的目的;采用自適應理論對目標函數(shù)的權重進行確定,來達到減少遺傳算法迭代次數(shù)的目的;最后根據(jù)遺傳算法的尋優(yōu)過程來得出RGV具體的行走軌跡,進而得到效率較高的動態(tài)調度策略。
關鍵詞:動態(tài)調度 動態(tài)規(guī)劃—粒子群 自學習遺傳算法
模擬仿真
1. 引言
簡易的智能加工系統(tǒng)由數(shù)控機床(CNC)、軌道式自動引導車(RGV)、引導車直線軌道等其他附屬設備組成,其中RGV是一種自動沿用軌道的自動運行,在軌道兩側傳送帶用于上料、下料,RGV可通過移動到數(shù)控機床(CNC)旁,使用引導車自身帶有的機械手臂、兩只機械手爪和物料清洗槽,完成上、下料和物料清洗。
物料的加工作業(yè)大致可分為兩種情況,一是由一臺CNC就可以完成,二是由兩臺CNC完成,且兩臺機器的刀具不同。
2.基于兩道工序的RGV動態(tài)調度模型
RGV對CNC上料需求的選擇若僅僅依靠就近原則,可能會造成多臺CNC的空閑和RGV長時間停止等待任務的情況,這種簡單的調度方式效率低,因此,基于兩道工序加工物料的RGV需考慮多個目標函數(shù)。
2.1模型的準備
將GRV作業(yè)過程中任意時刻的狀態(tài)進行量化,以便后續(xù)約束條件和目標函數(shù)的建立。根據(jù)表格中GRV系統(tǒng)作業(yè)參數(shù),得出物料加工的第一、二道工序基本相等,所以將8個CNC平均分為兩部分,1#、3#、5#、7#可完成物料加工的第一道工序,中,;表示第個物料在任一個CNC上開始加工的時刻,表示第個物料開始加工第二道工序的時刻,。
其中,約束條件(7)表示一個物料的第一道工序完成總成第二道之前,目標函數(shù)(8)表示RGV在工作時間8小時內執(zhí)行次指令時移動總路程的最小值;系統(tǒng)作業(yè)效率,目標函數(shù)(12)表示RGV作業(yè)過程的最短總路徑和最大作業(yè)效率。
2.2自學習遺傳算法模型的建立
自學習遺傳算法避免傳統(tǒng)遺傳算法局部搜索的不敏感,可解決多個目標函數(shù)的優(yōu)化問題,算法中引入遺傳算子和妥協(xié)解自學習,提高了遺傳算法的局部收斂速度。
1.編碼、變異和交叉遺傳
遺傳染色體的編碼方式采用二進制編碼方法,對一輛RGV工作狀態(tài)和作業(yè)進度進行編碼,組成染色體,具體編碼為:;
直線往復式RGV進行作業(yè)時,實時自主變化的是作業(yè)任務點,隨之變化的是RGV的移動路線,在遺傳變異中,采用多點交叉法,交叉位置為RGV小車等待狀態(tài)=0,交叉點數(shù)服從泊松分布:
(14)
2.自適應交叉、變異概率
等研究人員提出改變算法遺傳變異中交叉概率和變異概率都不變的條件,提出遺傳適應度自動進行改變和優(yōu)化,其中交叉概率,變異概率計算公式為:
其中,為種群最大、最小交叉概率;為種群最大、最小變異概率; 為種群的最大適應值;為每代種群的平均適應值;為兩個個體中較大的適應度值。
減少時,種群中個體的適應度高于平均適應值,較小時,進行遺傳變異時,將被保留下來,否則將被淘汰。
3.自適應函數(shù)
由于軌道往復式小車的在不同時間的作業(yè)情況可能出現(xiàn)重復,引入知識專家種群模塊,當出現(xiàn)相同的路徑選擇時直接調用庫中之前生成的種群收斂性最優(yōu)解,不僅提高迭代效率,在隨機種群的不斷生成中,更新知識專家?guī)臁M讌f(xié)方法是通過不斷訓練,隨著子代數(shù)的不斷增加,染色體發(fā)生遺傳和變異趨向穩(wěn)定,最終得出與實際中與理想條件最接近的最優(yōu)解。
總 結
動態(tài)規(guī)劃—粒子群算法在優(yōu)化實現(xiàn)上迭代計算比遺傳算法容易,并且在優(yōu)化的結果上相較于動態(tài)規(guī)劃計算結果精度顯著提高,該結合算法不易陷入局部最優(yōu),保證了全局優(yōu)化結果的有效性,試用于大量難以全面研究的領域,例如航空航天領域、大型水庫蓄水量管理等等,可其中的部分粒子劃分為若干個階段,以局部粒子的最優(yōu)取向得出全局的發(fā)展趨勢。
本文中定義的RGV的作業(yè)時間是除原地等待以外所有的有效時間,在確保全局路徑在一定值的情況下,還需要借助效率目標函數(shù)進行最優(yōu)趨向引導,自適應遺傳算法可同時設立多個目標函數(shù),求解各個目標函數(shù)在執(zhí)行決策中的權重,能夠準確的得出RGV動態(tài)調度策略。并且CNC出現(xiàn)故障對于RGV路徑和作業(yè)時間的影響不同,通過公式得出理論修正系數(shù)也不同,多個目標函數(shù)與其不同的修正系數(shù)匹配得到實際RGV調度策略和系統(tǒng)作業(yè)效率。
參考文獻
[1] 江唯,何非,童一飛,李東波. 基于混合算法的環(huán)形軌道RGV系統(tǒng)調度優(yōu)化研究[J]. 計算機工程與應用,2016,52(22):242-247.
[2] 王曉寧. 直線往復式軌道穿梭車避讓策略仿真研究[D].北京郵電大學,2012.
[3] 吳孟達. 數(shù)學建模教程[M]. 高等教育出版社, 2011.
[4] 唐猛. 自動小車存取系統(tǒng)建模及調度優(yōu)化研究[D].武漢大學,2015.
[5] 聶峰. 自動化立體倉庫穿梭車系統(tǒng)控制方法與優(yōu)化調度研究[D].太原理工大學,2009.