張子凱 唐秋華 張利平 李梓響

1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，武漢，430081

2.武漢科技大學(xué)機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，武漢，430081

0 引言

裝配線是一種常用于汽車、電子等行業(yè)的產(chǎn)品制造系統(tǒng)。在裝配線上，產(chǎn)品從入口線的工位依次進(jìn)入下一工位進(jìn)行裝配，直到從出口線的工位出來(lái)。該過(guò)程中，工序的裝配順序需滿足工序間的優(yōu)先關(guān)系，且工位的加工時(shí)間應(yīng)小于節(jié)拍。不同于傳統(tǒng)的直線型裝配線，U型裝配線的同一工位既可以包含入口線工序，也可以包含出口線工序，這使得U型裝配線具有更高的生產(chǎn)效率和柔性。如今，自動(dòng)化技術(shù)已逐漸應(yīng)用到企業(yè)的裝配系統(tǒng)，機(jī)器人開(kāi)始逐漸替代工人在裝配線上進(jìn)行作業(yè)的裝配。

M ILTENBURC等［1］提出并構(gòu)建了U型裝配線平衡的數(shù)學(xué)模型后，眾多學(xué)者開(kāi)始研究U型裝配線平衡問(wèn)題。G?K?EN等［2］采用最短路徑法、OGAN等［3］提出分支定界法來(lái)求解簡(jiǎn)單U型裝配線平衡問(wèn)題。LI等［4］提出多規(guī)則啟發(fā)式算法求解第二類U型裝配線平衡問(wèn)題。RABBBANI等［5］同時(shí)考慮混流U型裝配線的工位負(fù)載和線效率，提出了基于規(guī)則編碼的遺傳算法來(lái)實(shí)現(xiàn)該類問(wèn)題的求解。張子凱等［6］設(shè)計(jì)了基于Bender分解的多目標(biāo)快速非支配遺傳算法來(lái)實(shí)現(xiàn)多重資源約束下的第一類U型裝配線平衡問(wèn)題的求解。查靚等［7］運(yùn)用基于信息素更新的蟻群算法求解第一類U型裝配線問(wèn)題。劉冉等［8］采用多目標(biāo)克隆免疫協(xié)同進(jìn)化算法來(lái)實(shí)現(xiàn)混流U型裝配線平衡與調(diào)度的多目標(biāo)集成優(yōu)化問(wèn)題的求解。唐秋華等［9］基于隨機(jī)機(jī)會(huì)約束規(guī)劃，通過(guò)確定性等價(jià)和線性化處理模型，采用GAMS/Cplex實(shí)現(xiàn)小規(guī)模U型裝配線的平衡問(wèn)題的優(yōu)化。

總體來(lái)看，上述研究主要是研究半自動(dòng)化或人工U型裝配線，主要目的是在生產(chǎn)節(jié)拍和優(yōu)先關(guān)系的約束下，將各裝配工序分配到工位。不同于該類裝配線，機(jī)器人裝配線不僅要分配工序到工位，還應(yīng)當(dāng)分配機(jī)器人到工位。因此為實(shí)現(xiàn)機(jī)器人U型裝配線工序和機(jī)器的協(xié)同優(yōu)化，本文以能耗為優(yōu)化目標(biāo)，提出一種基于隨機(jī)鍵編碼的混合灰狼優(yōu)化（hybrid gray w olf optim ization，HG?WO）算法，并將算法與原始灰狼算法進(jìn)行對(duì)比以證明算法的優(yōu)越性。

1 機(jī)器人U型裝配線

機(jī)器人U型裝配線由若干個(gè)工作站組成，每個(gè)工作站一般配備一個(gè)機(jī)器人來(lái)完成裝配工序，因此，機(jī)器人U型裝配線問(wèn)題主要涉及兩類問(wèn)題：工序分配和機(jī)器人分配。

U型裝配線中，某一工序的直接前序或直接后序分配到工作站，該工序才能進(jìn)行分配。為描述這種關(guān)系，URBAN［10］提出了影子優(yōu)先約束關(guān)系（圖1）?；谟白觾?yōu)先約束關(guān)系分配工序到工作站時(shí)，每個(gè)工作站的裝配時(shí)間應(yīng)當(dāng)小于或等于預(yù)定的節(jié)拍。

圖1 影子優(yōu)先約束關(guān)系Fig.1 Phantom p recedence relationship

分配機(jī)器人到工作站時(shí)，一般假設(shè)機(jī)器人的數(shù)量等于工作站的數(shù)量，且各工序在不同機(jī)器人上的裝配時(shí)間不同［11］。由于部分機(jī)器人不能裝配所有的工序，故當(dāng)某一機(jī)器人無(wú)法裝配某一工序時(shí)，設(shè)置其裝配時(shí)間為一個(gè)極大值。圖2展示了機(jī)器人U型裝配線。

機(jī)器人裝配線平衡問(wèn)題中，一般以能耗為其主要的優(yōu)化目標(biāo)。裝配線問(wèn)題中，能耗特指電能耗，主要包含兩部分：裝配能耗和待機(jī)能耗。各能耗分別與裝配時(shí)間和待機(jī)時(shí)間成正比［12］，計(jì)算公式如下：

式中，P1為裝配能耗；P2為待機(jī)能耗；P3為總能耗；n、m、r分別為工序數(shù)、工作站數(shù)和機(jī)器數(shù)；Xij(Yij)為1表示工序i分配到工作站j的入口線（出口線）；Zkj為1表示機(jī)器人k分配到工作站j；tik為工序i在機(jī)器人k上的裝配時(shí)間；Ek、Ik分別為機(jī)器人k的裝配單元能耗和待機(jī)單元能耗；C為節(jié)拍。

2 混合灰狼算法

原始的灰狼算法模擬灰狼尋找獵物的行為來(lái)搜索最優(yōu)解。灰狼社會(huì)有4種狼：α、β、δ和ω，其中，具有最佳適應(yīng)度的狼稱為α，具有第二、第三最佳適應(yīng)度的狼分別稱為β和δ，其余的狼稱為ω?；依撬惴ㄖ?，低等級(jí)的狼必須服從高等級(jí)的狼，所以算法中的狩獵過(guò)程（優(yōu)化過(guò)程）主要由α、β和δ引導(dǎo)ω包圍獵物，并不斷更新其位置，更新方式如下：

式中，t為當(dāng)前迭代次數(shù)；Xp為獵物位置；X為灰狼的位置；A、C為系數(shù)；r1、r2為服從［0，1］均勻分布的隨機(jī)變量；a在迭代過(guò)程中，從2到0線性下降。

在α、β和δ引導(dǎo)ω包圍獵物時(shí)，由于獵物的位置是未知的，該算法假設(shè)獵物位于α、β和δ之間，所以在α、β和δ引導(dǎo)下，灰狼ω位置更新如下：

其中，Xα、Xβ、Xδ分別為α、β和δ的位置。

上述灰狼算法常用來(lái)處理連續(xù)問(wèn)題，而機(jī)器人U型裝配線為一個(gè)離散問(wèn)題。為此，有效的編碼方式和進(jìn)化機(jī)制是實(shí)現(xiàn)灰狼算法求解機(jī)器人U型裝配線平衡問(wèn)題的關(guān)鍵。本文提出的混合灰狼算法采用隨機(jī)鍵編碼方式對(duì)種群個(gè)體進(jìn)行編碼，解碼中，考慮工序間的優(yōu)先關(guān)系約束和節(jié)拍約束，將工序和機(jī)器人分配到工位，計(jì)算灰狼的適應(yīng)度函數(shù)值（能耗值）。算法基于灰狼個(gè)體間的社會(huì)等級(jí)信息，選擇出3只最優(yōu)狼指引剩余個(gè)體進(jìn)化，防止算法陷入局部最優(yōu)，以實(shí)現(xiàn)種群的更新。最后，算法采用交叉算子，以實(shí)現(xiàn)種群間的信息交流。

2.1 編碼和解碼

機(jī)器人U型裝配線涉及工序和機(jī)器人的分配［13?15］，因此，種群初始化時(shí)，其編碼主要包含兩部分：工序編碼和機(jī)器人編碼。

工序編碼采用隨機(jī)鍵編碼方式，以實(shí)現(xiàn)連續(xù)問(wèn)題到離散問(wèn)題的轉(zhuǎn)換。該編碼包含N個(gè)要素，每一個(gè)要素為0、1之間的隨機(jī)數(shù)，且每一位置的隨機(jī)數(shù)表示對(duì)應(yīng)工序的權(quán)值。當(dāng)從可選工序集中選擇工序進(jìn)行分配時(shí)，權(quán)值最大的工序被挑選出來(lái)。可選工序集包含兩部分：入口線可選工序集和出口線可選工序集。依據(jù)影子優(yōu)先約束關(guān)系，若工序的所有直接前序工序已分配，則該工序進(jìn)入入口線可選工序集；若工序的所有直接后續(xù)工序已分配，則進(jìn)入出口線可選工序集。

如圖3所示，某一灰狼的工序權(quán)值編碼為{0.910 1，0.854 2，0.321 5，0.120 3，0.146 5，0.652 4，0.854 1，0.941 2，0.215 3}。由影子優(yōu)先約束關(guān)系圖（圖1）可知，初始入口線可選工序集為{1}，出口線可選工序集為{7，9}，則可選工序集中具有最大權(quán)值0.910 1的工序1被挑選出，存放到工序分配序列第一個(gè)位置，且被分配到入口線。由于工序1已被分配，則工序1從可選工序集中剔除，且此時(shí)工序2、3、4的所有直接前序工序1已被分配，則工序2、3、4進(jìn)入入口線可選工序集。更新后，入口線可選工序集為{2，3，4}，出口線可選工序集為{7，9}。第二次選擇時(shí)，可選工序集中具有最大權(quán)值0.852 4的工序2存放到工序分配序列第二個(gè)位置，且被分配到入口線。以此類推，直到所有的工序存放到工序分配序列。機(jī)器人編碼中，編碼長(zhǎng)度等于工位的數(shù)量且每一要素表示機(jī)器人代號(hào)。

上述工序編碼和機(jī)器編碼僅僅得到工序分配順序和機(jī)器人分配情況，而解碼方式則是進(jìn)一步獲取工序分配到工位情況以及獲取適應(yīng)度函數(shù)值。具體步驟如下：

（1）初始節(jié)拍值為

令當(dāng)前節(jié)拍C=C0，工作站序號(hào)j=1；

（2）按照工序分配序列，將工序i分配到工作站j中，若分配后的工作站裝配時(shí)間大于節(jié)拍C，則工作站序號(hào)j←j+1，將工序i重新分配到工作站j；

（3）重復(fù)步驟（2），直至工序全部分配；

（4）若工作站數(shù)量大于m，則令C←C+1，轉(zhuǎn)步驟（2）；

（5）計(jì)算能耗值。

2.2 進(jìn)化機(jī)制

根據(jù)原始灰狼算法包圍獵物的原理，利用適應(yīng)度函數(shù)最佳的3只灰狼α、β和δ引導(dǎo)其余灰狼ω包圍獵物，實(shí)現(xiàn)位置的更新。

2.3 交叉算子

原始灰狼算法只有最佳的3只灰狼α、β、δ與其余灰狼ω存在信息交流，最低等級(jí)的灰狼ω之間無(wú)信息交流。因此，為增強(qiáng)灰狼間的信息交流，該算法分別針對(duì)工序編碼和機(jī)器人編碼，提出兩種交叉方式：雙點(diǎn)工序交叉和單點(diǎn)機(jī)器人交叉。具體交叉方式如圖4、圖5所示。

圖3 編碼和解碼Fig.3 Encode and decode

圖4 雙點(diǎn)工序交叉Fig.4 Two-point task crossover

圖5 單點(diǎn)機(jī)器人交叉Fig.5 Single-poin t robot crossover

混合灰狼算法的流程如圖6所示。

圖6 混合灰狼算法流程Fig.6 Flow chart of hybrid grey wolf op tim ization

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

為驗(yàn)證HGWO算法的性能，將HGWO算法與GWO算法進(jìn)行對(duì)比。兩種算法都采用C語(yǔ)言進(jìn)行編程，并在同一臺(tái)電腦上運(yùn)行，電腦配置為：Intel Core i5 CPU，2.80 GHz and 2.00 GB RAM。實(shí)驗(yàn)案例選取大規(guī)模U型裝配線標(biāo)桿案例：A rcus111，Barthol148和Scholl297。3個(gè)案例的工序數(shù)n分別為111、148、297。且每個(gè)案例分別設(shè)置4種規(guī)模的工作站數(shù)量：A rcus111中，m=9，13，17，22；Barthol148中，m=10，14，21，29；Scholl297中，m=19，29，38，50。機(jī)器人的數(shù)量r等于工作站的數(shù)量。案例的優(yōu)先關(guān)系和裝配時(shí)間來(lái)自專業(yè)裝配線網(wǎng)站https：//assembly?line?balancing.de/。工序在不同機(jī)器人上的加工時(shí)間在［0.8ti，1.2ti］中隨機(jī)生成（ti為工序 i的裝配時(shí)間），單元能耗值在［0.2，3.0］中隨機(jī)生成［12］。算法終止條件設(shè)置為運(yùn)行時(shí)間n×n×10和n×n×20。

算法對(duì)比前，采用M initab中的田口實(shí)驗(yàn)對(duì)算法進(jìn)行參數(shù)校驗(yàn)，得出最佳參數(shù)組合。HGWO最佳參數(shù)組合為：種群規(guī)模40，交叉概率0.7；GWO最佳參數(shù)組合為：種群規(guī)模40。

對(duì)比試驗(yàn)中，每一個(gè)案例運(yùn)行10次，獲取總能耗的最小值和平均值。表1、表2分別展示了2種終止條件下的對(duì)比結(jié)果。

表1 終止條件為n×n×10的對(duì)比結(jié)果Tab.1 Com parative resu lts of term inal condition n×n×10

表2 終止條件為n×n×20的對(duì)比結(jié)果Tab.1 Com parative results of term inal condition n×n×20）

由表1、表2可知，在不同的案例，兩種終止條件下，HGWO所獲得能耗最小值和平均值基本都要小于GWO獲取的結(jié)果。從而證明了所提出的HGWO算法在求解機(jī)器人U型裝配線能耗優(yōu)化問(wèn)題時(shí)具有顯著的優(yōu)越性。

圖7為HGWO算法求解A rcus111問(wèn)題的收斂圖，即能耗隨迭代次數(shù)的變化曲線。由圖7可知，在算法運(yùn)行到70代左右時(shí)，算法收斂很快；70～308代時(shí)，算法收斂變慢，但種群還在持續(xù)進(jìn)化；308代之后，算法基本不再進(jìn)化。這表明HGWO算法在求解該問(wèn)題時(shí)具有較好的收斂性。

圖7 HGWO算法收斂圖Fig.7 Convergence of HGWO algorithm

為分析能耗的降低是否會(huì)影響裝配線常規(guī)目標(biāo)——節(jié)拍值，本文分析了不同方案的工序分配、機(jī)器人分配和目標(biāo)值。表4展示了兩種方案的工序和機(jī)器人布局，以及節(jié)拍值和能耗值。所分析的案例為A rcus111標(biāo)桿案例，工序數(shù)為111，工作站和機(jī)器人數(shù)為9。方案1為HGWO算法的第一代最優(yōu)解的分配方案，方案2為算法優(yōu)化后，得到的最優(yōu)解的分配方案。由表4可知，由于方案1中工序分配很不均勻，其最終的節(jié)拍值和能耗都很大，分別為755和9 252.28。方案2工序分配比較均勻，每個(gè)工作站的工序數(shù)量都在13左右，且節(jié)拍值和能耗都要小于方案1，分別為709和8 756.12。由此可以發(fā)現(xiàn)，在算法優(yōu)化能耗的同時(shí)，節(jié)拍值也在逐漸減小，表明能耗的降低也會(huì)影響裝配線的傳統(tǒng)目標(biāo)——節(jié)拍。因此，在實(shí)際裝配線布局時(shí)，企業(yè)可以以能耗為目標(biāo)，來(lái)平衡裝配線的生產(chǎn)負(fù)載。這樣既可以達(dá)到負(fù)載均衡的目的，也能降低企業(yè)的生產(chǎn)能耗。

表4 能耗節(jié)能方案對(duì)比表Tab.4 Com parative results of the energy consum p tion p lans

4 結(jié)語(yǔ)

針對(duì)當(dāng)前逐漸推廣的機(jī)器人U型裝配線問(wèn)題，本文以能耗為優(yōu)化目標(biāo)，介紹了機(jī)器人U型裝配線平衡問(wèn)題，并采用混合灰狼算法求解了該問(wèn)題。算法采用隨機(jī)鍵編碼方式實(shí)現(xiàn)工序編碼，將連續(xù)問(wèn)題離散化。針對(duì)問(wèn)題中的工序分配和機(jī)器人分配，引入兩種交叉算子，實(shí)現(xiàn)算法中最低等級(jí)灰狼之間的信息交流。通過(guò)與原始灰狼算法的對(duì)比，驗(yàn)證了混合灰狼算法性能的可行性和有效性。在未來(lái)的研究中，可以將生產(chǎn)中的負(fù)載問(wèn)題與能耗問(wèn)題進(jìn)行協(xié)同優(yōu)化。