基于改進(jìn)水波算法的復(fù)雜多人共站裝配線平衡研究

張 梅,傅艷霞,朱金輝,鄧率航

(1.華南理工大學(xué) 自動化科學(xué)與工程學(xué)院,廣東 廣州 510641;2.華南理工大學(xué) 軟件學(xué)院,廣東 廣州 510006;3.華南理工大學(xué) 大數(shù)據(jù)與智能機(jī)器人教育部重點實驗室,廣東 廣州 510006)

1 問題的描述

裝配線平衡問題是在滿足裝配任務(wù)約束的條件下,將所有作業(yè)任務(wù)(工序)分配到各個工作站上,同時在保證整條裝配線連續(xù)生產(chǎn)的情況下,盡可能使每個工作站在節(jié)拍時間內(nèi)的生產(chǎn)效率達(dá)到最大[1]。當(dāng)前裝配線平衡問題的研究主要集中在簡單裝配線[2-4],其特點是單個工作站只能容納一個工人,且只能對單一類型的產(chǎn)品進(jìn)行大批量流水裝配作業(yè),難以降低裝配線的生產(chǎn)周期[5]。在實際裝配過程中,由于產(chǎn)品體積過大或裝配復(fù)雜度較高,形成了單個工作站在同一時間段內(nèi)需要多個工人并行加工多道工序的多人共站裝配線,其實現(xiàn)了裝配線線長與生產(chǎn)周期更短、柔性更高,提高了裝配線的空間利用率,如圖1所示。類似于簡單裝配線平衡問題(Simple Assembly Line Balance Problem,SALBP),多人共站的裝配線平衡問題(Multi-manned Assembly Line Balance Problem,MALBP)根據(jù)已知條件、優(yōu)化目標(biāo)的不同,可大致分為4類:第Ⅰ類多人共站裝配線平衡問題(MALBP-Ⅰ)為給定生產(chǎn)節(jié)拍,最小化工作站數(shù)目;第Ⅱ類多人共站裝配線平衡問題(MALBP-Ⅱ)為給定工作站數(shù)目,最小化生產(chǎn)節(jié)拍;第SI類多人共站裝配線平衡問題(MALBP-SI)為給定生產(chǎn)節(jié)拍和工作站數(shù)目,最小化平滑指數(shù);第E類多人共站裝配線平衡問題(MALBP-E)為給定生產(chǎn)節(jié)拍或工作站數(shù)目,最大化裝配線的線效率。相比于SALBP,MALBP研究較少,但在近幾年來逐漸引起了人們的關(guān)注。DIMITRIADIS[5]最先提出了MALBP的概念,采用啟發(fā)式算法對該問題進(jìn)行求解。FATTAHI等[6]根據(jù)多人共站裝配線的特點建立了MALBP的數(shù)學(xué)模型,并提出一種改進(jìn)的蟻群算法用于解決該類問題。錢雄文[7]提出一種第II類多人共站裝配線平衡問題,在給定工作站數(shù)量的前提下,最小化節(jié)拍時間。FANG等[8]針對飛機(jī)總裝線中具有多階段工作站的靈活工人分配問題,建立了以工作站節(jié)拍時間最小化、工作站和工人負(fù)載均衡為目標(biāo)的整數(shù)規(guī)劃模型,并提出一種改進(jìn)的非主導(dǎo)排序遺傳算法(NSGA-Ⅳ)求解了該問題的實例。還有一些文獻(xiàn)在研究多人共站裝配線平衡問題的基礎(chǔ)上,考慮了工人負(fù)載均衡[9]、復(fù)雜約束[10-11]、生產(chǎn)成本最小化[12]以及柔性工作站[13]等因素。

圖1 多人共站裝配線示意圖

上述文獻(xiàn)涉及的多人共站裝配線平衡問題一般都是考慮每道工序所需的工人數(shù)量相同的情況,而在實際生產(chǎn)中,不同工序裝配的復(fù)雜程度不同,所需的工人數(shù)量也不同,對于復(fù)雜的工序,如大型設(shè)備的裝配工序,需要分配較多數(shù)量的工人以工作組的形式共同協(xié)作完成;而對于簡單的工序,則分配較少數(shù)量的工人完成。因此,對于這類問題,還需要考慮工作站內(nèi)工作組間的工人調(diào)度,從而在裝配線生產(chǎn)能力不變的前提下,盡可能地保持裝配線平衡,優(yōu)化裝配線的生產(chǎn)成本。針對這類問題,本文提出一種復(fù)雜多人共站裝配線,如圖2所示,裝配線上的工序沿著箭頭方向順序裝配,不同顏色表示不同類型的工人,每道工序由一個或多個工人協(xié)同裝配,需要根據(jù)工序的復(fù)雜程度,將工人以成組形式指派到各個工作站上,在每個工作站內(nèi),實線框內(nèi)的工序為已裝配的工序,虛線框內(nèi)的工序為待裝配工序,工作站內(nèi)待裝配工序所需的工人組根據(jù)以下原則進(jìn)行指派:①待裝配工序與已裝配工序所需工人類型和工人數(shù)量一致,則工作組不需拆分,將其直接指派給待裝配工序,如工作站1所示,將已裝配工序1和工序2的工人直接重組并指派給待裝配工序3;②待裝配工序與已裝配工序所需工人類型一致,而所需工人組的人數(shù)多于已裝配工序,則需由工作組外工人(優(yōu)先考慮工作站內(nèi)其他被拆分工作組的工人,如不滿足人數(shù)要求再從工人池中新增工人)補(bǔ)充進(jìn)工作組,再指派給待裝配工序,如工作站2所示,將工序4的工人與從工人池中新增的工人重新組合并指派給待裝配工序6;③待裝配工序與已裝配工序所需工人類型一致,而所需工人組的人數(shù)少于已裝配工序的工人數(shù),則可將已完成裝配的工人組拆成多組進(jìn)行指派或在當(dāng)前工作站中等待指派給后續(xù)待裝配工序,如工作站3所示,將已裝配工序7的工人組拆分為兩組,其中一組1人指派給待裝配工序9,另一組2人在工作站中等待指派;④待裝配工序與已裝配工序所需工人類型不一致時,則需按照待裝配工序所需的工人數(shù)量和類型,從工人池中新增工人組,再指派給待裝配工序,如工作站4所示,從工人池中新增一個工人組并指派給待裝配工序12。

圖2 復(fù)雜多人共站裝配線示意圖

水波優(yōu)化(Water Wave Optimization,WWO)[14]算法是一種求解連續(xù)優(yōu)化問題的新型智能優(yōu)化算法,受淺水波模型的啟發(fā),WWO算法利用傳播、碎浪、折射操作實現(xiàn)了解空間中的有效搜索,具有可調(diào)參數(shù)少、操作簡單、易于實現(xiàn)等優(yōu)點。近年,有研究者對該算法進(jìn)行改進(jìn),用于解決實際車間調(diào)度[15]和車輛路徑[16]等離散問題。王文艷等[15]利用塊最優(yōu)插入、交叉操作、多鄰域搜索策略分別對基本水波優(yōu)化算法的算子進(jìn)行了改進(jìn),加入替換差解操作以協(xié)調(diào)水波優(yōu)化算法的局部和全局搜索的能力,提高了算法的收斂速度,并與其他4種算法進(jìn)行了對比,驗證了離散水波優(yōu)化算法在車間調(diào)度問題上的求解性能。張春苗等[16]針對車輛路徑問題生成一個初始概率矩陣,基于該初始概率矩陣完成了初始化、傳播、折射、碎浪操作,同時引入insert-opt與cross-opt等算子進(jìn)行局部優(yōu)化,最后通過標(biāo)準(zhǔn)測試用例實驗驗證了算法的性能。

綜上,本文提出一種復(fù)雜多人共站裝配線平衡問題(Complex Multi-manned Assembly Line Balancing Problem,CMALBP),考慮了實際生產(chǎn)中需要根據(jù)裝配工序的復(fù)雜程度指派不同規(guī)模和類型的工人組協(xié)同裝配工序的情況。此外,由于CMALBP相對于MALBP具有更加復(fù)雜的約束和任務(wù)分配限制,屬于NP-hard問題,而精確算法難以求解大規(guī)模問題[17-18],因此,本文提出一種改進(jìn)的離散水波優(yōu)化(Discrete Water Wave Optimization,DWWO)算法,采用了基于拓?fù)渑判虻木幋a方案和啟發(fā)式解碼方案,并分別對傳播、碎浪、折射算子進(jìn)行了離散化改造,同時引入擾動個體和路徑重連的搜索策略,提高種群的多樣性,最后設(shè)計實驗驗證了DWWO算法求解CMALBP的有效性,并與其他算法進(jìn)行了對比,進(jìn)一步驗證了DWWO算法的優(yōu)良性能,同時基于實際動車裝配線的生產(chǎn)數(shù)據(jù)給出了一個實例,從而驗證所建模型的有效性。

2 問題分析與模型建立

2.1 問題分析

復(fù)雜多人共站裝配線平衡問題(CMALBP)是一個復(fù)雜的組合優(yōu)化問題,在MALBP的基礎(chǔ)上,本文所研究的CMALBP考慮了以下兩種特殊情況:

(1)多人協(xié)同裝配一道工序 在裝配過程中,由于某些工序所需的零部件體積過大或工序的裝配復(fù)雜度過高,無法由一個工人獨立完成,在為工序指派工人之前,需要考慮工序的復(fù)雜程度,在裝配過程中指派工序所需類型和數(shù)量的工人,從而協(xié)作完成一道工序的裝配,同時,已指派的工人組只能在工作站內(nèi)調(diào)度,不在工作站之間流動。

(2)工人能力約束 工人類型由工人的技能來確定,裝配某道工序的工人必須與該工序所需的工人類型相匹配,即每一類工人只能完成與其技能相匹配的工序的裝配任務(wù),同時假設(shè)掌握同一種技能的工人之間無能力差異,且每一道工序都只需要某一種類型的工人完成裝配。

解決CMALBP的關(guān)鍵在于尋求一種最優(yōu)的裝配線平衡方案,在滿足工序之間優(yōu)先關(guān)系約束的前提下,合理地將工序分配到工作站上,使得每個工作站上的工序都能夠在節(jié)拍時間內(nèi)完成,同時,為每道工序指派一組合適的工人,在不超過每個工作站所能容納的最大工人數(shù)量的前提下,使工人的工時利用率達(dá)到最大,從而減小裝配線上的總工人數(shù)量與工人的空閑時間,進(jìn)一步提高裝配線的線效率,降低平滑指數(shù)。

2.2 數(shù)學(xué)建模

針對CMALBP問題的研究目的,本文在滿足問題約束的前提下,建立以最小化工作站數(shù)量和工人數(shù)量為綜合優(yōu)化目標(biāo)的數(shù)學(xué)模型,模型中涉及的符號定義如表1所示。

表1 符號含義

問題的模型如下:

(1)

(2)

?i,k∈N,i≠k,(i,k)∈G;

(3)

ci+tk≤ck+B(1-oik),

?i,k∈N,i≠k;

(4)

ti≤ci≤CT,?i∈N;

(5)

(6)

?(i,k)∈N,i≠k,?l∈P;

(7)

?(i,k)∈N,i≠k,?l∈P;

(8)

(9)

eiyil=ekykl,?i,k∈N,?l∈P;

(10)

?i,k∈N,i≠k,?l∈P;

(11)

oik+oki≥yil+ykl-1,

?i,k∈N,i≠k,?l∈P;

(12)

oik+oki≤1,?i,k∈N,i≠k;

(13)

qijl≥xij+yil-1,

?i∈N,?j∈St,?l∈P;

(14)

?i∈N,?j∈St,?l∈P;

(15)

(16)

zlj≥xij+yil-1,

?i∈N,?j∈St,?l∈P。

(17)

式(1)中目標(biāo)函數(shù)的第一項為最小化工作站數(shù)量,第二項為最小化工人數(shù)量,通過加權(quán)系數(shù)w1和w2將多目標(biāo)問題轉(zhuǎn)化為以最小化綜合成本C為目標(biāo)函數(shù)的單目標(biāo)問題來求解?？紤]到在實際裝配線的生產(chǎn)過程中,增加一個工作站的成本遠(yuǎn)比增加一個工人的成本要大,因此,在建立目標(biāo)函數(shù)時,需要更多地考慮工作站成本對目標(biāo)函數(shù)的影響?；谝陨戏治?本文在求解CMALBP時,取工作站成本的權(quán)重系數(shù)w1=0.8,工人成本的權(quán)重系數(shù)w2=0.2。式(2)為任務(wù)分配約束,表示任意一道工序必須且只能分配到一個工作站上。式(3)和式(4)為工序的裝配順序約束和工人的流動約束,其中?i,j∈N,i≠k,(i,k)∈G表示工序i和工序k為任意兩道不同的工序,且工序i必須在工序k之前完成裝配;當(dāng)工序i和工序k分配給同一個工作站上的同一個工人時,xij=1,xkj=1,oik=1,此時式(3)和式(4)均等價于ci≤ck-tk,即工序k的開始時刻不能早于其前序工序i的結(jié)束時刻;當(dāng)工序i和工序k分配給同一個工作站上的不同工人時,xij=1,xkj=1,oik=0,此時式(4)恒成立,式(3)等價于ci≤ck-tk;當(dāng)工序i和工序k分配給不同的工作站時,工人不在工作站之間流動,oik=0,此時式(4)恒成立,僅當(dāng)工序i的工作站索引小于工序k的工作站索引時,式(3)成立,即優(yōu)先分配工序k的前序工序i。式(5)為節(jié)拍約束,表示工序i的結(jié)束時刻既不能早于工序的裝配時間,也不能超過節(jié)拍時間。式(6)為多人協(xié)同裝配的約束,表示工序i需要pi個工人同時裝配。式(7)和式(8)為工序指派約束,表示所有指派給同一個工人的工序必須分配到同一個工作站上。式(9)為工人數(shù)量約束,表示一個工作站上的工人數(shù)量不能超過Pmax。式(10)為工人能力約束,表示分配給同一個工人的工序所需的工人類別必須相同。由于模型中涉及的決策變量較多,且決策變量之間存在一定的相關(guān)性,因此式(11)～式(17)對決策變量oik、qijl、zlj進(jìn)行了邏輯上的一致性約束。其中式(11)～式(13)約束了oik的取值:當(dāng)工序i和工序k分配給同一個工人時,yil=1,ykl=1,此時若工序i在工序k之前裝配,則oik=1,oki=0;否則oki=1,oik=0;當(dāng)工序i和工序k分配給不同工人時,oik=0且oki=0。式(14)～式(17)約束了qijl、zlj的取值:當(dāng)工序i分配給工人l,且工序i分配給工作站j時,yil=1,xij=1,此時qijl=1且zlj=1;否則qijl=0且zlj=0。

3 改進(jìn)的離散水波優(yōu)化算法

多人共站裝配線平衡問題(MALBP)是一個組合優(yōu)化問題,具有離散性、多約束性、多目標(biāo)性以及求解復(fù)雜等特點,常采用遺傳算法、模擬退火算法、蟻群算法等啟發(fā)式算法來求解。采用元啟發(fā)式算法雖然能夠獲得較好的求解效果,但存在建模效率低、鄰域結(jié)構(gòu)設(shè)計復(fù)雜、收斂精度不高等問題。而水波優(yōu)化算法是近些年提出的智能進(jìn)化算法,具有算法框架簡單、容易實現(xiàn)、搜索能力強(qiáng)等優(yōu)點,且適用于求解實際生產(chǎn)調(diào)度中的大規(guī)模問題[15],因此,本文考慮采用改進(jìn)的水波優(yōu)化算法以解決CMALBP。

3.1 基本水波優(yōu)化算法

水波算法是由ZHENG[14]提出的一種智能進(jìn)化算法,主要針對連續(xù)優(yōu)化問題進(jìn)行求解,具有搜索能力強(qiáng)、流程簡單且易于實現(xiàn)的優(yōu)點。水波算法從淺水波模型獲得靈感,將海床模擬為解空間,將海床上的水波模擬為一個解,海床深度反比于該解的適應(yīng)度值。在初始化時,需要將每個個體(解)的高度設(shè)置為Hmax,波長設(shè)置為λ0。在尋優(yōu)過程中,種群中的個體依次進(jìn)行傳播、折射和碎浪3種算子操作。

3.1.1 算法流程圖

基本水波優(yōu)化算法的流程圖如圖3所示。

圖3 基本水波優(yōu)化算法流程圖

3.1.2 傳播算子

傳播算子通過對個體的每一維進(jìn)行搜索,得到一個新的解,傳播算子如式(18)所示。

x′(d)=x(d)+rand(-1,1)λL(d)。

(18)

其中:rand(-1,1)表示區(qū)間(-1,1)內(nèi)的隨機(jī)數(shù),L(d)為解空間第d維的長度。在每一次迭代過程中,個體的波長λ按照式(19)迭代。

(19)

其中:α為衰減系數(shù),通常取大于1的常數(shù);f(x)為當(dāng)前解的適應(yīng)度值;fmax、fmin為當(dāng)前所有個體適應(yīng)度值的最大值和最小值,ε為一個接近0的正數(shù)。

3.1.3 碎浪算子

碎浪算子是對個體的某一維進(jìn)行如式(20)所示的搜索。

x′(d)=x(d)+N(0,1)βL(d)。

(20)

其中:N(0,1)是滿足均值為0,標(biāo)準(zhǔn)差為1的高斯分布的隨機(jī)數(shù);β為碎浪系數(shù),β∈[0.01,0.2]。

碎浪過程中,隨機(jī)選擇個體x的k個維度,使用式(20)產(chǎn)生k個子代個體,若k個子代個體中有較個體x更優(yōu)的個體,則從中選擇最優(yōu)的個體替換x,否則保留個體x。

3.1.4 折射算子

當(dāng)個體的高度為0時,對個體進(jìn)行折射算子操作,折射算子如下:

(21)

3.2 改進(jìn)的離散水波優(yōu)化算法

基本水波優(yōu)化(WWO)算法主要由算法框架和算子操作組成,適用于求解連續(xù)函數(shù)優(yōu)化問題,而復(fù)雜多人共站裝配線平衡問題(CMALBP)是一個離散的組合優(yōu)化問題,且約束條件較為復(fù)雜,因此,本文提出一種改進(jìn)的離散水波優(yōu)化(DWWO)算法,算法的流程與基本水波優(yōu)化算法相同,但在算法性能方面做出了如下改善:

(1)對于CMALBP中的復(fù)雜約束,設(shè)計了基于拓?fù)渑判虻木幋a方案和一種啟發(fā)式的解碼方案;

(2)針對CMALBP的離散化特點,以基本水波優(yōu)化算法的框架為基礎(chǔ),對3種算子進(jìn)行離散化改造;

(3)在傳播操作中,采用自適應(yīng)的片段長度控制算子的搜索范圍,增強(qiáng)算法的全局搜索性能;

(4)在折射操作中,引入擾動個體和路徑重連的搜索策略,增加種群的多樣性,使得算法在后期收斂時能夠跳出局部最優(yōu)。

3.2.1 基于拓?fù)渑判虻木幋a方案

本文基于圖論中有向無環(huán)圖的拓?fù)渑判蛩枷?采用考慮工序優(yōu)先關(guān)系約束的編碼方案,編碼形式如圖4所示,編碼以工序為基本單位,個體中的每一位代表工序的編號,每道工序在個體中的位置必須在其所有緊前工序之后,采用該編碼方案進(jìn)行個體初始化的基本步驟為:

圖4 工序優(yōu)先關(guān)系圖

步驟1在工序優(yōu)先關(guān)系圖中選擇一個入度為0的工序節(jié)點i加入個體,其中入度為0的節(jié)點是指沒有前驅(qū)節(jié)點的節(jié)點;

步驟2在工序優(yōu)先關(guān)系圖中刪除工序節(jié)點i和所有以i為起點的邊;

步驟3若工序優(yōu)先關(guān)系圖上所有的節(jié)點都被刪除,則輸出個體;否則轉(zhuǎn)步驟1。

以如圖4所示的工序優(yōu)先關(guān)系圖為例,采用上述基于拓?fù)渑判虻木幋a方案,得到一種可能的個體編碼序列,如圖5所示。

圖5 可能的個體編碼序列之一

3.2.2 啟發(fā)式解碼方案

解碼是將個體編碼序列轉(zhuǎn)化為CMALBP平衡方案的過程,即將所有工序合理地分配到工作站上以及為所有工序指派合適的工人組。本文提出一種啟發(fā)式解碼方法,按照個體編碼序列中工序出現(xiàn)的先后順序考慮每一道工序的分配方案,從而確定每一道工序?qū)?yīng)的工作站和工人組,此方法在不增加工人數(shù)量的情況下,盡可能地將工序分配到當(dāng)前工作站上,當(dāng)無法繼續(xù)分配工序時,再新增工人,使得當(dāng)前工作站上工人的時間利用率達(dá)到最大。工作站j上工人的時間利用率urj的定義如式(22)所示。工人的時間利用率越高,工作站上所需要的工人數(shù)量越少,對應(yīng)的裝配線平衡方案更優(yōu)。

(22)

其中:Sj為所有分配到工作站j上的工序集合,ti為工序i的所需的裝配時間,pi為工序i所需要的工人數(shù)量,CT為節(jié)拍時間,mj為被分配到工作站j上的工人數(shù)量。具體的解碼過程如下:

步驟1初始化參數(shù)。設(shè)當(dāng)前工作站的編號j=0,當(dāng)前工作站上的工人數(shù)量m=0。

步驟2判斷終止條件。若仍有工序沒有確定分配信息,使得j自增1,即開辟新的工作站,使得工作站上的工人數(shù)量m=0;否則輸出所有工序的分配信息,并結(jié)束解碼過程。

步驟3確定預(yù)分配工序。按照工序在個體編碼序列中出現(xiàn)的順序確定需要預(yù)分配的工序i。

步驟4為預(yù)分配工序指派工人。預(yù)分配工序i到工作站j上,即在工作站j上已有的工人中指派一組工人裝配工序i。若預(yù)分配成功,計算此時工作站的時間利用率,轉(zhuǎn)步驟3;否則轉(zhuǎn)步驟5。

步驟5增加與工序所需工人類型相匹配的工人。若工作站j上的工人數(shù)量小于工作站所允許的最大工人數(shù)量,即m

步驟6確定預(yù)分配工序的分配信息。搜索工作站j上所有已經(jīng)預(yù)分配的工序,找出一道工序k使得預(yù)分配完工序k時工作站j的時間利用率最高,確定所有在工序k之前完成預(yù)分配的工序(包含工序k)的分配信息,在工序k之后完成預(yù)分配的工序需要繼續(xù)分配到后續(xù)工作站上;轉(zhuǎn)步驟2。

在為工序分配工人時,若有多組工人都滿足條件,則優(yōu)先選擇開始裝配時間最早的一組工人。這種啟發(fā)式解碼方式可以使得每個工人的平均空閑時間最小,最終達(dá)到裝配線負(fù)載均衡的目的。

3.2.3 自適應(yīng)長度的傳播算子

離散傳播算子主要是進(jìn)行鄰域搜索,為保證搜索過程中不破壞個體的編碼約束,引入多段交叉的思想設(shè)計傳播算子,算子的操作過程為:隨機(jī)選擇當(dāng)前個體X1的一個片段,并使用輪盤賭[19]的方法選擇種群中的另外一個個體X2,將X1中所選片段的所有工序按照它們在X2中出現(xiàn)的相對順序重新排列,用重新排列后的新片段代替X1中的原片段,從而得到一個新個體X′。在如圖6所示的傳播算子示例中,選擇X1的一個片段[1,3,4,6],按照它們在X2中出現(xiàn)的相對順序重新排列得到新片段[1,4,3,6],將新片段代替X1中的原片段,得到新個體X′。

圖6 傳播算子示意圖

由于復(fù)雜多人共站裝配線平衡問題(CMALBP)是離散優(yōu)化問題,因此,對傳播算子進(jìn)行重新設(shè)計,如式(23)所示:

(23)

式(23)中,兩個個體進(jìn)行多段交叉操作的片段長度由參數(shù)PL自適應(yīng)調(diào)整,從而控制傳播算子的搜索范圍,PL的計算公式如式(24)所示:

PL=2+randInt(λ·(L-2))。

(24)

其中,為了保證搜索的有效性,設(shè)定片段長度PL的最小值為2,randInt(x)為不超過x的隨機(jī)正整數(shù),L為個體的長度,且L>2。

3.2.4 離散碎浪算子

離散碎浪算子主要是對個體進(jìn)行小范圍的鄰域搜索,為了保證搜索過程中不破壞個體的編碼約束,引入拓?fù)渑判蚍椒▉砜刂扑阉鞣较?算子的操作過程為:隨機(jī)選擇當(dāng)前個體中的一個片段,考慮片段內(nèi)工序的優(yōu)先關(guān)系約束,采用拓?fù)渑判虻姆椒óa(chǎn)生一個新的片段,并將得到的新片段代替原片段。如圖7所示的碎浪算子示例中,選擇個體X0的一個片段[1,3,4],然后根據(jù)該片段中所包含的工序的優(yōu)先關(guān)系圖,隨機(jī)選取入度為0的工序節(jié)點加入新片段,并將被選擇的工序節(jié)點從優(yōu)先關(guān)系圖中刪除,當(dāng)所有工序選取完畢時,用最終產(chǎn)生的新片段[1,4,3]代替原片段得到個體Xb,優(yōu)先關(guān)系圖的變化過程如圖8所示。

圖7 碎浪算子示意圖

圖8 碎浪算子中工序優(yōu)先關(guān)系圖變化過程示意圖

與傳播算子相同,在基本水波算法中,碎浪算子的搜索范圍取決于碎浪系數(shù)β,因此,對碎浪算子進(jìn)行離散化改造,算子搜索的片段長度BL如式(25)所示:

BL=2+randInt(β·(L-2))。

(25)

其中:BL為碎浪算子的搜索長度,β為碎浪系數(shù),其他參數(shù)與式(24)相同。

3.2.5 引入擾動個體的折射算子

在基本水波優(yōu)化算法中,折射算子操作容易導(dǎo)致種群過早收斂,因此,在執(zhí)行離散折射算子時,以pn的概率引入一個擾動個體X′,擾動個體X′通過拓?fù)渑判虻姆绞疆a(chǎn)生,同時,引入路徑重連[20]的思想,以1-pn的概率搜索初始個體X和最優(yōu)個體X*之間的解空間,從而增加種群的多樣性,進(jìn)一步提高算法的全局搜索性能。

初始個體X和最優(yōu)個體X*之間的搜索過程為:以當(dāng)前種群中的最優(yōu)個體X*為導(dǎo)向,按照一組隨機(jī)生成的序列依次交換初始個體X中兩道工序的位置,直到初始個體X與最優(yōu)個體X*完全相同;在交換過程中會產(chǎn)生與初始個體X和最優(yōu)個體X*都不相同的中間個體,從所有中間個體中選擇適應(yīng)度值最大的個體作為最終輸出的個體X′。

在搜索中間個體的過程中,可能會破壞個體編碼序列的優(yōu)先關(guān)系約束,導(dǎo)致算法的尋優(yōu)效率下降,因此,采用拓?fù)渑判虻姆椒▽χ虚g個體進(jìn)行修正。在修正過程中,若有多個工序節(jié)點入度為0,則優(yōu)先選擇最先出現(xiàn)的工序節(jié)點。

如圖9所示的離散折射算子示例中,對初始個體X0使用離散折射算子,通過3次工序位置交換后得到最優(yōu)個體X*,同時產(chǎn)生了兩個中間個體X1、X2,由于X2中片段[3,1]不符合個體編碼序列的優(yōu)先關(guān)系約束,因此采用拓?fù)渑判蚍椒▽⑵湫拚秊閇1,3,2,4,5,6,7],最后,從X1和X2中選擇適應(yīng)度值最大的個體作為最終輸出的個體X′。

圖9 離散折射算子示意圖

4 實驗分析

4.1 算法參數(shù)設(shè)置

4.1.1 測試用例

本文所研究的復(fù)雜多人共站裝配線平衡問題(CMALBP)是以實際動車裝配線為背景提煉出來的,由于動車是大型裝配產(chǎn)品,在實際調(diào)度過程中,裝配工序的數(shù)量多、復(fù)雜程度不同,裝配任務(wù)需要由不同數(shù)量和類型的工人協(xié)作完成。與多人共站裝配線平衡問題(MALBP)相比,CMALBP更注重于研究具有多工種的并行裝配任務(wù)優(yōu)化,因此,針對該類裝配線平衡問題的優(yōu)化,在平衡工作站負(fù)載以減少工作站數(shù)量和提高生產(chǎn)效率的同時,需考慮指派不同規(guī)模和類型的工人組完成裝配任務(wù),盡可能地減少工人數(shù)量并提高工人的工作效率,從而降低企業(yè)的勞動力成本。

由于當(dāng)前難以找到CMALBP的標(biāo)準(zhǔn)測試用例,為了驗證算法的有效性,結(jié)合動車裝配線的實際生產(chǎn)情況,生成了考慮以下3個因素的測試用例:

(1)裝配工序所需的工人類別不同;

(2)裝配工序的復(fù)雜程度不同,不同工序由數(shù)量不同的工人協(xié)作完成;

(3)實際裝配空間有限,工作站內(nèi)所能容納的工人數(shù)量存在上限值。

同時,為了說明算法對不同規(guī)模的CMALBP的求解能力,設(shè)定不同工序數(shù)量的測試用例來說明實際裝配線中不同規(guī)模的問題,并將每一組測試用例的節(jié)拍時間分別設(shè)置為16、24、32、40,CMALBP測試用例的基本信息如表2所示。

表2 CMALBP測試用例信息

4.1.2 參數(shù)設(shè)置實驗

本文所提出的改進(jìn)離散水波優(yōu)化(DWWO)算法有幾個重要的參數(shù),分別為:波長衰減系數(shù)α、碎浪系數(shù)β、初始波長λ0、最大高度Hmax以及折射算子中的擾動概率pn,取α=1.001、β=0.2。DWWO算法的搜索效率主要取決于參數(shù)λ0、Hmax和pn的取值,如果搜索的精度不夠高,將會導(dǎo)致當(dāng)前解偏離全局最優(yōu)解的方向,進(jìn)而影響整個算法的尋優(yōu)性能,因此設(shè)計實驗確定最優(yōu)的參數(shù)組合。

實驗采用不同參數(shù)組合下的DWWO算法分別求解如表2所示的測試用例,算法在每個測試用例上獨立運行20次,選擇使算法性能最優(yōu)的參數(shù)組合作為后續(xù)實驗的參數(shù)。在實驗中,λ0分別設(shè)置為0.5、0.75、1.0,Hmax分別設(shè)置為4、6、8、10,pn分別設(shè)置為0.0、0.25、0.5、0.75、1.0,參數(shù)組合共有3×4×5=60種可能的情況,記錄算法在不同參數(shù)組合下的實驗結(jié)果,并使用平均相對偏移量(APRD)來評估算法的性能,APRDt表示算法在測試用例t上的平均相對偏移量,APRDt越小,則說明算法在測試用例t上的結(jié)果越好。APRDt的計算公式如式(26)所示:

(26)

其中:t為測試用例的編號,Ctr為算法在測試用例t上第r次運行所得結(jié)果,R為算法的獨立運行次數(shù),Ctmin為算法在第t個測試用例上的不同參數(shù)組合下所能找到的最優(yōu)值。

由于APRDt只能用來評估采用某種參數(shù)組合的算法求解測試用例t的結(jié)果優(yōu)劣,而無法判斷該參數(shù)組合對算法整體性能的影響,計算總偏移量(SRD)來評價每種參數(shù)組合的優(yōu)劣。SRD的計算公式如式(27)所示:

(27)

其中n為測試用例總數(shù),其他符號含義與式(26)相同。由相對偏移量和總偏移量的關(guān)系可知,SRD越小,算法的整體性能越好。

算法在每種參數(shù)組合下的SRD的計算結(jié)果如圖10所示,在60種參數(shù)組合所得的實驗結(jié)果中,采用第22種參數(shù)組合的算法的總偏移量之和最小,此時的參數(shù)組合為λ0=1、Hmax=6、pn=0.25,即在該參數(shù)組合下,算法的整體性能最優(yōu)。

圖10 60種參數(shù)組合作用下的SRD

為了進(jìn)一步分析3個參數(shù)單獨作用時對算法整體性能的影響,對算法在不同參數(shù)組合下的總偏移量進(jìn)行統(tǒng)計分析,如圖11所示。圖11a表示在λ0取值分別為0.5、0.75、1時,對應(yīng)的Hmax和pn的20種可能組合下的總偏移量之和;圖11b表示Hmax取值分別為4、6、8、10時,對應(yīng)的λ0和pn的15種可能組合下的總偏移量之和;圖11c表示pn取值分別為0、0.25、0.5、0.75、1時,對應(yīng)的λ0和Hmax的12種可能組合下的總偏移量之和?？梢钥闯?在λ0、Hmax、pn單獨作用下所對應(yīng)的總偏移量之和最小時的取值分別為1、6、0.25,與3個參數(shù)的最優(yōu)組合取值一樣,也就是說,當(dāng)每個參數(shù)取值最優(yōu)時,算法的整體性能最好。因此,選擇λ0=1,Hmax=6,pn=0.25,此時算法效果最好。

圖11 3個參數(shù)單獨作用時的SRD

4.2 測試用例分析

4.2.1MALBP標(biāo)準(zhǔn)測試用例實驗

為了測試算法的精度以及算法對不同規(guī)模問題的求解能力,分別從文獻(xiàn)[6]中不同規(guī)模的MALBP標(biāo)準(zhǔn)測試用例中選擇了工序數(shù)量N≤30的11個小規(guī)模測試用例、工序數(shù)量3090的6個大規(guī)模測試用例作為測試集,使用離散水波優(yōu)化(DWWO)算法求解,算法在每個測試用例上獨立執(zhí)行20次,記錄實驗結(jié)果的平均值、最優(yōu)值和標(biāo)準(zhǔn)差,并與蟻群優(yōu)化[6](Ant Colony Optimization,ACO)算法、模擬退火[21](Simulated Annealing,SA)算法以及改進(jìn)候鳥遷移[22](Effective modified Migrating Birds Optimization,EMBO)算法進(jìn)行了對比,EMBO算法的參數(shù)按照文獻(xiàn)[22]中的數(shù)值進(jìn)行設(shè)置。表3中:N為工序數(shù)量,CT為節(jié)拍時間,AVG、BEST和STD分別表示實驗結(jié)果的平均值、最優(yōu)值和標(biāo)準(zhǔn)差,實驗結(jié)果中前一個數(shù)字代表工人數(shù)量,后一個數(shù)字代表工作站數(shù)量,如“5,3”表示優(yōu)化后總工人數(shù)量為5人,工作站數(shù)量為3個,同時,使用粗體表示工人數(shù)量和工作站數(shù)量都為最優(yōu)時的結(jié)果。

表3 算法在MALBP標(biāo)準(zhǔn)測試用例上的實驗結(jié)果

由表3可得,在29個不同規(guī)模大小的標(biāo)準(zhǔn)測試用例中,DWWO算法可在27個用例中(占93.1%)獲得最優(yōu)的平均值,較ACO算法(17個用例,占58.6%)和EMBO算法(10個用例,占34.5%)有更好的整體尋優(yōu)性能。雖然文獻(xiàn)[21]沒有提供SA算法對應(yīng)的平均值和標(biāo)準(zhǔn)差數(shù)據(jù),但DWWO算法較SA算法在更多的測試用例上獲得更好的最優(yōu)值;而DWWO算法在未求得最優(yōu)值的兩個測試用例上,其工作站數(shù)量較ACO算法和SA算法大大減少,即所得平衡方案對應(yīng)的裝配線線長更短,這說明DWWO算法在優(yōu)化工作站數(shù)量上性能更優(yōu)。同時,4種算法對于小、中規(guī)模測試用例的求解效果沒有明顯差異,但在大規(guī)模測試用例上,DWWO算法均求得了最優(yōu)的平均值和最好值,這說明DWWO算法對于大規(guī)模問題的求解更有優(yōu)勢。

為了進(jìn)一步分析算法對于MALBP中工人數(shù)量的優(yōu)化性能,引入文獻(xiàn)[21]中使用的線效率(LE)和平滑指數(shù)(SI)兩個裝配線平衡性度量指標(biāo)對求解方案的優(yōu)劣進(jìn)行評估,LE和SI的計算公式分別如式(28)和式(29)所示:

(28)

(29)

其中:ti為第i道工序的裝配時間,N為裝配線的總工序數(shù)量,NM為優(yōu)化后的總工人數(shù)量,CT為節(jié)拍時間,Tl為第l位工人的總裝配時間。

由式(28)可得,對于同一個測試用例,工序的總裝配時間和工作站的節(jié)拍時間相同,則線效率與優(yōu)化所得調(diào)度方案的總工人數(shù)量成反比,即總工人數(shù)量越少,線效率的值就越大,裝配線的平衡性越好。由式(29)可得,對于同一個測試用例,工作站的節(jié)拍時間相同,每個工人的總裝配時間與節(jié)拍時間的差即為該工人的空閑時間,則平滑指數(shù)與優(yōu)化所得調(diào)度方案中工人的空閑時間以及總工人數(shù)量有關(guān),當(dāng)總工人數(shù)量一樣時,工人的空閑時間越小,平滑指數(shù)的值就越小,裝配線上工人之間的負(fù)載差異越小。

由于文獻(xiàn)[6]沒有提供ACO算法優(yōu)化所得平衡方案對應(yīng)的LE和SI,因此只計算表3中DWWO算法和EMBO算法在5組測試用例的不同節(jié)拍時間下所得的最優(yōu)平衡方案對應(yīng)的平均線效率和平滑指數(shù),記為LE(AVG)和SI(AVG),并與文獻(xiàn)[21]中SA算法所得數(shù)據(jù)進(jìn)行對比,用粗體標(biāo)明LE(AVG)和SI(AVG)最優(yōu)的結(jié)果,如表4所示。

由表4可知,SA算法對應(yīng)的平均線效率性能最優(yōu),DWWO算法對應(yīng)的平均平滑指數(shù)性能最優(yōu),說明SA算法所得平衡方案有利于降低裝配線上的勞動力成本,而DWWO算法所得平衡方案有利于降低工人之間的負(fù)載差異,提高工人的利用率。

4.2.2 CMALBP測試用例實驗

表5 算法在CMALBP測試用例上的實驗結(jié)果

由表5可得,在20個測試用例中,從優(yōu)化所得的平均值(AVG)來看,DWWO算法可得到15個用例(占75%)的最好結(jié)果,SA算法可得到4個用例(占20%)的最好結(jié)果,EMBO算法可得到9個用例(占45%)的最好結(jié)果;就最優(yōu)值(BEST)而言,DWWO算法在18個用例(占90%)上獲得了最好結(jié)果,SA算法和EMBO算法分別在9個用例(占45%)上獲得了最好結(jié)果;這說明DWWO算法較另外兩種算法所得的裝配線平衡方案更優(yōu)。由于DWWO算法在測試用例5(工序數(shù)>100)的大規(guī)模測試用例上均取得了最好的平均值和最優(yōu)值,較其他算法優(yōu)勢更加明顯,再次證明了DWWO算法更適用于求解大規(guī)模問題。

為了分析算法在優(yōu)化工人數(shù)量和工作站數(shù)量上的性能,計算3種算法在20個測試用例上求得的工人數(shù)量平均相對偏移量(APRD-W)和工作站數(shù)量平均相對偏移量(APRD-S)。APRD-W和APRD-S的計算方法與式(26)相同,但是目標(biāo)函數(shù)值分別替換為最小工人數(shù)量和最小工作站數(shù)量。3種算法在20個測試用例上的APRD-W和APRD-S可以用箱線圖表示,如圖12和圖13所示。

圖12 3種算法對應(yīng)的APRD-W箱線圖

圖13 3種算法對應(yīng)的APRD-S箱線圖

由圖12可知,DWWO算法的APRD-W整體較另外兩種算法都小,說明DWWO算法在優(yōu)化工人數(shù)量方面較另外兩種算法性能更好。由圖13可知,DWWO算法在APRD-S上其整體性能優(yōu)于SA算法,而與EMBO算法相比,其所得中位數(shù)和最大值更大,但其在上四分位數(shù)值較EMBO算法更小,而且經(jīng)過計算得到的平均值也較EMBO算法略小,說明DWWO算法與EMBO算法在APRD-S上性能接近。

同樣地,采用線效率(LE)和平滑指數(shù)(SI)來評估不同算法所得CMALBP平衡方案的優(yōu)劣。與MALBP不同的是,CMALBP中一道工序需要由多個工人協(xié)同裝配,而工序的實際總裝配時間等于工序的裝配時間乘以該道工序所需的工人數(shù)量,此時LE的計算公式(28)將不再適用于CMALBP,因此,重新設(shè)計LE的計算公式,如式(30)所示,而SI的計算公式中不涉及工序的裝配時間,可直接使用MALBP中的式(29)計算。

(30)

其中pi為第i道工序所需的工人數(shù)量,其他參數(shù)與式(28)相同。

分別計算3種算法在表5中5組CMALBP測試用例的不同節(jié)拍時間下所得的最優(yōu)平衡方案對應(yīng)的LE(AVG)和SI(AVG),并用粗體標(biāo)明最優(yōu)值,結(jié)果如表6所示。

表6 算法在CMALBP測試用例上的平衡性度量指標(biāo)的計算結(jié)果

由表6可知,DWWO算法對應(yīng)的平均線效率和平滑指數(shù)的性能均為最優(yōu),說明DWWO算法相對于SA算法和EMBO算法來說,更適用于求解CMALBP。

4.2.3 動車裝配線平衡優(yōu)化

動車總裝是動車生產(chǎn)過程中的重要一環(huán),由于動車體積龐大、結(jié)構(gòu)復(fù)雜、工序繁瑣,其生產(chǎn)線較長,且總裝過程需要大量的工人參與,因此,合理地分配工序以及調(diào)度工人是維持動車生產(chǎn)平衡的關(guān)鍵。本文對實際生產(chǎn)中的動車裝配線進(jìn)行平衡優(yōu)化,從而驗證所構(gòu)建的復(fù)雜多人共站裝配線平衡問題模型的有效性。

裝配線上一共有249道工序,3種類型的工人,每種類型的工人數(shù)量不限,每天的工作時長不能超過8 h。工序的裝配時間、所需的工人類型及數(shù)量如表7所示,工序之間的優(yōu)先約束關(guān)系如表8所示。另外,由于裝配線上的空間有限,每個工作站內(nèi)可容納的最大工人數(shù)量為25,根據(jù)最長工序路徑計算所得理論最優(yōu)工作站數(shù)量為18個。

表7 裝配工序信息

表8 工序優(yōu)先約束關(guān)系

以最小化工作站數(shù)量和工人數(shù)量為目標(biāo),建立該實例的CMALBP數(shù)學(xué)模型,并采用DWWO算法進(jìn)行求解,最終得到裝配線上的工序分配方案以及工人指派方案。由于文章篇幅有限,圖14僅給出工作站1的工人裝配甘特圖,其中,橫坐標(biāo)為工人的工作時長,縱坐標(biāo)為工作站編號-工人編號,綠色、藍(lán)色、黃色分別表示類型1、類型2、類型3的工人,甘特圖中標(biāo)明的數(shù)字為工序的編號。最終優(yōu)化所得的工人數(shù)量為454,工作站數(shù)量為19個,根據(jù)式(29)和式(30)分別計算得到裝配線的平滑指數(shù)(SI)為0.149、線效率(LE)為0.945,與現(xiàn)有的裝配線方案相比有較好的提高。

圖14 工作站1的工人裝配甘特圖

5 結(jié)束語

本文提出一種復(fù)雜多人共站的裝配線平衡問題(CMALBP),該問題考慮了多人協(xié)同裝配一道工序和工人技能差異等特殊情況,將裝配線所需要的工作站數(shù)量和工人數(shù)量的加權(quán)和作為目標(biāo)函數(shù),優(yōu)化裝配線平衡方案使得總成本最小。針對該組合優(yōu)化問題,提出一種離散水波優(yōu)化(DWWO)算法求解,設(shè)計了考慮工序優(yōu)先關(guān)系約束的編碼方案和啟發(fā)式的解碼方案,并針對編碼方案的特點設(shè)計了3種離散算子。同時,在MALBP標(biāo)準(zhǔn)測試用例上,將DWWO與ACO、SA、EMBO算法的實驗結(jié)果進(jìn)行對比,通過計算線效率和平滑指數(shù)兩個平衡性度量指標(biāo),驗證了DWWO算法的求解精度。最后,結(jié)合動車裝配線的實際生產(chǎn)情況,分別采用DWWO、SA和EMBO算法求解CMALBP測試用例,驗證了DWWO算法的適用性以及在求解大規(guī)模問題上的優(yōu)越性,并通過實例求解驗證了所建模型的有效性。后續(xù)可以針對實際裝配過程中的動態(tài)因素進(jìn)行更深入的研究,以提高模型的適用范圍和DWWO算法的魯棒性。