基于TSP模擬退火的智能RGV動態調度問題

李夢琳 馬雯秋

[摘要]本文圍繞著智能RGV的動態調度問題進行研究。以TSP問題為基礎，建立了基于TSP問題的啟發式RGV動態調度模型，并利用模擬退火算法進行求解，給出了一道工序情況下的RGV動態調度策略。

[關鍵詞]TSP;最優序列;模擬退火算法

一、問題重述

一個智能加工系統包括8臺計算機數控機床（CNC）CNC#1-CNC#8、1輛軌道式自動引導車（RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶。RGV是一種既可無人駕駛又可以在固定軌道上自由運行的智能車，它能夠根據指令控制自身移動距離和方向，且其自帶一個機械手臂、兩只機械手爪和物料清洗槽，從而能完成上下料及清洗物料等任務。

針對一道工序的物料加工作業情況：每臺CNC安裝相同刀具，物料可在任一臺CNC上完成加工。對于一般問題進行研究，給出RGV的動態調度模型和其相應的求解算法。

二、模型的建立與求解

在智能加工系統工作過程中，通常當CNC處于空閑狀態或加工完成時會立即向RGV發出上料需求信號，此時RGV會接受CNC發出的信號并自行判斷CNC的上下料作業次序，并通過發送指令信號來確定其服務CNC上下料的個數和順序。考慮到一道工序系統作業流程是周期性循環的，因此定義一個作業周期是RGV為系統內所有CNC完成一輪服務的過程，在考慮RGV的調度問題時，由于RGV服務CNC的順序不同會導致一個作業周期的時間不同，因此在制定調度策略時，我們要確定一個作業周期內RGV服務CNC的最優序列。

為了確定最優服務序列，我們需要分別確定序列中元素的個數和順序。在一個作業周期內，使總時間最小的循環工作的CNC個數是最優序列個數。根據相關智能加工系統作業參數的數據計算得知，最優序列的元素個數為8個。

以下將基于SP算法確定最優序列。

設加工系統一個周期作業的總時間為T=t₁+t₂，其中t₁表示RGV為所有CNC提供上下料服務所需的時間，t₂表示RGV移動過程所需的時間。

由于在一個周期內，RGV服務的對象為CNC#1-CNC#8，因此RGV為CNC提供上下料服務的時間在不同序列順序情況下都保持不變，而t₂會受到序列順序的影響，因此，若希望總時間T最小，需找到RGV服務CNC的最佳順序使得t₂最小。

考慮到序列中的元素個數為8，因此RGV在一次作業周期中對每臺CNC都提供服務且只提供一次服務，因此我們建立基于TSP的RGV動態調度模型。

由于此問題是一個較復雜的優化問題，由于Lingo求解不一定能夠得到全局最優解，因此采用模擬退火算法來尋求全局最優解。

針對以上通過模擬退火方法求得的CNC最優序列解，給出以下RGV調度方案：

考慮到RGV的移動受到CNC發出信號的影響，當有CNC向RGV發出信號時，RGV才會移動，而不同CNC發出信號的過程中，就存在RGV向哪邊移動的選擇問題，因此我們通過考慮CNC的信號發出情況來制定RGV的調度策略。

首先將信號的發出順序分為兩種：不同CNC同時發出信號、不同CNC先后（不同時）發出信號。

RGV在收集到CNC的需求信號后，會做出相應的判斷和選擇，決定前往工作臺的順序。若信號均不同時發出，則RGV收到何處的信號，就前往何處進行作業，即按照CNC信號發出時間先后順序來決定RGV的移動;若存在信號同時發出，則需要RGV做出相應的判斷，此時需要將同時發出的信號位置進行歸類處理，以傳送帶為中心對稱分布的兩臺 CNC作為一類信號（忽略縱向分布的工作臺的先后順序帶來的影響，只考慮橫向分布的工作臺的信號發出順序），可以分出四類信號，結果如表1。

將同時發出信號數量作為分類指標進行歸類整理，分別針對不同的情況進行調度策略的選擇。

其次企業只需根據實際情況制定調度策略即可。

最后針對此模型，作出如下評價：

將RGV與CNC之間的動態調度關系抽象為序列，構造TSP模型，尋找總路程最小的回路圈，具有一定的新穎性與合理性。本文使用了模擬退火算法找出TSP的最優解，結果真實可靠，計算方便。通過TSP問題求解出的最優解對應的序列，來求解具體每個零件的加工CNC序號、開始加工時間以及加工結束時間需要一定的計算過程。

參考文獻：

司守奎，孫兆亮.數學建模算法與應用（第二版[M].北京：國防工業出版社，2015.