基于粒子群算法和仿真技術(shù)的RGV動(dòng)態(tài)調(diào)度建模與優(yōu)化

引言

RGV(Rai1GuidedVehic1e),即有軌制導(dǎo)車輛,又稱有軌穿梭小車。目前,RGV廣泛應(yīng)用于自動(dòng)化倉庫和自動(dòng)化物流系統(tǒng)等領(lǐng)域。已有研究表明,部分學(xué)者集中研究了一維平面上RGV的運(yùn)動(dòng),主要以環(huán)形軌道和直線軌道上運(yùn)行的多輛RGV為研究對象。

例如:吳焱明研究了基于遺傳算法的環(huán)軌RGV動(dòng)態(tài)調(diào)度問題,通過eM-P1ant軟件驗(yàn)證了模型的有效性。顧紅針對環(huán)形RGV的工作特點(diǎn),建立了RGV搬運(yùn)作業(yè)的多目標(biāo)調(diào)度數(shù)學(xué)模型,提出了基于自學(xué)習(xí)和改進(jìn)遺傳算法的環(huán)形RGV實(shí)時(shí)調(diào)度算法。江唯提出路徑最短和擁堵次數(shù)最少兩個(gè)優(yōu)化目標(biāo),建立數(shù)學(xué)模型,設(shè)計(jì)了基于規(guī)則的混合遺傳算法求解環(huán)形軌道上RGV的調(diào)度問題。陳華以救災(zāi)物資自動(dòng)化立體倉庫為背景,提出了直線軌道上基于區(qū)域劃分的2-RGV碰撞避免調(diào)度問題的混合整數(shù)線性規(guī)劃模型和混合遺傳算法。國外學(xué)者Jackon于1957年最早提出了動(dòng)態(tài)調(diào)度的概念,主要的研究方法包括啟發(fā)式方法和仿真方法。劉儼后定義了動(dòng)態(tài)事件,稱引起調(diào)度環(huán)境變化進(jìn)而需要進(jìn)行動(dòng)態(tài)調(diào)度的事件為動(dòng)態(tài)事件,動(dòng)態(tài)事件主要包括訂單相關(guān)、工序相關(guān)和機(jī)器相關(guān)的三種情況,在此基礎(chǔ)上研究了制造系統(tǒng)受到隨機(jī)事件干擾情況下即有緊急訂單插入事件的動(dòng)態(tài)調(diào)度問題。Peteghem等設(shè)計(jì)了分層遺傳算法,解決了多資源約束條件下的動(dòng)態(tài)調(diào)度問題。

上述研究多以RGV的調(diào)度策略為切入點(diǎn),對機(jī)器相關(guān)、訂單相關(guān)的事件進(jìn)行調(diào)度,但均未考慮與工序相關(guān)的工序排布問題。仿真方法不足之處在于每一次仿真運(yùn)行只是對實(shí)際加工過程的一次抽樣,不能進(jìn)行有效的優(yōu)化。

本文主要研究一智能加工系統(tǒng)與工序相關(guān)、與機(jī)器相關(guān)的事件發(fā)生后對動(dòng)態(tài)調(diào)度產(chǎn)生的影響。與工序相關(guān)指工序排布不同導(dǎo)致對作業(yè)效率的影響,與機(jī)器相關(guān)指按照一定的調(diào)度策略為各工序分配合適的加工機(jī)床進(jìn)行加工。為了彌補(bǔ)單一優(yōu)化的不足,本文的工作是將仿真方法、調(diào)度策略和粒子群算法相結(jié)合,實(shí)現(xiàn)智能加工系統(tǒng)的動(dòng)態(tài)調(diào)度。

1多目標(biāo)優(yōu)化模型

1.1仿真模型框架

模型的組成:該智能加工系統(tǒng)由l0臺(tái)計(jì)算機(jī)數(shù)控機(jī)床(ComputerNumberContro11er,CNC)、l輛軌道式自動(dòng)引導(dǎo)車(Rai1 GuideVehic1e ,RGV) 、l條RGV直線軌道 、l條上料傳送 帶、l條下料傳送帶等附屬設(shè)備組成 。RGV可根據(jù)指令自動(dòng)控制移動(dòng)方向和距離 ,并自帶一個(gè)機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽 ,能夠完成上下料及清洗物料等作業(yè)任務(wù)。CNC的編號按奇偶數(shù)分布在上下料傳送帶的兩側(cè) ,如圖1所示。

假設(shè)10臺(tái)CNC上共加工N件物料 ,每件物料由K道工序組成。單道工序的物料可在M臺(tái)設(shè)備中的任一 臺(tái)CNC上加工完成。多道工序的物料分別由不同的CNC依次加工完成 ,每道工序完成時(shí)間不盡相同。

問題假設(shè):

(1)忽略物料上下傳送帶的時(shí)間:

(2)傳送帶上的物料不存在積壓:

(3)RGV抓取物料的時(shí)候 ,物料已經(jīng)在傳送帶上準(zhǔn)備到位:

(4)RGV接收CNC發(fā)送的需求信號 ,并根據(jù)所在位置按照一定調(diào)度策略就近選擇服務(wù):

(5) 一件物料的加工工序只能在一個(gè)班次(設(shè)定為8 h) 中進(jìn)行:

(6)所有CNC在時(shí)刻l=0都可用:

(7)加工是非搶占式的 , 即在給定時(shí)間段內(nèi) , 一 臺(tái)CNC只能加工一件物料,只有當(dāng)前工序結(jié)束后才能開始加工其他物料。

1.2 數(shù)學(xué)模型

通過分析 , 物料狀態(tài)對應(yīng)分為三種: 生料 、熟料 、成料: CNC狀態(tài)對應(yīng)分為三種:加工、空閑、故障:RGV狀態(tài)有四種:移動(dòng)、上下料作業(yè)、停止等待、熟料清洗 。對變量定義如下:

對于物料:

N:待加工生料數(shù)量集合 ,j=(l ,2 , … ,N):

N':加工完成的熟料數(shù)量集合 ,s=(l ,2 , … ,N') :

Ⅹij億:物料億第j道工序在編號為i的CNC上加工與否 ,Ⅹij億=1 表示加工 ,Ⅹij億=0表示不加工:

K:物料的工序數(shù)量集合 ,億={1 ,2 , … ,K):

ⅩEQ \* jc3 \* hps10 \o\al(\s\up 3(億 :物料億第j道工序在編號為i的CNC上加工開始時(shí)間:

ⅩEQ \* jc3 \* hps10 \o\al(\s\up 3(億 :物料億第j道工序在編號為i的CNC上加工結(jié)束時(shí)間。

對于CNC:

皿:計(jì)算機(jī)數(shù)控機(jī)床CNC集合 ,i={1 ,2 , … ,皿):

tij億:物料j第億道工序在編號為i的CNC上加工所需時(shí)間。

對于RGV:

tEQ \* jc3 \* hps10 \o\al(\s\up 3(億g:RGV響應(yīng)上下料作業(yè)j的第億道工序 , 移動(dòng)g個(gè)單位(g+1臺(tái)相鄰CNC間的距離)到編號為i的CNC機(jī)床位置正中間所需時(shí)間。

對于RGV而言 ,它的時(shí)間主要包括四項(xiàng):移動(dòng)時(shí)間 、停止等待時(shí)間、上下料時(shí)間和清洗作業(yè)時(shí)間。

移動(dòng)時(shí)間為RGV通過一定規(guī)則移動(dòng)到要為其服務(wù)的CNC 正中間位置所需時(shí)間 ,表示如下:

根據(jù)上述分析 ,建立兩個(gè)目標(biāo)函數(shù):系統(tǒng)作業(yè)效率最大化和RGV移動(dòng)時(shí)間最短。

對于目標(biāo)函數(shù)1 ,系統(tǒng)的作業(yè)效率n定義為單位時(shí)間(設(shè)為 min)內(nèi)加工熟料的數(shù)量 ,故目標(biāo)函數(shù)可表述為:

對于目標(biāo)函數(shù)2 ,RGV移動(dòng)時(shí)間最短可表述為:

約束條件s.t. :

約束條件中 ,式(4)表示物料j只分配給某一 臺(tái)CNC加工:式(5)表示物料j第億道工序必須在第億- 1道工序完成后才能開始:式(6)表示第i臺(tái)CNC上不能同時(shí)加工兩個(gè)任意不同的物料;式(7)表示CNC加工物料的時(shí)間約束。

2 調(diào)度策略的建立

調(diào)度策略的建立主要考慮兩個(gè)方面 ,其一 目 的在于使用人為制定的規(guī)則使RGV有導(dǎo)向地向指定目標(biāo)移動(dòng) ,為相應(yīng)的 CNC進(jìn)行作業(yè);其二目的在于考慮CNC上的加工工序排布 ,可以更加高效地完成對多道工序的物料加工 。根據(jù)對問題的分析,設(shè)定了三種動(dòng)態(tài)調(diào)度策略:CNC工序分配、CNC編號奇偶優(yōu)先和RGV任務(wù)分派策略。

2. 1 CNC工序分配策略

CNC工序分配策略指的是 ,在智能加工系統(tǒng)通電啟動(dòng)后 , RGV處于CNC1#和CNC2#正中間的初始位置 ,所有CNC都處于空閑狀態(tài)。此時(shí) ,假設(shè)CNC1、2、3、4、5、6、7、8、9、10上需加工完成兩道工序的物料 ,其加工工序?yàn)?、2、2、2、2、1、1、1、1、1 ,此時(shí)編號為2、4、6、8、10的CNC上分別加工物料的第2、2、1、1、1道工序 ,編號為1、3、5、7、9的CNC上分別加工物料的第2、2、2、1、1道工序。

2.2 CNC編號奇偶優(yōu)先策略

對于兩道不同的工序 ,影響有效物料生產(chǎn)個(gè)數(shù)的因素有兩方面 ,主要因素在于CNC工序1和工序2的不同排布 ,次要因素在于同一工序排布狀態(tài)下CNC的奇偶優(yōu)先性 , 即在CNC處于空閑的狀態(tài) ,優(yōu)先分配編號為奇數(shù)的CNC還是編號為偶數(shù)的CNC進(jìn)行物料加工。

2.3 RGV任務(wù)分派策略

CNC向RGV發(fā)送需求信號 ,到達(dá)RGV的指令信號視為一個(gè)任務(wù)隊(duì)列。當(dāng)物料送入傳送帶 ,RGV在收到CNC的需求信號后 ,將根據(jù)需求指令決定作業(yè)路徑 。當(dāng)某一 臺(tái)CNC完成加工物料操作 , 由加工作業(yè)狀態(tài)轉(zhuǎn)換為空閑狀態(tài)時(shí) ,若RGV沒有執(zhí)行其他作業(yè)且正好處于該空閑CNC正中間位置 , 則優(yōu)先響應(yīng)對應(yīng)位置上的CNC;否則 ,RGV執(zhí)行移動(dòng)操作 ,按照最短路徑移動(dòng)至空閑CNC的正中間位置 ,進(jìn)行上下料作業(yè)。

3 粒子群算法設(shè)計(jì)

1995年 ,Kennedy等人提出了基于鳥群覓食行為的粒子群優(yōu)化算法(Ps0) ,簡稱"粒子群算法" 。粒子群算法對于約束優(yōu)化中的規(guī)劃 ,離散空間組合問題的求解非常有效。多目標(biāo)優(yōu)化問題是粒子群算法的主要研究方向。基于此 ,本文結(jié)合自動(dòng)化生產(chǎn)領(lǐng)域的智能加工系統(tǒng) ,提出基于工序編碼的粒子群算法 ,在一個(gè)班次的工作狀態(tài)下 ,對系統(tǒng)的作業(yè)效率和RGV移動(dòng)時(shí)間進(jìn)行優(yōu)化。

3. 1 基于工序的粒子編碼

根據(jù)圖1的智能加工系統(tǒng)示意圖 , 以10臺(tái)CNC、1輛RGV、加工兩道工序的物料為例 ,將粒子做出如圖2所示的編碼設(shè)計(jì) 。首先給出一組隨機(jī)解 ,設(shè)為0000011111 ,其中0表示第一道工序, 1表示第二道工序。然后以此為出發(fā)點(diǎn) ,通過迭代尋找最優(yōu)解。

圖2中的第一行表示CNC編號 ,第二行表示機(jī)床CNC是否進(jìn)行物料第幾道工序的加工 。例如 , 工序(0000011111) 中的(0)物料可在編號為1 ,2 ,3 ,4 ,5的CNC上其中任一 臺(tái)進(jìn)行加工 , (1)表示物料可在編號為6 ,7 ,8 ,9 , 10的CNC上其中任一 臺(tái) 進(jìn)行加工。

3.2 種群的初始化

根據(jù)3. 1的粒子編碼方式 ,每一件物料的每道工序都可以在指定的CNC上進(jìn)行加工 ,初始化粒子的位置和速度 ,根據(jù)模型的 目標(biāo)函數(shù)式(2)和式(3)設(shè)計(jì)適應(yīng)度函數(shù) ,計(jì)算每個(gè)粒子的適應(yīng)值 ,并記錄個(gè)體極值點(diǎn)pBest、全局極值點(diǎn)gBest。

3.3 粒子位置的更新

在基本的粒子群算法中 ,粒子根據(jù)公式(8)和(9)來更新自己的速度和位置:

式中 ,w為慣性權(quán)重;c1、c2表示學(xué)習(xí)因子 ,也稱為加速常數(shù);r1、 r2為區(qū)間[0 , 1]范圍內(nèi)的隨機(jī)數(shù);pid為個(gè)體最優(yōu)粒子位置;pgd為全局最優(yōu)粒子位置;⑦、x分別表示粒子速度和粒子位置。

3.4 權(quán)重的更新

本文使用線性遞減權(quán)重法 ,使慣性權(quán)重依照線性從大到小遞減 ,其公式為:

式中 ,wmax表示權(quán)重最大值;wmin表示權(quán)重最小值;t表示當(dāng)前迭代步數(shù)。

3.5 獲取最優(yōu)值

將每個(gè)粒子的適應(yīng)值與粒子的最好位置比較 ,如果相近 ,則將當(dāng)前值作為粒子最好的位置 , 比較當(dāng)前所有的pBest和 gBest,更新gBest。在適應(yīng)值的計(jì)算過程中 ,根據(jù)所有粒子的適應(yīng)值按照由高到低的順序進(jìn)行排序 ,計(jì)算平均適應(yīng)值 ,然后剔除適應(yīng)值低于平均適應(yīng)值的粒子 。隨后再重新引入一批新的粒子。

3.6 算法是否終止

當(dāng)算法達(dá)到最大迭代次數(shù)時(shí) , 則停止搜索并輸出最終結(jié)果 ,否則返回到3.3繼續(xù)執(zhí)行。

4 實(shí)例驗(yàn)證

下面對圖1所示的智能加工系統(tǒng)進(jìn)行仿真實(shí)驗(yàn)。根據(jù)前文所述 ,選擇10臺(tái)CNC加工1個(gè)班次兩道工序的物料 。實(shí)驗(yàn)在PC 機(jī)上的0T框架下進(jìn)行 ,所有代碼均由C++語言編程實(shí)現(xiàn) ,求解過程中分別代入表1中的三組參數(shù) ,求解結(jié)果如表2~4所示。

在第一組數(shù)據(jù)計(jì)算結(jié)果中 ,系統(tǒng)作業(yè)效率為51.04% ,RGV 移動(dòng)時(shí)間為6 751 s ,加工熟料的數(shù)量為245件 , 同 一 結(jié)果下 , CNC工序的分配有8種 ,奇偶優(yōu)先結(jié)果相同。

在第二組數(shù)據(jù)計(jì)算結(jié)果中 ,系統(tǒng)作業(yè)效率為43.96% ,RGV 移動(dòng)時(shí)間為7 482 s ,加工熟料的數(shù)量為211件 , 同 一 結(jié)果下 , CNC工序的分配有16種 ,奇偶優(yōu)先結(jié)果相同。

在第三組數(shù)據(jù)計(jì)算結(jié)果中 ,奇偶優(yōu)先結(jié)果不同。奇優(yōu)先的情況下 ,系統(tǒng)作業(yè)效率為51.25% ,RGV移動(dòng)時(shí)間為6 932 s ,加工熟料的數(shù)量為246件 ,CNC工序的分配有8種;偶優(yōu)先的情況下 ,系統(tǒng)作業(yè)效率為50.83% ,RGV移動(dòng)時(shí)間為6 672 s ,加工熟料的數(shù)量為244件 ,CNC工序的分配有32種 。本組數(shù)據(jù)說明奇偶優(yōu)先策略不同 ,CNC工序分配差異較大。

5 結(jié)論與展望

本文基于智能加工系統(tǒng)給出了動(dòng)態(tài)調(diào)度的數(shù)學(xué)模型 ,在調(diào)度過程中考慮了CNC工序分配策略 、CNC編號奇偶優(yōu)先策略、RGV任務(wù)分派策略。

該模型結(jié)合粒子群算法進(jìn)行求解 , 設(shè)計(jì)了基于工序編碼的粒子編碼方式 ,調(diào)整了慣性權(quán)重 ,對適應(yīng)度值較低的粒子做了剔除以提高全局搜索能力 , 從而得出CNC的最優(yōu)調(diào)度結(jié)果。

后續(xù)工作將結(jié)合自動(dòng)化領(lǐng)域生產(chǎn)調(diào)度的實(shí)際問題 , 比如從CNC最優(yōu)加工臺(tái)數(shù) 、物料的多道工序 、CNC加工過程中出現(xiàn)故障的情況等角度入手展開更細(xì)致的研究。