基于粒子群算法的兩道工序RGV動態調度模型

伊新銅

摘 要：本文針對基于CNC和RGV構成的智能加工系統的動態調度進行了詳細研究，建立了2道工序在無故障的動態優化模型，并分別利用貪心算法和遺傳算法對所建優化模型進行求解。本文運用搜索樹對每一次RGV確定CNC的上下料作業順序進行決策，搜索域為與RGV距離最短的3個CNC，尋找最短的遍歷3個CNC的路徑，通過運行算法輸出第一組、第二組、第三組產出熟料的數量分別為371、346、371。

關鍵詞：動態調度模型 粒子群算法 搜索樹

中圖分類號：TP39 文獻標識碼：A 文章編號：1674-098X（2019）04（a）-0124-02

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

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

對于有n（n=2）道加工工序的物料，將RGV的工作狀態分為為第 道工序進行上下料幾個作業狀態，并考慮到n道加工順序和CNC出現故障后維修時間的連續性，找到一種可行的調度方案，使CNC在時間約束下空閑時間最小。

1 符號說明

符號說明，如表1所示。

2 模型假設

（1）CNC系統在整個系統運行過程中，保持正常運行；（2）每臺CNC前的傳送帶提供物料量遠大于RGV的需求量，由于傳送帶造成的微小誤差可忽略不計；（3）CNC在換刀片的過程中可以直接更換，不需要更換的時間；

3 模型的建立與求解

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

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

算法設計：

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

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

下面給出算法的詳細步驟：

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

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

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

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

（5）決定對集合B中的CNC作業順序并對CNCi和RGV的屬性更新：秉承距離近的CNC先進行上下料作業的原則尋找全局最優線路，確定RGV下一個進行上下料作業的CNCi，并對CNCi的時間、RGV的時間、位置和是否攜帶物料進行更新，應注意此時對RGV時間RGVt的更新不包括對物料清洗的步驟，因為此物料為僅完成第一道加工工序的物料，下轉步驟（2）；

（6）集合B中沒有CNC發送需求信號，對RGV的時間進行更新，RGV的時間CNCi為集合B中所有CNC時間中最小值，下轉步驟（4）；

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

（8）決定對集合A中的CNC作業順序并對CNCi和RGV的屬性更新：確定RGV下一個進行上下料作業的CNCi，并對CNCi的時間、RGV的時間、位置以及是否攜帶物料進行更新，下轉步驟（2）；

（9）集合A中沒有CNC發送需求信號，對RGV的時間進行更新，RGV的時間CNCi為集合A中所有CNC時間中最小值，下轉步驟（7）。

4 模型結果

在2道工序中，我們計算出的結果示237，所得到的順序為0256。在2道工序模型的整個建立的過程中，采用粒子群算法進行分配工序給CNC，這樣通過大量交叉、變異的方案，能做到相對最優，得到次優解，對CNC進行動態調度以時間優先，RGV做決策也會影響CNC的等待時間，我們建立了RGV的搜索樹，進行廣度搜索，這樣保證了不會陷入局部最優解。

參考文獻

[1] 楊紅紅，吳智銘.基于自適應遺傳算法的柔性動態調度研究[J].中國機械工程，2002（21）：1845-1848.

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

[3] 殷文.改進的并行遺傳模型的構建及應用[J].計算機工程，2008，34（4）：203-206.