基于粒子群算法的兩道工序RGV動(dòng)態(tài)調(diào)度模型

伊新銅

摘 要：本文針對(duì)基于CNC和RGV構(gòu)成的智能加工系統(tǒng)的動(dòng)態(tài)調(diào)度進(jìn)行了詳細(xì)研究，建立了2道工序在無故障的動(dòng)態(tài)優(yōu)化模型，并分別利用貪心算法和遺傳算法對(duì)所建優(yōu)化模型進(jìn)行求解。本文運(yùn)用搜索樹對(duì)每一次RGV確定CNC的上下料作業(yè)順序進(jìn)行決策，搜索域?yàn)榕cRGV距離最短的3個(gè)CNC，尋找最短的遍歷3個(gè)CNC的路徑，通過運(yùn)行算法輸出第一組、第二組、第三組產(chǎn)出熟料的數(shù)量分別為371、346、371。

關(guān)鍵詞：動(dòng)態(tài)調(diào)度模型 粒子群算法 搜索樹

中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2019）04（a）-0124-02

智能RGV加工系統(tǒng)主要由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（CNC）、1輛自動(dòng)引導(dǎo)車（RGV）、1條上料傳送帶和1條下料傳送帶構(gòu)成，其中RGV是一種根據(jù)指令在固定軌道上自動(dòng)控制移動(dòng)方向和距離的智能車，并自一個(gè)帶機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，從而完成上下料及清洗物料等任務(wù)。

RGV系統(tǒng)由中間至兩邊分別為自動(dòng)引導(dǎo)車RGV、物料傳送帶和數(shù)控機(jī)床CNC。自帶機(jī)械手和清洗槽的自動(dòng)引導(dǎo)車RGV，機(jī)械手臂前端的兩個(gè)手爪通過旋轉(zhuǎn)可先后抓取一個(gè)物料（未加工生料或已加工熟料），從而完成上下料任務(wù)；清洗槽每次僅可清洗1個(gè)熟料（不可清洗生料）。RGV系統(tǒng)的工作流程為：（1）RGV位于初始位置，所有CNC空閑→（2）空閑CNC向RGV發(fā)上料信號(hào)→（3）RGV收到信號(hào)，確定CNC上下料次序并完成上下料→（4）每完成一次上下料進(jìn)行清洗作業(yè)→（5）REV完成一項(xiàng)任務(wù)后執(zhí)行下一指令或原地等待→（6）重復(fù)步驟（3）～（5）直至系統(tǒng)停止作業(yè)。

對(duì)于有n（n=2）道加工工序的物料，將RGV的工作狀態(tài)分為為第 道工序進(jìn)行上下料幾個(gè)作業(yè)狀態(tài)，并考慮到n道加工順序和CNC出現(xiàn)故障后維修時(shí)間的連續(xù)性，找到一種可行的調(diào)度方案，使CNC在時(shí)間約束下空閑時(shí)間最小。

1 符號(hào)說明

符號(hào)說明，如表1所示。

2 模型假設(shè)

（1）CNC系統(tǒng)在整個(gè)系統(tǒng)運(yùn)行過程中，保持正常運(yùn)行；（2）每臺(tái)CNC前的傳送帶提供物料量遠(yuǎn)大于RGV的需求量，由于傳送帶造成的微小誤差可忽略不計(jì)；（3）CNC在換刀片的過程中可以直接更換，不需要更換的時(shí)間；

3 模型的建立與求解

有2道工序的物料進(jìn)行加工，目標(biāo)為使得8h內(nèi)完成的熟料個(gè)數(shù)最多。由于本題有2道工序，首先根據(jù)加工第1道工序所用時(shí)間與加工第2道工序所用時(shí)間的按比例分配加工2道工序CNC數(shù)量分別為N1、N2；其次對(duì)于RGV的線路規(guī)劃秉承距離近的CNC先進(jìn)行上下料作業(yè)的原則，可使得8h內(nèi)CNC作業(yè)時(shí)間多。由于具有2道加工工序的物料加工總時(shí)間遠(yuǎn)大于RGV移動(dòng)、上下料和清洗的時(shí)間，即出現(xiàn)多個(gè)CNC同時(shí)發(fā)出需求信號(hào)的幾率是非常小的，秉承模型合理性以及實(shí)用性的原則，本模型對(duì)RGV的線路規(guī)劃秉承距離近的CNC先進(jìn)行上下料作業(yè)的原則。

在RGV系統(tǒng)整個(gè)運(yùn)行過程中，RGV可分為3個(gè)主要階段：為執(zhí)行第1道工序的CNC進(jìn)行上下料操作、為執(zhí)行第2道工序的CNC進(jìn)行上下料操作和休息。假設(shè)RGV攜帶已完成第1道工序的物料，此時(shí)用于加工第2道工序的CNC是n（n≤N2）個(gè)發(fā)出需求、用于第2道工序的CNC中距RGV最近的CNC，從而使CNC的時(shí)間利用盡可能的充分，達(dá)到完成數(shù)量足夠多的目的。

算法設(shè)計(jì)：

除了的位置、完成本次加工物料時(shí)刻以及加工單個(gè)物料所需時(shí)間三個(gè)屬性，RGV的位置和時(shí)刻兩個(gè)屬性以外，由于需要確定RGV下一階段將對(duì)第幾道工序的CNC進(jìn)行上下料作業(yè)，因此對(duì)CNC增加是否攜帶物料屬性，此物料為僅完成第一道加工工序的物料，由于不是加工完成的熟料，故此物料不用執(zhí)行清洗作業(yè)。

本算法仍以RGV的時(shí)刻變化作為整個(gè)智能RGV系統(tǒng)的工作時(shí)間。對(duì)于RGV來說，只有為加工第1道工序的CNC換料、為加工第2道工序的CNC換料和原地等待三種狀態(tài)，且同一時(shí)間內(nèi)RGV只能執(zhí)行其中一項(xiàng)，因此可將RGV整個(gè)工作程序分解為RGV為執(zhí)行某一道工序的CNC進(jìn)行上下料的小步驟。

下面給出算法的詳細(xì)步驟：

（1）初始化CNCi的位置CNCi pos、完成本次加工物料時(shí)刻CNCi time、加工單個(gè)物料所需的時(shí)間t和CNCi是否攜帶物料，RGV的時(shí)間RGVt與RGVpos位置，用于加工第一道工序的CNC集合A以及用于加工第二道工序的CNC集合B。

（2）時(shí)間約束：判斷RGV的時(shí)間是否小于8h：如果是，執(zhí)行步驟（3）；如果不是，運(yùn)行停止。

（3）判斷RGV上是否有物料：如果是，執(zhí)行步驟（4）；如果不是，執(zhí)行步驟（7）；

（4）判斷集合B中是否有CNC發(fā)送需求：判斷用于加工第二道工序的CNC集合B中是否有RGV的時(shí)間RGVt大于CNCi的時(shí)間：如果是，執(zhí)行步驟（5）；如果不是，執(zhí)行步驟（6）；

（5）決定對(duì)集合B中的CNC作業(yè)順序并對(duì)CNCi和RGV的屬性更新：秉承距離近的CNC先進(jìn)行上下料作業(yè)的原則尋找全局最優(yōu)線路，確定RGV下一個(gè)進(jìn)行上下料作業(yè)的CNCi，并對(duì)CNCi的時(shí)間、RGV的時(shí)間、位置和是否攜帶物料進(jìn)行更新，應(yīng)注意此時(shí)對(duì)RGV時(shí)間RGVt的更新不包括對(duì)物料清洗的步驟，因?yàn)榇宋锪蠟閮H完成第一道加工工序的物料，下轉(zhuǎn)步驟（2）；

（6）集合B中沒有CNC發(fā)送需求信號(hào)，對(duì)RGV的時(shí)間進(jìn)行更新，RGV的時(shí)間CNCi為集合B中所有CNC時(shí)間中最小值，下轉(zhuǎn)步驟（4）；

（7）判斷集合A中是否有CNC發(fā)送需求：判斷用于加工第一道工序的CNC集合A中是否有RGV的時(shí)間RGVt大于CNCi的時(shí)間：如果是，執(zhí)行步驟（8）；如果不是，執(zhí)行步驟（9）；

（8）決定對(duì)集合A中的CNC作業(yè)順序并對(duì)CNCi和RGV的屬性更新：確定RGV下一個(gè)進(jìn)行上下料作業(yè)的CNCi，并對(duì)CNCi的時(shí)間、RGV的時(shí)間、位置以及是否攜帶物料進(jìn)行更新，下轉(zhuǎn)步驟（2）；

（9）集合A中沒有CNC發(fā)送需求信號(hào)，對(duì)RGV的時(shí)間進(jìn)行更新，RGV的時(shí)間CNCi為集合A中所有CNC時(shí)間中最小值，下轉(zhuǎn)步驟（7）。

4 模型結(jié)果

在2道工序中，我們計(jì)算出的結(jié)果示237，所得到的順序?yàn)?256。在2道工序模型的整個(gè)建立的過程中，采用粒子群算法進(jìn)行分配工序給CNC，這樣通過大量交叉、變異的方案，能做到相對(duì)最優(yōu)，得到次優(yōu)解，對(duì)CNC進(jìn)行動(dòng)態(tài)調(diào)度以時(shí)間優(yōu)先，RGV做決策也會(huì)影響CNC的等待時(shí)間，我們建立了RGV的搜索樹，進(jìn)行廣度搜索，這樣保證了不會(huì)陷入局部最優(yōu)解。

參考文獻(xiàn)

[1] 楊紅紅，吳智銘.基于自適應(yīng)遺傳算法的柔性動(dòng)態(tài)調(diào)度研究[J].中國(guó)機(jī)械工程，2002（21）：1845-1848.

[2] 唐然，龍騰銳，龍向宇宙.基于模糊聚類的改進(jìn)遺傳算法[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，31（2）：166-169.

[3] 殷文.改進(jìn)的并行遺傳模型的構(gòu)建及應(yīng)用[J].計(jì)算機(jī)工程，2008，34（4）：203-206.