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

于紅斌，周康壘，李俊霖

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

1 引 言

隨著先進(jìn)制造技術(shù)的發(fā)展，一個(gè)工廠的業(yè)績(jī)與效率很大程度上取決于加工設(shè)備的智能化程度，智能加工系統(tǒng)已然成為現(xiàn)代化工廠的代名詞。有軌制導(dǎo)車輛RGV（Rail Guided Vehicle）作為一種無人駕駛、能在固定軌道上自由運(yùn)行的智能車，可以根據(jù)指令自動(dòng)控制移動(dòng)方向和距離完成上下料及清洗物料等作業(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)問題時(shí)，要結(jié)合問題制定適合的調(diào)度策略，且不能僅考慮其中一個(gè)因素而忽略其它因素，必須要全方位考慮才能使系統(tǒng)的作業(yè)效率達(dá)到最高。故此，從一個(gè)實(shí)際的生產(chǎn)實(shí)例出發(fā)，研究多指標(biāo)RGV 調(diào)度問題，建立包含CNC 等待時(shí)間與RGV 調(diào)度運(yùn)行時(shí)間的多目標(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)精度低、早熟收斂和對(duì)離散問題求解效果不佳等缺點(diǎn)。

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

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

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

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

以2018 中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)協(xié)會(huì)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B 題[8]所給出的數(shù)據(jù)為例，設(shè)定一種智能加工系統(tǒng)，由8 臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（CNC）、1 輛軌道式自動(dòng)引導(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ù)

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

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

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

3.2.2 時(shí)間模型

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

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

3.2.3 模型評(píng)價(jià)指標(biāo)

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

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

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

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

在同一臺(tái)CNC 上，前一物料的下料時(shí)間即為下一物料的上料時(shí)間，即為：

這里，i 和j 分別為在同一臺(tái)CNC 上加工的相鄰兩個(gè)物料的編號(hào)。

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

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

續(xù)表 單位：秒

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

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

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

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

5 結(jié)束語

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