多約束條件下智能RGV 的動態調度策略

張雨萌，胡正凱，王保榮，吳宇航

(1. 華北理工大學 數學建模創新實驗室，河北 唐山 063210；2. 華北理工大學 理學院，河北 唐山 063210； 3. 華北理工大學 電氣工程學院，河北 唐山 063210；4. 華北理工大學 化學工程學院，河北 唐山 063210； 5. 河北省數據科學與應用重點實驗室，河北 唐山 063210；6. 唐山市數據科學重點實驗室，河北 唐山 063210)

0 引言

智能加工系統[1]由8 臺計算機數控機床（CNC）、1 輛軌道式自動引導車（RGV）、1 條RGV 直線軌道、1 條上料傳送帶、1 條下料傳送帶等附屬設備組成。RGV 是一個由機械手臂、兩只機械手爪和物料清洗槽組成的具有智能控制的小車，其清洗槽每次只能清洗1 個物料，機械手臂前端有2 個手爪，通過旋轉可以先后各抓取1 個物料，可以完成上下料作業，通過給CNC 進行取放料，進行動態調度，使其達到最優的生產效率。通過研究確定了RGV 的調度策略、建立RGV 動態調度[2]模型，使得該系統在不同工作情況下具有最優的工作效率。

1 基于路程時間差限定的放料順序的確定

對零件的加工分析，由于8 個CNC 工作臺初始狀態是都沒有放上需加工的零件的，首先，需要對8 個CNC 工作臺進行放料工作，對8 個CNC 工作臺進行全排列，選取其中一種排列方式進行第一批放料工作，從而使得每個CNC 工作臺都會加工第一批加工器件，由于初始位置是CNC1#和CNC2#正中間，若對8 個CNC 工作臺進行全排列，放定第一批的8 個器件，不同放料排列方式之間會產生初始的路程時間差，若選定了最優的排列方式，可以將系統調制最優狀態，初試的路程時間差可以忽略不計。可以將放置第一個零件開始時刻定義為系統0 時刻。

對第一批放料的過程進行模擬，將不同順序放料的零件進行第一批放料，如下式：

其中，Lit→j表示從i位置到j位置所用時間，Ftm、Ftn表示取放料所用時間，m為1、3、5、7，n為2、4、6、8，Jt表示零件加工時間，Qt表示零件清洗所用時間，En表示第n個零件加工結束時間，Fn表示第n個零件放料結束時間，Dt表示CNC工作臺等待RGV小車的時間，Mt1→i表示從0時刻開始計時，從1位置放料開始到第i位置放料完成時間總和。

為了使系統達到最優狀態應使得所有的Dt總和達到最小，即此系統達到了最優的工作效率，若初始的Dt總和達到了最小，往后的每批原件都會達到最優，其間還應考慮第一批最后一個零件清洗結束時間和第二批第一個零件的加工結束時間，若第一批最后一個零件清洗結束時間比第二批第一個零件的加工結束時間晚，可以使RGV小車沒有停留時間一直處于工作狀態。

第一批最后一個零件清洗結束時間為：

第二批第一個零件的加工結束時間為：

上述兩個時間差受 Lt總、Lt8→1、D1t大小所控制的系統，然而 Lt8→1、 D1t大小均受 Lt總所影響，因此通過這個限制條件從8 個CNC 工作臺全排列中選取最優的一種排列方式，即可達到系統最優。通過對此限制條件進行求解計算出一道工序下第一組的最優放料順序為35281746，此種放料順序生產一批零件耗時最短，從而使整個系統達到最優狀態。

2 基于約束條件下的排隊論模型

確定好放料順序后，采用就近原則下的仿真算法，正在服務的CNC 序號用1-8 表示，采用0 表示非加工狀態，1 表示加工狀態，同時累加CNC 的加工時間，RGV 記為4 個狀態，1 表示正在上下料，2 表示正在清洗，3 表示正在移動，0 表示等待狀態，CNC 處理工序的組合方式為窮舉法。

采用計時循環，以秒為單位，首先分別預計8 臺機床的過渡時間，采用DX 表示服務狀態，G 表示工序時間，XT 表示CNC 加工累計時間值，Z 表示正在服務的CNC 序號，FZ 表示正要或剛完成某序號的CNC 服務，j 表示8 個工序，X 表示加工或非加工狀態，T 表示正在執行周期時間向量。

上式1 表示剛完成服務的CNC，式子2 表示正在服務的CNC,式子3 表示CNC 加工狀態，式子4表示CNC 等待狀態，通過計算RGV 上下料時間，移動到各CNC 所需的時間，清洗時間等，需要考慮各個CNC 剩余的加工時間與RGV 移動至CNC 的較大時間，因此對RGV 判斷判定如下：

上式1 表示處于上下料階段，式子2 處于清洗階段，式子3 處于運動階段，式子4 處于RGV 等待狀態。F 表示的是RGV 計數變量，CT 表示執行命令累加時間向量。

綜上所述，通過就近原則的仿真得到對于一道工序的器件，在第一組生產數據下可以生產376 件，在第二組生產數據下可以生產359 件，在第三組生產數據下可以生產385 件。

3 兩道工序的調度模型的改進

3.1 兩道工序的生產過程分析

與上述一道工序的研究相比，兩道工序的生產過程實質是在此基礎上加入了“分組”的情況，即兩個CNN 工作臺為一組共同處理物料，不同的分組會使RGV 在移動過程中耗時不同進而產生生產效率的差別[3]。于是，通過改進遺傳算法來確定對CNN 的分組情況及RGV 移動的最優路徑[4]。

3.2 遺傳算法的引入與改進

（1）種群初始化

種群初始化是對遺傳個體進行編碼，8 個CNN 工作臺編號分別為 1、2、3、4、5、6、7、8，RGV有4 個位置編號分別為1、2、3、4，當RGV 處在位置編號1、2、3、4 時分別為CNN 工作臺1 和2號、3 和4 號、5 和6 號、7 和8 號提供服務。然后，隨機選定4 個工作臺作為第一道工序的加工器，另外4 個作為第二道工序的加工器，兩種加工器自由結合實現分組，生成種群個體[5]。

（2）選擇

計算每個個體的目標函數值。首先，在加工生產物料時，RGV完成最后一個清洗任務所用的時間即為完成此組任務所用的時間，即為一個個體的目標函數值，具體包括上下料時間、加工時間、清洗時間、移動時間。然后，用基于排序的適應度分配方法[7]計算每個個體的適應度fi=2-p+2(p-1)(n-1）/(N-1)p∈[1,2]，其中fi為個體i的適應度，N為種群大小，n為個體在種群中的序位，p為選擇壓差。最后，計算每個個體的選擇概率，通過隨機遍歷抽樣法[7]可得到第i個個體的選擇概率Fi。此過程中，選擇的個體數目M=N×G，其中M為選擇的個數；G為代溝，取值為0.7～0.9。

最后計算每個人個體的選擇概率

式中：Fi為第i個個體的選擇概率，選取的方式采用隨機遍歷抽樣法。

（3）交叉

交叉操作產生全局較優解。此處采用部分匹配交叉的方法進行交叉操作[8]，首先在2個父個體中隨機選擇2個交叉點，如表1所示。

表1 有2個插入點的2個父個體Table 1 Two Parents with Two Insertion Points

然后交換中間的基因段，保留2 個父個體中兩端與中間段不重復的任務基因段， 并根據中間段的任務對應關系，得到2 個子個體，如表2 所示。

表2 交叉完成后的2 個子個體 Table 2 Two Subindividuals after Cross Completion

（4）變異

通過變異產生更多種類的個體，來局部優化[9]個體。

（5）判斷

判斷是否滿足終止條件，終止條件包括是否到達終止代數，目標值、適應度是否滿足要求等[10]。滿足終止條件時終止得到CNN 的最優分組，否則開始下一次循環。

通過采用遺傳算法迭代與仿真技術的結合[11]，模擬加工過程，主要分為判斷清洗料的屬性、計算移動后裝載的時間變化、記錄車的料等。對工序機進行約束，零件1 計數變量用NA 表示，零件2 計數變量用NB 表示，NA＞NB, 在第二道工序的CNC 中取較小者，NA = NB, 在第二道工序的CNC 中取較小者，NB＞NA, 在所有CNC 的較大時間中取較小者。同時記錄總加工量、剩余未完成的加工量和組合最佳方案等[12]。 最終得到在第一組生產數據下可以生產211 件，在第二組生產數據下可以生產182件，在第三組生產數據下可以生產222 件。

4 結論

本文給出了基于路程時間差限定的放料順序的確定模型和基于約束條件下的排隊論模型以及對兩道加工工序的改進方法，最終確定了最優的放料順序為35281746，基于排隊論模型的加工順序增加了加工件數。運用遺傳算法對兩道工序的加工方法進行改進，很大程度上提高了系統的工作效率。