基于改進(jìn)多目標(biāo)灰狼算法的裝配線平衡與預(yù)防維護(hù)集成優(yōu)化

蒙 凱,唐秋華+,張子凱,盧辰灝,鄧明星

(1.武漢科技大學(xué) 冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081;2.武漢科技大學(xué) 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081;3.東風(fēng)雷諾汽車有限公司設(shè)備保全科,湖北 武漢 430056;4.武漢科技大學(xué) 汽車與交通工程學(xué)院，湖北 武漢 430081)

0 引言

裝配線平衡和設(shè)備維護(hù)是保證整條裝配線高效運(yùn)行的兩個(gè)獨(dú)立子系統(tǒng)，即在生產(chǎn)進(jìn)行之前，利用裝配線平衡確保整條裝配線上各工位的負(fù)載均衡，以更好地發(fā)揮裝配線生產(chǎn)效率；設(shè)備維護(hù)是按規(guī)定計(jì)劃或技術(shù)規(guī)程進(jìn)行的設(shè)備管理活動(dòng)，設(shè)備維護(hù)常分為故障維護(hù)與預(yù)防維護(hù)，旨在控制設(shè)備性能劣化或降低設(shè)備失效概率。由于裝配線平衡和設(shè)備維護(hù)的相對(duì)獨(dú)立，在現(xiàn)行裝配生產(chǎn)中逐漸表現(xiàn)出以下兩個(gè)問題：

(1)由于裝配線平衡是在假定所有工位都正常工作的前提下做出的，且裝配線上各工位具有串行流水特征，當(dāng)其中一個(gè)工位突發(fā)故障或任一工位上設(shè)備需要維護(hù)時(shí)，必然要求整條裝配線停工。其中未發(fā)生故障或不需要維護(hù)工位的被迫停機(jī)，自然導(dǎo)致產(chǎn)能的巨大浪費(fèi)和成本的巨幅提升。

(2)故障維護(hù)是在設(shè)備出現(xiàn)故障后的事后維護(hù)，預(yù)防維護(hù)是為確保設(shè)備工作狀態(tài)的提前性維護(hù)，裝配線平衡是在生產(chǎn)進(jìn)行之前的計(jì)劃性任務(wù)分配。從時(shí)間上來說預(yù)防維護(hù)和裝配線平衡都需要提前進(jìn)行。但是兩者的目標(biāo)不一致，常發(fā)生時(shí)間沖突。裝配線平衡的目標(biāo)是使整條裝配線快速高效運(yùn)轉(zhuǎn)，預(yù)防維護(hù)目標(biāo)是設(shè)備的可靠性或可用度高。當(dāng)生產(chǎn)任務(wù)或設(shè)備維護(hù)任務(wù)很重時(shí)，如何協(xié)調(diào)工位維護(hù)時(shí)間或裝配生產(chǎn)時(shí)間，避免兩者之間的時(shí)間沖突，目前還缺乏有效依據(jù)。

據(jù)此，需將裝配線平衡與工位設(shè)備預(yù)防維護(hù)進(jìn)行集成優(yōu)化，制定出能提供設(shè)備維護(hù)契機(jī)、保證維護(hù)時(shí)生產(chǎn)連續(xù)性的多套分配方案。在正常生產(chǎn)過程中，如果某工位設(shè)備需要進(jìn)行預(yù)防維護(hù)，可按照預(yù)先制定的生產(chǎn)計(jì)劃，快速從一套分配方案切換到另一套方案。通過生產(chǎn)的快速調(diào)整，提升生產(chǎn)時(shí)的設(shè)備可維護(hù)性和維護(hù)時(shí)的生產(chǎn)連續(xù)性，避免因設(shè)備維護(hù)造成整線停機(jī)所致的生產(chǎn)損失，而且對(duì)提高工位利用率和縮短產(chǎn)品制造周期，也具有重要意義。

在已發(fā)表文獻(xiàn)中，還未見將裝配線平衡與工位預(yù)防維護(hù)集成優(yōu)化的研究，然而在裝配線平衡、預(yù)防維護(hù)和生產(chǎn)調(diào)度與預(yù)防維護(hù)集成優(yōu)化等相關(guān)領(lǐng)域，具有很多研究基礎(chǔ)。首先在裝配線平衡方面，根據(jù)所優(yōu)化目標(biāo)的不同，將問題分為3類：第Ⅰ類問題給定節(jié)拍，優(yōu)化工位數(shù)量[1]；第Ⅱ類問題給定工位，最小化節(jié)拍[2-3]；第Ⅲ類問題給定節(jié)拍和工位，最大化生產(chǎn)線效率。裝配線平衡與工位預(yù)防維護(hù)的集成優(yōu)化，實(shí)質(zhì)上是在工位給定情形下最小化多重生產(chǎn)節(jié)拍與生產(chǎn)調(diào)整，可算是第Ⅱ類問題的變體。

關(guān)于設(shè)備預(yù)防維護(hù)，方玲珍等[4]以單位維護(hù)成本的產(chǎn)出最大化為優(yōu)化目標(biāo)，構(gòu)建了一種維護(hù)效率導(dǎo)向的設(shè)備預(yù)防維護(hù)模型。Seiti[5]等提出一種表達(dá)模糊可靠性的新模糊模型，并考慮了可能因素的風(fēng)險(xiǎn)和誤差，將其用于多期時(shí)間范圍內(nèi)的預(yù)防維護(hù)計(jì)劃。但對(duì)平衡與維護(hù)的集成優(yōu)化問題而言，上述問題僅考慮了設(shè)備預(yù)防維護(hù)，并不能實(shí)現(xiàn)維護(hù)時(shí)連續(xù)生產(chǎn)的目標(biāo)。

生產(chǎn)調(diào)度與預(yù)防維護(hù)的集成優(yōu)化，目前僅在加工車間、流水車間等方面有相關(guān)研究。如蔣凱麗等[6]等針對(duì)兩階段的混合流水線系統(tǒng)，考慮具有時(shí)間窗的周期性維護(hù)需求，以最小化最大完成時(shí)間為調(diào)度指標(biāo)，建立調(diào)度與維護(hù)的聯(lián)合優(yōu)化模型。Adrian[7]等提出一種基于中期優(yōu)化的方法，用于將生產(chǎn)計(jì)劃、調(diào)度和維護(hù)進(jìn)行集成。然而，目前文獻(xiàn)還未見考慮無緩沖前提下裝配線上設(shè)備預(yù)防維護(hù)與線平衡的集成。

為求解具有強(qiáng)NP-hard屬性的組合優(yōu)化問題，近期出現(xiàn)了很多新穎的智能優(yōu)化算法，如灰狼優(yōu)化算法[8]、鯨魚優(yōu)化算法[9]、蝗蟲優(yōu)化算法[10]等。其中，灰狼優(yōu)化算法通過模擬狼群覓食過程，借助頭狼的導(dǎo)引能力和普通灰狼的自適應(yīng)調(diào)整能力，實(shí)現(xiàn)全局尋優(yōu)，主要優(yōu)點(diǎn)是：①結(jié)構(gòu)簡(jiǎn)單、需要調(diào)節(jié)的參數(shù)少、容易實(shí)現(xiàn)[11]；②存在能夠自適應(yīng)調(diào)整的收斂因子以及信息反饋機(jī)制，能夠在全局搜索與局部尋優(yōu)之間實(shí)現(xiàn)平衡，在問題求解精度和收斂速度方面都有良好的性能[11]。該算法已在無人作戰(zhàn)飛行器路徑規(guī)劃[12]、經(jīng)濟(jì)調(diào)度指派[13]、直流電機(jī)最優(yōu)控制[14]、多輸入輸出電力系統(tǒng)[15]等諸多領(lǐng)域得到成功應(yīng)用。并且，算法雖主要用于求解連續(xù)優(yōu)化問題[11]，但在離散問題中同樣有效[16]。

因此，針對(duì)裝配線平衡與預(yù)防維護(hù)的集成優(yōu)化問題，首先需要面向正常生產(chǎn)和給定工位預(yù)防維護(hù)等多種情形，構(gòu)建可實(shí)現(xiàn)多套裝配線平衡方案且各方案之間調(diào)整代價(jià)小的多目標(biāo)優(yōu)化模型。其次，考慮到裝配線平衡與預(yù)防維護(hù)的集成優(yōu)化問題特點(diǎn)，需要設(shè)計(jì)一種改進(jìn)的多目標(biāo)灰狼算法(Improved Multi-Objective Grey Wolf Optimization algorithms, IMOGWO)，并通過對(duì)比實(shí)驗(yàn)驗(yàn)證算法的合理和有效性，以便經(jīng)濟(jì)、高效地求取較優(yōu)解。

1 問題描述

在裝配線平衡與預(yù)防維護(hù)的集成優(yōu)化時(shí)，需要考慮多種生產(chǎn)情形：①正常工作，即裝配線上每個(gè)工位均能正常生產(chǎn)；②指定工位設(shè)備預(yù)防維護(hù)，即根據(jù)設(shè)備可用性、可靠性等的預(yù)測(cè)，推斷在未來一段時(shí)間內(nèi)需要進(jìn)行預(yù)防維護(hù)的設(shè)備及工位，每一種預(yù)防維護(hù)情形下需要停機(jī)的工位不同。當(dāng)二者集成后，生產(chǎn)過程就變成多種生產(chǎn)情形之間的切換，以便實(shí)現(xiàn)高效生產(chǎn)、滿足設(shè)備維護(hù)要求?？紤]到設(shè)備維護(hù)的頻率，后續(xù)生產(chǎn)調(diào)整主要指在正常工作與預(yù)防維護(hù)情形之間的變動(dòng)，不考慮多種預(yù)防維護(hù)情形之間的變動(dòng)。其中涉及到的符號(hào)及其說明如表1所示。

表1 符號(hào)及其說明

1.1 多目標(biāo)優(yōu)化模型

包含兩類目標(biāo)：

(1)最小化各生產(chǎn)情形下的節(jié)拍，包括正常工作和各種預(yù)防維護(hù)情形。其中，所考慮生產(chǎn)情形的總量即為該類型優(yōu)化目標(biāo)的個(gè)數(shù)。

minCTc?c∈C。

(1)

(2)最小化正常工作與各種預(yù)防維護(hù)情形間的工序調(diào)整數(shù)。工序調(diào)整即將一個(gè)操作從一個(gè)工位調(diào)整到另一個(gè)工位，涉及到對(duì)應(yīng)物料的調(diào)整、操作工技能/工夾具等的調(diào)整，影響生產(chǎn)現(xiàn)場(chǎng)穩(wěn)定性，也會(huì)擾亂生產(chǎn)秩序。優(yōu)化工序調(diào)整數(shù)量，對(duì)于快速實(shí)現(xiàn)生產(chǎn)切換、快速恢復(fù)工作秩序，具有顯著意義。

c∈{2,…,C}。

(2)

1.2 約束

集成考慮裝配線平衡與工位預(yù)防維護(hù)，還需考慮各種情形下的約束，包括工位分配約束、工序分配約束、節(jié)拍約束、優(yōu)先關(guān)系約束等。

(1)工位分配約束 正常工作時(shí)，每個(gè)工位都應(yīng)該被分配工序，且至少完成一個(gè)工序。但當(dāng)進(jìn)行工位維護(hù)時(shí)，需要維護(hù)的工位不被分配工序。

(3)

(4)

(2)工序分配約束 在任何生產(chǎn)情形下，每個(gè)工序都必須分配到工位中，且只能分配一次。

(5)

(3)節(jié)拍約束 正常工位的總操作時(shí)間不能超過節(jié)拍，處于維護(hù)情形下工位的總操作時(shí)間為0。

(6)

(7)

(4)優(yōu)先關(guān)系約束 當(dāng)某道工序的所有前序工序都已經(jīng)分配完畢時(shí)，該工序才能分配。

(8)

式(1)～式(8)綜合反映出平衡與維護(hù)集成優(yōu)化問題，本質(zhì)上是一種帶有多種整數(shù)決策的多目標(biāo)優(yōu)化問題。關(guān)于決策變量數(shù)，有多少種生產(chǎn)情形就需要多少套生產(chǎn)方案；而關(guān)于優(yōu)化目標(biāo)數(shù)，其數(shù)值為生產(chǎn)情形數(shù)加1，即式(2)表示的工序調(diào)整數(shù)。

2 改進(jìn)多目標(biāo)灰狼優(yōu)化算法(IMOGWO)

2.1 基本灰狼算法

灰狼算法最早由Mirjalili等[8]于2014年提出，通過在29個(gè)標(biāo)桿案例中與粒子群算法、引力搜索算法進(jìn)行比較，證明了算法在對(duì)解空間的探索、避免局部最優(yōu)、收斂性等方面都具有明顯優(yōu)勢(shì)?；依撬惴ㄍㄟ^模擬灰狼尋找獵物的行為搜索最優(yōu)解，該過程可表示為：

D=|C×Xp(t)-X(t)|，

(9)

X(t+1)=Xp(t)-A×D。

(10)

其中：Xp表示獵物的位置；X表示任一灰狼的位置；t表示迭代次數(shù)；D表示灰狼與獵物之間的距離。亦即，任一灰狼在下一次迭代時(shí)的位置需根據(jù)獵物位置和相對(duì)距離確定。而A和C的計(jì)算公式如下：

A=2a×r1-a，

(11)

C=2×r2。

(12)

其中：r1、r2為[0,1]之間的隨機(jī)數(shù)；a是一個(gè)線性減小的正數(shù)，初值為2。每次迭代開始時(shí)，用a減去初值與迭代次數(shù)t的商后賦值給a，最后一次迭代時(shí)，a為0。

灰狼社會(huì)有4種狼：α、β、δ和ω，其中，具有最佳目標(biāo)函數(shù)值的灰狼稱為α，具有第二、第三目標(biāo)函數(shù)值的灰狼分別稱為β和δ，其余灰狼稱為ω[16]。普通灰狼ω的捕食行為常常由α個(gè)體進(jìn)行引導(dǎo)，β、δ偶爾也引導(dǎo)狼群捕食。由于不知道最佳的獵物位置，為了從數(shù)學(xué)上模擬灰狼的捕食行為，可假設(shè)α、β、δ對(duì)獵物的潛在位置有更好的理解，再據(jù)此調(diào)整普通灰狼ω的位置。故而，基于式(9)和式(10)，普通灰狼ω的捕食行為可以描述為：

Dα=|C1×Xα-X|，Dβ=|C2×Xβ-X|，

Dδ=|C3×Xδ-X|，

(13)

X1(t+1)=Xα(t)-A1×Dα，

X2(t+1)=Xβ(t)-A2×Dβ,

X3(t+1)=Xδ(t)-A3×Dδ,

(14)

(15)

其中X1、X2、X3分別為在灰狼α、β、δ引導(dǎo)下普通灰狼ω的位置分量。

2.2 基于隨機(jī)鍵的編碼、解碼及目標(biāo)函數(shù)值計(jì)算

平衡與維護(hù)集成優(yōu)化問題主要涉及工序分配Xijc，采用灰狼算法優(yōu)化時(shí)每個(gè)灰狼個(gè)體的編碼也應(yīng)該反映工序分配。由于該集成問題本質(zhì)上是離散優(yōu)化問題，而灰狼算法主要用于解決連續(xù)優(yōu)化問題，故采用隨機(jī)鍵的編碼方式實(shí)現(xiàn)離散問題向連續(xù)問題的轉(zhuǎn)化。限于篇幅，下述案例中僅考慮正常工作情形和一種工位預(yù)防維護(hù)情形。

在編碼過程中，每個(gè)個(gè)體的編碼包含兩部分，共2×I個(gè)要素，前I個(gè)要素代表正常工作情形下的編碼，第I+1～第2×I個(gè)要素代表工位維護(hù)情形下的編碼。每個(gè)要素是介于(0,1)之間的隨機(jī)數(shù)，且每一位置的隨機(jī)數(shù)代表對(duì)應(yīng)工序的權(quán)值。如圖1所示的工序具有11個(gè)操作，每個(gè)工序加工時(shí)間分別為{6,2,5,7,1,2,3,6,5,5,4}，考慮正常工作和一種維護(hù)情形的集成問題，其編碼可表示為：{0.97,0.96,0.49,0.80,0.14,0.42,0.91,0.79,0.96,0.66,0.04|0.85,0.93,0.68,0.76,0.74,0.39,0.66,0.17,0.71,0.03,0.28}。

在上述編碼基礎(chǔ)上，需要進(jìn)行進(jìn)一步的解碼，得到兩種情形下的工序安排，步驟如下：

步驟2對(duì)于每種工作情形，依據(jù)隨機(jī)鍵編碼和工序間優(yōu)先關(guān)系生成該情形下的加工序列。將直接前序已完成的全部工序，放入到待加工工序集中。在該集合中找到編碼值最大的工序，置入到加工序列中；并將新的直接前序已全部完成的工序，增加到待加工工序集中。依次類推，直到所有工序都被加入加工序列。

步驟3針對(duì)正常工作情形，依據(jù)該情形下的加工序列，以CT1為節(jié)拍將裝配操作分配至[1,J-1]工位中；將余下操作全部放入J工位，若能滿足節(jié)拍約束，則轉(zhuǎn)步驟4；否則，CT1=CT1+1，轉(zhuǎn)步驟3，重新對(duì)工序進(jìn)行分配。

步驟4針對(duì)指定工位需要維護(hù)的情形，依據(jù)該情形下的加工序列，以CTc為節(jié)拍將裝配操作分配至除待維護(hù)工位和最后一個(gè)工位之外的其他工位中。若余下操作能全部放入最后一個(gè)不需維護(hù)的工位，且能滿足節(jié)拍約束，則轉(zhuǎn)步驟5；否則，CTc=CTc+1，重新執(zhí)行步驟4。

步驟5分別輸出正常工作和指定工位維護(hù)情形下的工序分配結(jié)果及節(jié)拍CT1和CTc，并計(jì)算工序調(diào)整數(shù)。

根據(jù)前述的隨機(jī)鍵編碼和優(yōu)先關(guān)系圖，生成正常工作情形下的加工序列。如圖1所示，由于工序1沒有緊前工序，將工序1直接放入加工序列；將工序{2,3,4,5}放入待加工工序集中。考慮其編碼值分別為(0.96,0.49,0.80,0.14)且工序2數(shù)值最大，選擇工序2進(jìn)入加工序列。依次類推，可得到正常工作與預(yù)防維護(hù)情形下的工序分配序列各為{1,2,4,3,6,8,10,5,7,9,11}和{1,2,4,5,3,7,9,6,8,10,11}。在正常工作情形下，當(dāng)CT1=13時(shí)，4個(gè)工位的工序分配順次為：{{1,2},{4,3},{6,8,10},{5,7,9,11}}。預(yù)知工位3需要維護(hù)，且當(dāng)CTc=16時(shí)，其余3個(gè)工位的工序分配順次為：{{1,2,4,5},{3,7,9,6},{},{8,10,11}}。

在解碼時(shí)已經(jīng)獲得不同生產(chǎn)情形下的節(jié)拍，還需計(jì)算工序調(diào)整數(shù)?？偣ば蛘{(diào)整數(shù)PC定義為各預(yù)防維護(hù)情形與正常生產(chǎn)情形之間各工序所在工位差的絕對(duì)值之和。如圖1所示，工序4在兩種情形下分別被分配至工位2、工位1，故工位差絕對(duì)值為1。通過計(jì)算得到了每只灰狼對(duì)應(yīng)的多個(gè)目標(biāo)函數(shù)值，基于此還需對(duì)多個(gè)灰狼個(gè)體進(jìn)行評(píng)價(jià)，選擇優(yōu)秀個(gè)體引導(dǎo)進(jìn)化。

2.3 狼群等級(jí)劃分與引導(dǎo)狼確定

原始灰狼算法讓目標(biāo)函數(shù)值最佳的灰狼α、β、δ引導(dǎo)其他灰狼進(jìn)行捕食，從而實(shí)現(xiàn)位置更新。但在多目標(biāo)問題中，僅在一個(gè)目標(biāo)上進(jìn)行比較，無法得到最優(yōu)解，也無法選出α、β、δ。在以往的研究中，Mirjalili[17]等改進(jìn)灰狼算法，實(shí)現(xiàn)灰狼算法求解多目標(biāo)問題。為了更好地優(yōu)化多目標(biāo)問題，提出基于Pareto層級(jí)的狼群等級(jí)劃分方法，并引進(jìn)式(16)所示的擁擠距離[18]，以計(jì)算同層灰狼個(gè)體之間的緊密程度：

(16)

狼群等級(jí)劃分方法如下：按Pareto層次構(gòu)造方法對(duì)狼群個(gè)體進(jìn)行分層，選出非支配灰狼個(gè)體作為第一層，然后在剩下的灰狼個(gè)體中選出非支配個(gè)體作為第二層。以此類推，直到所有灰狼都被分層。然后按照式(16)計(jì)算每層灰狼個(gè)體間的擁擠距離。

在確定引導(dǎo)狼α、β、δ時(shí)，可分為以下4種狀況：①若第一和二層灰狼個(gè)體數(shù)都為1，將第一層灰狼個(gè)體定為α，第二層灰狼個(gè)體定為β，然后在第三層中選擇擁擠距離最大的個(gè)體作為δ；②若第一層灰狼個(gè)體數(shù)為1，第二層灰狼個(gè)體數(shù)大于1，將第一層灰狼個(gè)體定為α，然后選擇第二層中擁擠距離最大的兩個(gè)個(gè)體作為β、δ；③若第一層灰狼個(gè)體數(shù)為2，則將它們分別定為α、β，然后在第二層個(gè)體中選擇擁擠距離最大的個(gè)體作為δ；④若第一層灰狼個(gè)體數(shù)大于等于3，選擇擁擠距離最大的3個(gè)個(gè)體分別作為α、β、δ。

原始灰狼算法中，在確定灰狼α、β、δ后，通過式(13)～式(15)對(duì)種群中其他灰狼的位置進(jìn)行更新?？紤]到上述集成問題存在正常生產(chǎn)和一種預(yù)防維護(hù)兩種情形，需將上述編碼分為兩段，分別按照式(13)～式(15)對(duì)每段進(jìn)行更新，實(shí)現(xiàn)灰狼ω位置的更新。

2.4 交叉算子與種群更新機(jī)制

原始灰狼算法中灰狼間沒有信息交流。為了有效提升狼群的進(jìn)化效率，提高算法的全局搜索能力，在算法中加入雙點(diǎn)交叉算子。對(duì)于狼群中任意的灰狼個(gè)體，當(dāng)交叉概率CR大于隨機(jī)數(shù)時(shí)，從狼群中隨機(jī)選取一只灰狼個(gè)體與當(dāng)前灰狼個(gè)體進(jìn)行交叉，具體交叉方法如圖2所示。

每次迭代最后將本次迭代中通過位置更新和雙點(diǎn)交叉產(chǎn)生的新個(gè)體與原種群中的個(gè)體進(jìn)行結(jié)合，計(jì)算所有個(gè)體的目標(biāo)函數(shù)值，并重新構(gòu)建Pareto層級(jí)。依據(jù)每一只灰狼所處的層級(jí)和擁擠距離，從集合中選擇出新的種群加入下一次迭代。選擇的過程按照下列步驟進(jìn)行：

步驟1對(duì)母代種群和子代種群進(jìn)行Pareto分層。

高職院校相對(duì)比較封閉，創(chuàng)新創(chuàng)業(yè)項(xiàng)目的開展應(yīng)該在開放的環(huán)境中進(jìn)行。創(chuàng)新團(tuán)隊(duì)外出交流，不僅可以學(xué)習(xí)到新的理念、技術(shù)，更可以認(rèn)識(shí)技術(shù)同行，為自身項(xiàng)目完善、發(fā)展提供更多機(jī)會(huì)。外出參加的活動(dòng)主題可以與創(chuàng)新團(tuán)隊(duì)的研究目標(biāo)有關(guān)，也可以與學(xué)生專業(yè)相關(guān)，既可以是創(chuàng)新創(chuàng)業(yè)類活動(dòng)，又可以是創(chuàng)新創(chuàng)業(yè)專項(xiàng)訓(xùn)練。既可以走出去，又可以引進(jìn)來。創(chuàng)客空間可以利用自身場(chǎng)，舉辦講座、沙龍等活動(dòng)。

步驟2創(chuàng)建新種群Ф，Pareto當(dāng)前層數(shù)k=1。

步驟3若第k層個(gè)體數(shù)Nk+|Ф|小于設(shè)定種群規(guī)模PS時(shí)，將第k層所有個(gè)體加入新種群Ф中，轉(zhuǎn)步驟4；反之，對(duì)當(dāng)前層按照擁擠距離從大到小進(jìn)行排序，選擇(PS-|Ф|)個(gè)個(gè)體進(jìn)入新種群，轉(zhuǎn)步驟5。

步驟4k=k+1,轉(zhuǎn)步驟3。

步驟5新種群Ф作為母代種群進(jìn)行下一次迭代。

2.5 改進(jìn)灰狼算法流程

按前文所述，改進(jìn)后多目標(biāo)灰狼算法流程偽代碼如下，其中POS表示Pareto最優(yōu)前沿，random_number表示隨機(jī)數(shù)。

算法1改進(jìn)多目標(biāo)灰狼算法(IMOGWO)。

輸入裝配線平衡問題數(shù)據(jù)。

開始：

基于隨機(jī)鍵的編碼和解碼，初始化狼群；

構(gòu)建 POS；

For k=1 to t do

基于Pareto層級(jí)進(jìn)行狼群等級(jí)劃分，確認(rèn)α、β、δ；

For m=1 to PS do

采用進(jìn)化機(jī)制(式(13)～式(15))更新灰狼ωm；

If random_number

對(duì)ωm進(jìn)行雙點(diǎn)交叉；

End If

End For

更新POS；

采用種群更新機(jī)制，形成新的灰狼種群；

End for

輸出POS

3 實(shí)驗(yàn)分析與討論

為驗(yàn)證算法性能，將改進(jìn)后算法與帶精英策略的快速非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ, NSGA-Ⅱ)[18]、多目標(biāo)粒子群優(yōu)化算法(Multi-Objective Particle Swarm Optimization algorithm, MOPSO)[19]、多目標(biāo)人工蜂群算法(Multi-Objective Artificial Bee Colony algorithm, MOABC)[20]進(jìn)行對(duì)比，為保證對(duì)比的公平性，對(duì)所有對(duì)比算法都進(jìn)行重新編碼和調(diào)整，并在相同配置電腦上運(yùn)行，采用MATLAB 2016a進(jìn)行編程，電腦配置為：Intel Core i5 CPU，2.40 GHz and 4.00 GB RAM。裝配線實(shí)驗(yàn)數(shù)據(jù)來自裝配線平衡專業(yè)網(wǎng)站https://assembly-line-balancing.de/；維護(hù)工位采用隨機(jī)方式生成，每個(gè)案例隨機(jī)指定一個(gè)或多個(gè)需要維護(hù)的工位。

3.1 案例描述

圖3所示分別展示了正常工作情形下與工位(2,3,5)同時(shí)預(yù)防維護(hù)情形下的最佳工序安排，所選案例為標(biāo)桿案例中148工序-10工位的案例。

圖3中方塊上的數(shù)字代表工序序號(hào)，灰色方塊表示需進(jìn)行調(diào)整的工序，白色方塊表示不需進(jìn)行調(diào)整的工序。在圖3a中10個(gè)工位均正常工作，最優(yōu)生產(chǎn)節(jié)拍很小，為429分；但由于工位(2,3,5)3個(gè)工位需要同時(shí)進(jìn)行維護(hù)，生產(chǎn)節(jié)拍變動(dòng)很大，增長(zhǎng)到620分，且生產(chǎn)調(diào)整數(shù)很大，需要調(diào)整110個(gè)工序，包含圖3中灰色所示的{1,2,3,…,147,148}工序。

與未集成相比，將裝配線平衡與預(yù)防維護(hù)集成后具有明顯優(yōu)勢(shì)。以一天為例，假設(shè)每個(gè)工位每天工作8 h，工位維護(hù)需要4 h，工序調(diào)整時(shí)間需10 min。在不考慮集成時(shí)，只要設(shè)備預(yù)防維護(hù)則整線停工，導(dǎo)致總工作時(shí)間變成4 h，按照每小時(shí)產(chǎn)值200萬計(jì)算，直接損失800萬。在考慮集成時(shí)，設(shè)備維護(hù)與工序調(diào)整并行，待工序調(diào)整后繼續(xù)工作。并在設(shè)備維護(hù)結(jié)束前10 min恢復(fù)正常工序分配。總工作時(shí)間為7.67 h。比未集成時(shí)增加192%。按調(diào)整工序后每小時(shí)產(chǎn)值140萬計(jì)算，直接損失將降至287萬，比未集成時(shí)減少517萬。

3.2 多目標(biāo)Pareto前沿評(píng)價(jià)指標(biāo)與參數(shù)校驗(yàn)

為評(píng)價(jià)改進(jìn)算法的性能，采用非支配解率RP、Pareto前沿解收斂性CP、個(gè)體間距離指標(biāo)SP三個(gè)指標(biāo)[21]評(píng)價(jià)解集的優(yōu)劣性。

(1)非支配解率RP對(duì)于每一個(gè)Pareto解集Si(i=1,2,3…,s,S=S1+S2+…+Si+…+Ss)，解集Si中不被其他解集支配的解所占的比重稱為非支配解率，RP值越高，解集Si性能越好。

(17)

式中：y?x表示y支配x;|Si|表示解集Si的數(shù)量。

(2)Pareto前沿解收斂性CP表示Pareto解集Si與近似true-Pareto解集TP的不同。

(18)

(19)

(3)個(gè)體間距度量指標(biāo)SP衡量Pareto集合的分布性。

(20)

(21)

算法對(duì)比前，使用Minitab軟件中的田口實(shí)驗(yàn)對(duì)IMOGWO算法進(jìn)行參數(shù)校驗(yàn)。首先通過田口實(shí)驗(yàn)產(chǎn)生9組參數(shù)值(如表2)。將每一組參數(shù)帶入算法進(jìn)行計(jì)算，得到當(dāng)前參數(shù)對(duì)應(yīng)的計(jì)算結(jié)果。然后將所有參數(shù)對(duì)應(yīng)的結(jié)果合在一起，計(jì)算出總結(jié)果中的Pareto前沿，然后計(jì)算每組結(jié)果中Pareto前沿解所占比重，即非支配解率RP。最終得到結(jié)果如表2所示。對(duì)每組的RP值進(jìn)行分析，得到信噪比主效應(yīng)圖(如圖4)。

表2 IMOGWO參數(shù)校驗(yàn)

由圖4可以得出IMOGWO的最佳參數(shù)組合為：種群大小90，交叉概率0.7，迭代次數(shù)100。為保證實(shí)驗(yàn)的公正性，考慮本問題特殊性對(duì)各對(duì)比算法做出如下改動(dòng)。其中NSGA-Ⅱ采用相同編碼解碼方案，采用單點(diǎn)交叉、保留原始算法更新機(jī)制，交叉變異后分別計(jì)算適應(yīng)度值并更新非支配解集；多目標(biāo)粒子群算法(MOPSO)采用相同編碼解碼方案，保留原始算法更新機(jī)制；多目標(biāo)人工蜂群算法(MOABC)采用相同編碼解碼方案，雇傭蜂、觀察蜂、偵查蜂每個(gè)階段結(jié)束時(shí)更新外部檔案。對(duì)上述對(duì)比算法同樣進(jìn)行參數(shù)檢驗(yàn)，得到各算法最優(yōu)參數(shù)組合如表3所示。

表3 各算法參數(shù)組合

續(xù)表3

3.3 算法性能分析

表4分別展示了4種算法在31個(gè)案例中的計(jì)算結(jié)果。每個(gè)算法下的3列數(shù)據(jù)分別對(duì)應(yīng)當(dāng)前算法在每個(gè)案例中計(jì)算出的3個(gè)指標(biāo)值：RP、CP、SP。其中，加下劃線表示性能較好的算法案例。

表4 多目標(biāo)優(yōu)化算法性能

續(xù)表4

分析表5可知，IMOGWO的RP值基本為1，表明該算法在每一個(gè)案例中得到的Pareto前沿解能支配NSGA-Ⅱ、MOABC、MOPSO等算法得到的Pareto前沿解集；此外IMOGWO計(jì)算得到的CP值均較小，說明該算法的收斂性優(yōu)于其他3個(gè)算法；IMOGWO的SP值在20個(gè)案例中大于其他算法，說明IMOGWO在多數(shù)案例中具有較好的分布性。

綜上表明，相對(duì)于NSGA-Ⅱ、MOABC、MOPSO算法，IMOGWO能高效地搜索到更多更優(yōu)的解，對(duì)于解決裝配線平衡與工位預(yù)防維護(hù)的集成問題具有明顯的優(yōu)勢(shì)。進(jìn)一步分析主要得益于算法在幾個(gè)方面的改進(jìn):①相比于對(duì)比算法，灰狼算法通過讓3只適應(yīng)度值最優(yōu)的頭狼引導(dǎo)種群進(jìn)化，加快了種群的進(jìn)化速度，促成了灰狼算法所得的前沿解對(duì)其他算法前沿解的支配性;②引入遺傳算法中的交叉算子，提高了種群內(nèi)部的交流，讓算法在每個(gè)案例中皆具有較好的分布性;③獨(dú)特的種群更新機(jī)制，即將新生成個(gè)體與原種群個(gè)體合在一起計(jì)算適應(yīng)度值，選擇其中優(yōu)秀的個(gè)體進(jìn)入下一代，充分保留了種群中的優(yōu)秀基因，防止算法在迭代過程中丟失種群更新的方向。

4 結(jié)束語

針對(duì)目前裝配線上不論設(shè)備預(yù)防維護(hù)或故障維護(hù)，都必須生產(chǎn)中斷，帶來巨大生產(chǎn)損失的問題，提出將裝配線平衡與工位預(yù)防維護(hù)兩個(gè)獨(dú)立子系統(tǒng)進(jìn)行集成，同時(shí)制定多套、能容留設(shè)備維護(hù)契機(jī)的裝配生產(chǎn)計(jì)劃，通過多套計(jì)劃之間的快速切換，保證生產(chǎn)時(shí)的設(shè)備可維護(hù)性和維護(hù)時(shí)的生產(chǎn)連續(xù)性。針對(duì)該集成問題，構(gòu)建數(shù)學(xué)規(guī)劃模型，指明不僅應(yīng)達(dá)成各工位在正常工作和工位維護(hù)情形下的節(jié)拍最小化，以保證生產(chǎn)效率，還應(yīng)對(duì)正常工作與預(yù)防維護(hù)情形之間切換時(shí)的工序調(diào)整最小化，以穩(wěn)定生產(chǎn)。設(shè)計(jì)基于隨機(jī)鍵的編碼和解碼方法，并提出融合Pareto層級(jí)構(gòu)造和擁擠距離的多目標(biāo)進(jìn)化機(jī)制，研制IMOGWO算法進(jìn)行求解。實(shí)驗(yàn)表明，所提出的IMOGWO算法在非支配率、收斂性和分布性指標(biāo)上，優(yōu)于其他算法，同時(shí)證明了采用集成方法后裝配生產(chǎn)損失大幅減小，生產(chǎn)連續(xù)性顯著提升。未來的研究將考慮一些更加復(fù)雜的生產(chǎn)情形，如多種產(chǎn)品在同一條裝配線上進(jìn)行加工等。