魏殿恩，郝歐亞，吳宇航

（1.華北理工大學數(shù)學建模創(chuàng)新實驗室，河北 唐山 063210；2.華北理工大學礦業(yè)工程學院，河北 唐山 063210；3.華北理工大學電氣工程學院，河北 唐山 063210）

0 引言

隨制造業(yè)的復興，人工智能技術和先進制造技術的融合，提高了制造業(yè)質量和效率[1]。RGV，即軌道式導引小車，是一種在車間或自動三維倉庫中沿著軌道運行的物料運輸工具。RGV 小車在運輸及倉儲方面的應用也越來越廣泛，如何以最優(yōu)路徑調度成為了當前需要解決的重要問題。楊康等以GPRS 和RFID 技術對軌道式電車的運行效率進行了研究分析[2]，馮倩倩等以狀態(tài)轉移公式對CNC 的分配進行了求解[3]，諸多學者利用差分進化法、分類討論法以及遺傳算法分析了兩道工序的加工作業(yè)情況[4-6]。本文基于2018 年全國大學生數(shù)學建模競賽的RGV 動態(tài)調度策略問題[7]，加以圖論組合優(yōu)化的RGV 動態(tài)調度模型思想[8]，重點解讀無故障的智能RGV 的兩道工序加工作業(yè)情況。

1 圖論組合優(yōu)化的調度模型思想

將系統(tǒng)中固定在軌道兩側的CNC 抽象為路徑網(wǎng)絡中的節(jié)點，其中將RGV 簡化為一個質點。將8 臺CNC上下料一次完整的過程看作為一個周期，根據(jù)就近的調度準則[9]，將第一輪上料順序理想簡化為先上料后下料的順序。

為了使RGV 的效率最高，擬定關于RGV 一個周期內運作時間的函數(shù)為：

為了避免目標路徑出現(xiàn)回路，要求：

xm n表示路徑是否通過路徑 ，等于0 表示未通過，1 表示已通過。

2 兩道工序最優(yōu)路徑的確立

每個物料的第一和第二道工序分別由兩臺安裝有不同刀具的CNC 完成。為使生產體系的工作效率最大化，針對兩種安裝不同刀具的CNC 的數(shù)量分配作了如下討論：

假設P1，P2 分別表示第一道工序和第二道工序所安排的CNC 平臺的數(shù)量。每一件物料的完成都需要兩道工序的配合。由賽題（文獻[7］）可知第一道工序加工時間小于第二道工序的加工時間。如果第一道工序和第二道工序安排的CNC 數(shù)量懸殊，而沒有完成第二道工序，顯然不會達到RGV 工作效率的最大化。經分析剔除第一工序CNC 平臺個數(shù)為一的情況。綜合考慮RGV 工作效率以及多方面的因素，將兩道工序的CNC 平臺的數(shù)量問題簡化為以下三種方案，其中P1 表示第一道工序加工的CNC 的數(shù)量，P2 第二道工序加工的CNC 的數(shù)量，方案如表1 所示：

表1 三種分配方案

基于各個方案中的兩道工序的CNC 平臺的數(shù)量，設置兩道工序CNC 平臺的分布情況，針對三種不同的方案分別進行討論。

2.1 二道工序加工作業(yè)方案一

由于第一道工序數(shù)量多于第二道工序數(shù)量所以先行確定第二道工序位置并得到相應的第一道工序位置。通過分析可知，第二道工序的位置有三種情況，分別為：

a) 相鄰的兩個CNC 平臺（機器號為CNC3#、CNC5#或者CNC4#、CNC6#）。

b) 兩個CNC 平臺處于對角線位置（機器號為CNC3#、CNC6#或者CNC4#、CNC5#）。

c) 兩個CNC 平臺處于相對位置（機器號為CNC3#、CNC4#或者CNC5#、CNC6#）。

比較圖1 的三種情況，得出兩項位置選取原則：同工序不同列、短時間工序放中間。

(1) 同工序不同列，以只加工一道工序的最短路徑為基礎，初步確立圖1 中的第一道工序順序為CNC1#—CNC8#—……—CNC2#，以此簡略分析六個CNC 平臺中的第一道工序完成后進入到第二道工序加工的過程中RGV 移動所需要的時間。

a 情況的RGV 移動時間：

c 情況的RGV 移動時間：

綜合式（4）～（5）， 得到T1＜T2，找出同工序不同列的位置選取原則。

（2）短時間工序在中間依據(jù)同工序不同列思想，比較b、c 情況的RGV 移動時間，c 情況的RGV 移動時間如下：

綜合式（4）～（6），得到T1＜T3，得出短時間工序在中間的位置選取原則。

2.2 二道工序加工作業(yè)方案二

基于方案一的位置確定策略，在本方案中可大致確定出帶有工序二刀頭的兩臺CNC 加工平臺的位置，如圖2，另外一個我們可以在A、B 和C 中選擇。

綜合考慮第一道工序完成后進入到第二道工序所需要的時間和第二道工序的CNC 加工平臺完全進入到工作狀態(tài)，經分析選取B、C 效果最優(yōu)并且B、C 的效果相同。即工序在同列位置的選取時具有相同的效果。最終以第三個第二道工序的CNC 加工平臺在B 位置，進行方案調度。

2.3 二道工序加工作業(yè)方案三

基于方案一的同工序不同列的原則與方案二中得出的結論工序在同列位置的選取時具有相同的效果，以圖3 等價位置圖為方案三的位置確定，進行對RGV的動態(tài)調度。

3 方案一、二和三動態(tài)調動的確立

基于圖論組合優(yōu)化的RGV 動態(tài)調度模型思想和動態(tài)最短路徑算法[10]得出三個方案在第一次進行第一道工序時RGV 所走路徑，依據(jù)就近原則選取加工第二道工序的CNC 平臺。由第一道工序完全進入第二道工序RGV 所走路徑如表2 所示。

表2 三種方案的二道工序RGV 最優(yōu)路徑

4 結論

在建立加工二道工序的動態(tài)調度模型中考慮多方案同時進行，以RGV 小車工作效率最高為目標，基于圖論組合優(yōu)化的RGV 動態(tài)調度模型思想和動態(tài)最短路徑算法得到了最優(yōu)路徑，使智能RGV 的兩道工序加工作業(yè)策略更加優(yōu)越。文中分析問題、解決問題用到的一些獨特的方法，對其他動態(tài)調度數(shù)學問題仍然適用。