改進(jìn)和聲搜索的智能RGV動態(tài)調(diào)度策略研究*

于紅斌，周康壘，李俊霖

（河南師范大學(xué)計算機(jī)與信息工程學(xué)院,河南新鄉(xiāng)453007）

1 引 言

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

2 基于IHS的調(diào)度模型

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

與傳統(tǒng)的連續(xù)優(yōu)化HS 不同，改進(jìn)算法采用離散優(yōu)化策略，結(jié)合RGV 問題，通過動態(tài)的參數(shù)選擇微調(diào)RGV 調(diào)度策略，計算該RGV 調(diào)度策略相對應(yīng)的各目標(biāo)函數(shù)，動態(tài)替換和聲記憶庫（HarmonyMemory,HM）中最差的調(diào)度策略。其算法流程圖如圖1。

圖1 改進(jìn)的和聲搜索算法流程圖

3 基于IHS的智能RGV動態(tài)調(diào)度

3.1 智能RGV系統(tǒng)構(gòu)成

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

圖2 智能加工系統(tǒng)

3.2 智能RGV系統(tǒng)模型

3.2.1 優(yōu)化目標(biāo)函數(shù)

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

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

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

3.2.2 時間模型

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

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

3.2.3 模型評價指標(biāo)

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表1 3000 秒內(nèi)系統(tǒng)作業(yè)具體分布（第1 組）單位：秒

續(xù)表 單位：秒

其中，上料時刻和下料時刻分別為上料和下料的開始時間，以秒為單位。在一個作業(yè)班次內(nèi)，系統(tǒng)開始啟動的時刻即為0 時刻。

系統(tǒng)在一個作業(yè)班次內(nèi)三組測試數(shù)據(jù)結(jié)果對比如表2所示。

表2 一道工序的物料加工相關(guān)參數(shù)

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

5 結(jié)束語

對和聲搜索算法進(jìn)行了改進(jìn)，使之適用于離散優(yōu)化模型。結(jié)合RGV 問題，提出多目標(biāo)優(yōu)化的離散策略，提高算法的局部搜索性能，實(shí)驗(yàn)結(jié)果表明相比于標(biāo)準(zhǔn)和聲搜索算法，改進(jìn)算法性能穩(wěn)定。對于多道工序物料加工以及發(fā)生系統(tǒng)故障等情況，驗(yàn)證算法的性能是今后要進(jìn)一步開展的工作。