改進和聲搜索的智能RGV動態調度策略研究*

于紅斌，周康壘，李俊霖

（河南師范大學計算機與信息工程學院,河南新鄉453007）

1 引 言

隨著先進制造技術的發展，一個工廠的業績與效率很大程度上取決于加工設備的智能化程度，智能加工系統已然成為現代化工廠的代名詞。有軌制導車輛RGV（Rail Guided Vehicle）作為一種無人駕駛、能在固定軌道上自由運行的智能車，可以根據指令自動控制移動方向和距離完成上下料及清洗物料等作業任務。智能RGV 調度問題屬于單處理機作業調度的多目標規劃問題，目的是要制定一種優化作業調度策略，旨在使系統效率達到最優。分析智能RGV 調度問題的相關文獻，大多數算法僅是單一指標優化問題[1-5]，在實際問題中，往往很難找到一種調度策略適用于所有的情況，因此在解決相關問題時，要結合問題制定適合的調度策略，且不能僅考慮其中一個因素而忽略其它因素，必須要全方位考慮才能使系統的作業效率達到最高。故此，從一個實際的生產實例出發，研究多指標RGV 調度問題，建立包含CNC 等待時間與RGV 調度運行時間的多目標函數，進而提出一種改進的和聲搜索（Improved Harmony Search,IHS）算法來求解目標函數的最優可行解，以解決智能RGV 的調度問題。

2 基于IHS的調度模型

和聲搜索算法(Harmony Search,HS)是一種新的群智能優化算法[6-7]，它通過調節每一維的變量來尋找近似最優解。但主要應用于連續優化區域，存在尋優精度低、早熟收斂和對離散問題求解效果不佳等缺點。

與傳統的連續優化HS 不同，改進算法采用離散優化策略，結合RGV 問題，通過動態的參數選擇微調RGV 調度策略，計算該RGV 調度策略相對應的各目標函數，動態替換和聲記憶庫（HarmonyMemory,HM）中最差的調度策略。其算法流程圖如圖1。

圖1 改進的和聲搜索算法流程圖

3 基于IHS的智能RGV動態調度

3.1 智能RGV系統構成

以2018 中國工業與應用數學協會全國大學生數學建模競賽B 題[8]所給出的數據為例，設定一種智能加工系統，由8 臺計算機數控機床（CNC）、1 輛軌道式自動引導車（RGV）、1 條RGV 直線軌道、1條上料傳送帶、1 條下料傳送帶等附屬設備組成，如圖2所示。

圖2 智能加工系統

3.2 智能RGV系統模型

3.2.1 優化目標函數

對于不同工序的物料加工，要使系統的工作效率盡可能高，則需要考慮CNC 的等待時間和RGV的移動距離所用時間這兩個主要因素。建立的數學模型如下:

目標函數式(1)的意義是：CNC 等待時間的標準差與RGV 移動距離所有時間之和的最小化。X=(x1,x2,...,xn)是一組可行解，表示CNC 加工物料的序列；ww11、ww22分別為 f1、f2的權重；f1表示可行解 X所對應的CNC 的等待時間標準差；f2表示RGV 移動距離所用的時間，有如下式：

其中，twait(xi)表示編號為 xi的CNC 從發出請求到受到響應所等待的時間；Taver表示CNC 發出請求到響應上下料的平均等待時間。

3.2.2 時間模型

為了增加模型的可靠性，CNC 等待時間采用遞歸算法計算、RGV 移動時間使用蒙特卡洛算法計算，如下式：

式（5）中，RTS 表示系統啟動作業前所需要檢測機器是否能正常工作的自檢時間，在此設置系統開機自檢時間以確保所有CNC 都能得到有效檢測，從而降低系統發生故障的概率；pos(xi)表示編號為xi的CNC在RGV 直線軌道上的位置，pos(xo)表示系統初始化狀態RGV所處的軌道位置（對于本改進智能加工系統，規定從RGV 軌道的左側開始依次編號，分別為1、2、3、4）；Tm 表示 RGV 由前一次響應位置移動到下一次響應位置所需的時間，Tmi表示移動i 個單位距離所需要的時間；Tc 表示為奇數編號的CNC 上下料所用的時間；TTww 表示RGV 清洗物料所用的時間；Tr 表示CNC 請求的時刻（包括空閑請求和加工完成的請求）。

3.2.3 模型評價指標

定義系統效率為加工一個物料所需的最短時間與實際加工的平均加工時間之比，以此作為評價系統性能的重要指標，如下式：

其中，實際加工一個物料所需要的時間包括CNC 的平均等待時間、RGV 的平均移動時間、加工一個物料所需要的時間以及上下料、清洗所用的時間。由于在對不同的CNC 上下料所用的時間不同，因此取二者的平均值Tcaver作為系統效率的計算。

4 實驗結果與分析

采用IHS 算法對上述初始化的模型優化求解設置適應一道工序加工情況下的模型參數：RTS=500s，ww11=ww22=0.5，在智能加工系統優化模型中，第i個物料加工的下料時刻等于編號為xi的CNC 的第i 次請求時刻Tr(xi)與一道工序物料加工所用的時間tfinish1之差，如下式所示：

在同一臺CNC 上，前一物料的下料時間即為下一物料的上料時間，即為：

這里，i 和j 分別為在同一臺CNC 上加工的相鄰兩個物料的編號。

將賽題所給第1 組測試數據數據作為系統參數，采用改進的和聲搜索算法計算RGV 為CNC 上料、下料的具體時刻，如表1所示。

表1 3000 秒內系統作業具體分布（第1 組）單位：秒

續表 單位：秒

其中，上料時刻和下料時刻分別為上料和下料的開始時間，以秒為單位。在一個作業班次內，系統開始啟動的時刻即為0 時刻。

系統在一個作業班次內三組測試數據結果對比如表2所示。

表2 一道工序的物料加工相關參數

由表2 可知，隨著參數的變動，系統作業效率均在95%左右且相差無幾，因此說明使用改進的IHS算法對RGV 進行動態調度的效率高，算法性能穩定。該算法的復雜度為O(nlnn)，對于高速而言，該算法運行的時間可以忽略不計。

5 結束語

對和聲搜索算法進行了改進，使之適用于離散優化模型。結合RGV 問題，提出多目標優化的離散策略，提高算法的局部搜索性能，實驗結果表明相比于標準和聲搜索算法，改進算法性能穩定。對于多道工序物料加工以及發生系統故障等情況，驗證算法的性能是今后要進一步開展的工作。