混合算法求解裝配線平衡與多技能工分配研究*

張國輝，焦迎濤，孫靖賀，張海軍

(鄭州航空工業(yè)管理學(xué)院 a.管理工程學(xué)院；b.航空工程學(xué)院，鄭州 450015)

0 引言

裝配線平衡問題旨在滿足約束條件的前提下，組合并分配單元作業(yè)，以使各工作站工時(shí)盡可能相等，最大限度地提高裝配線的整體效率[1]。楚克明等[2]運(yùn)用自適應(yīng)遺傳算法求解混流裝配線的排序問題，提高了求解搜索能力和效率。馬東升等[3]研究了在考慮需求波動(dòng)前提下，最小化資源成本和工作站成本的混流裝配線資源配置問題。甘雅文等[4]研究了主客觀因素交互影響下混合裝配線的排序問題，建立以最小化工作站堵塞時(shí)間與最小化產(chǎn)品切換次數(shù)為目標(biāo)的交互排序模型并進(jìn)行了求解。

然而，由于裝配線上每個(gè)工作站的操作工人存在技能差別，也會(huì)影響裝配線的節(jié)拍和平衡。員工的多種技能能夠有效的滿足裝配線各工位對(duì)不同技能的需求，提高裝配線的靈活性。Süer G A[5]將熟練程度分為9個(gè)類別，根據(jù)熟練程度水平，使用標(biāo)準(zhǔn)偏差值計(jì)算員工的操作時(shí)間。楊紅光等[6]考慮人力資源和空間等約束的前提下，構(gòu)建了以最大化裝配線產(chǎn)能和最小化人員成本為優(yōu)化目標(biāo)的裝配線人員再分配模型。李愛平等[7]針對(duì)裝配關(guān)系復(fù)雜性影響工人工作效率進(jìn)而導(dǎo)致產(chǎn)生瓶頸工位的問題，提出一種考慮裝配關(guān)系復(fù)雜性的改進(jìn)型多目標(biāo)裝配線平衡優(yōu)化方法。然而，已有文獻(xiàn)中更多關(guān)注人力成本約束問題[8]，考慮到員工技能等級(jí)和員工技能訓(xùn)練提升等因素，同時(shí)將工位分配和裝配線平衡集成的研究較少。

本文構(gòu)建多技能員工分配和裝配線平衡集成的數(shù)學(xué)模型，以裝配線的平衡率和員工技能強(qiáng)化訓(xùn)練的收益最大為優(yōu)化目標(biāo)，采用混合粒子群遺傳算法(Particle swarm optimization and Genetic algorithm，PSOGA)進(jìn)行求解，并通過實(shí)際案例進(jìn)行不同算法運(yùn)算結(jié)果對(duì)比，驗(yàn)證了建立的模型和提出的方法是可行和有效的。

1 問題描述與模型構(gòu)建

多技能員工分配和裝配線平衡問題可描述為：現(xiàn)有m個(gè)不同技能的員工和n個(gè)工作站(m≥n)，工作站的編號(hào)為j(1≤j≤n)，裝配的順序已知，且按照工作站的序號(hào)進(jìn)行。每位員工i(1≤i≤m)完成工作站j作業(yè)時(shí)間集為Tij。采用最大最小原則確定節(jié)拍，對(duì)不同工作站中最小的作業(yè)時(shí)間作比較，選取其中最大作業(yè)時(shí)間的工作站作為瓶頸工作站，并設(shè)定為該裝配線的節(jié)拍(CT)。員工的技能水平劃分為4個(gè)技能等級(jí)，并對(duì)其實(shí)際達(dá)到的技能狀況進(jìn)行分級(jí)評(píng)估。按熟練程度由低到高依次分為一級(jí)、二級(jí)、三級(jí)和四級(jí)，其中三級(jí)員工的作業(yè)時(shí)間為標(biāo)準(zhǔn)工時(shí)。不同工作站需要的技能不同，也就是說有的員工并不能在所有操作站上進(jìn)行分配。每個(gè)工作站上的員工通過從事低技能水平的工作，從而提高技能水平，獲得技能訓(xùn)練收益。

本文在進(jìn)行多技能員工分配時(shí)假設(shè)條件如下：

1)每個(gè)員工同時(shí)只能在一個(gè)工作站上工作，每個(gè)工作站僅能分配一個(gè)員工；

2)每個(gè)員工的技能范圍和水平已知；

3)三級(jí)員工的標(biāo)準(zhǔn)工時(shí)已知；

4)員工技能水平每提高一個(gè)等級(jí)作業(yè)時(shí)間減少10%；

5)技能訓(xùn)練的收益受限于工作站可從事員工數(shù)；

6)員工作業(yè)時(shí)間大于瓶頸工作站的工作時(shí)間時(shí)，刪除該員工技能。

建立兩個(gè)優(yōu)化目標(biāo)：

目標(biāo)1：裝配線的平衡率(LOB)最高，如式(1)。這個(gè)目標(biāo)也相當(dāng)于最小化裝配線的平滑度指標(biāo)，減少CT和Tij的總偏差。

(1)

目標(biāo)2：?jiǎn)T工技能訓(xùn)練的收益最大，如式(2)。這個(gè)目標(biāo)函數(shù)用于提高多技能員工分配所獲得訓(xùn)練收益(En)，其中pj表示不具備工作站j所需技能的員工個(gè)數(shù)。

(2)

采用加權(quán)方式對(duì)f1和f2合并為目標(biāo)函數(shù)f，如式(3)。w1，w2是表示f1和f2重要程度的參數(shù)，其值可以根據(jù)對(duì)于裝配線平衡和技能訓(xùn)練之間的重視程度進(jìn)行選取。

f=w1×f1+w2×f2

(3)

其中，w1+w2=1。

(4)

目標(biāo)函數(shù)中的變量和約束說明如下：

(5)

(6)

(7)

(8)

式(5)表示節(jié)拍的確定；式(6)表示員工是否被分配到相應(yīng)工作站上的決策變量；式(7)表示員工i僅分配一個(gè)工作站；式(8)表示工作站j僅分配一名員工。

圖1 PSOGA的算法流程圖

2 混合粒子群優(yōu)化算法

粒子群優(yōu)化算法是模擬鳥類覓食行為的一種群智能優(yōu)化算法，因其操作簡(jiǎn)單、易于實(shí)現(xiàn)而得到廣泛應(yīng)用于解決連續(xù)和離散優(yōu)化問題[9-10]。本文將粒子群優(yōu)化算法和遺傳算法進(jìn)行結(jié)合，提出混合粒子群優(yōu)化算法，算法流程框架如圖1所示。為了能夠更好地平衡算法求解過程中的全局搜索和局部搜索能力，并且提高算法的運(yùn)算效率和解的質(zhì)量，設(shè)計(jì)了定向變異和局部搜索算子。

2.1 編碼

好的編碼方式容易在后續(xù)操作中產(chǎn)生可行的解決方案，避免不可行的解決方案帶來的補(bǔ)救措施，能夠提高效率。

PSOGA中編碼采用員工編號(hào)的十進(jìn)制編碼方法。n個(gè)工作站分配m(m≥n)個(gè)員工，每個(gè)工作站一個(gè)員工。分配給n個(gè)工作站員工的粒子表示為P=(π1,...,πj,...,πn)。其中j為1～n的排列，πj由1～n的隨機(jī)非重復(fù)序列表示，如圖2所示π6=5，表示工作站6由5號(hào)員工承擔(dān)。

圖2 編碼方法

2.2 位置更新和速度更新

粒子群算法通過速度更新和位置更新實(shí)現(xiàn)粒子更新，主要用于求解連續(xù)無約束優(yōu)化問題。PSOGA由于員工分配問題的離散性與傳統(tǒng)的粒子速度和位置更新方式不同。員工分配問題中粒子速度Vt(Vt是行為工作站數(shù)m，列為粒子數(shù)的矩陣，即為交換序1)，t是目前迭代次數(shù)，初始所有粒子的速度V1為隨機(jī)生成矩陣，矩陣數(shù)值上限為n，下限為0。Vt+1是Vt中的數(shù)值以概率z(z為慣性系數(shù)，隨迭代次數(shù)增加而遞減)保留，未保留的數(shù)值將變?yōu)?。交換序2表示Pbest(個(gè)體最優(yōu)粒子)對(duì)粒子位置的影響。交換序3為Gbest(全局最優(yōu)粒子)對(duì)粒子位置的影響。交換序2和交換序3的確定方式為，從Pbest中取出元素i，然后從個(gè)體中取出元素k，如果兩個(gè)元素值相同且k≠i，則計(jì)交換序2的第i個(gè)元素值為k。同理確定交換序3。交換序2和交換序3的數(shù)值分別以概率c1和概率c2保留，未保留的數(shù)值將變?yōu)?。交換序1、2、3分別和粒子群中的每一個(gè)粒子進(jìn)行交換即通過粒子速度、Pbest、Gbest實(shí)現(xiàn)粒子位置更新。具體更新方式為：如圖3找到粒子中與交換序第1個(gè)元素對(duì)應(yīng)數(shù)值5相同數(shù)值所在的元素5，將粒子元素5的數(shù)值和元素1的數(shù)值進(jìn)行交換。當(dāng)交換序中數(shù)值為零則不發(fā)生交換，同理執(zhí)行其他元素的交換。

圖3 位置更新

通過將粒子當(dāng)前位置Xt和交換序1、2、3依次發(fā)生交換后實(shí)現(xiàn)粒子位置更新Xt+1，其中z的值隨著迭代次數(shù)(Iteration)的增加而減少服從公式(9)，其中maxInteration為最大迭代次數(shù)。

z=0.96-Iteration/maxIteration

(9)

2.3 粒子交叉

粒子交叉操作是隨機(jī)選中一段粒子片段與Gbest的相同位置片段進(jìn)行交叉，保留粒子交叉前后的最優(yōu)粒子。由于交叉后會(huì)存在相同元素值，而模型和算法本身不允許存在相同元素值，刪除個(gè)體中元素值相同的元素，保留交叉前后最優(yōu)值作為更新后的粒子。生成隨機(jī)數(shù)r1，r2，使得r1≠r2，如圖4所示。假設(shè)r1=6，r2=4，對(duì)于個(gè)體粒子P1=[1 6 5 7 3 8 4 2 9]選取第4～6元素的數(shù)值F1=[7 3 8]和全局最優(yōu)粒子G1=[7 3 1 8 6 9 2 4 5]的第4～6元素的數(shù)值F2=[8 6 9]交換。由于交叉后會(huì)存在相同元素，而模型和算法本身不允許存在相同元素，刪除個(gè)體P1中與F2中元素值相同的元素得到F3=[1 5 7 3 4 2]，將交叉片段F2插入到F3中第r(r=min(r1，r2))個(gè)位置。更新后的個(gè)體P2=[1 5 7 8 6 9 3 4 2]，計(jì)算P1和P2的適應(yīng)度值，保留交叉前后最優(yōu)值作為更新后的粒子。

圖4 粒子交叉

2.4 粒子變異

為了提高種群的多樣性，避免過早收斂的發(fā)生，采用隨機(jī)變異和定向變異兩種方法。

(1)隨機(jī)變異

為了保證粒子群的多樣性，避免陷入局部最優(yōu)。將群體中80%的個(gè)體進(jìn)行隨機(jī)變異，隨機(jī)選擇兩個(gè)元素進(jìn)行交換，并且計(jì)算交換前后的適應(yīng)度值，保留變異前后最優(yōu)適應(yīng)度值的粒子作為更新后的粒子。

(2)定向變異

為了使變異更有效、變異結(jié)果更好，將群體中20%的個(gè)體進(jìn)行定向變異。定向變異通過計(jì)算變異點(diǎn)全部可能發(fā)生的變異收益，從收益最大的若干個(gè)可變異選項(xiàng)中隨機(jī)選取一項(xiàng)作為變異點(diǎn)的變異結(jié)果。對(duì)于粒子P1，隨機(jī)數(shù)r5=3，P1的第3個(gè)元素π3=5，表示當(dāng)前工作站3上由5號(hào)員工工作，所需時(shí)間為T53，由于同一員工操作不同工作站熟練程度和等級(jí)不同，所需時(shí)間不同。假設(shè)3號(hào)工作站由4號(hào)員工操作，那么如圖5所示，工作站3、7的操作時(shí)間由T53變?yōu)門43，T47變?yōu)門57。然后，計(jì)算交換變異前工作站和變異后工作站所需時(shí)間和的差值Q(b)，其中b為變異點(diǎn)定向交換的工作站序號(hào)，Q(b)越大變異收益越大。如圖5中，變異點(diǎn)3，定向交換7號(hào)工作站，Q(7)=T43+T57-(T53+T47)，同理依次計(jì)算剩余可與工作站3上5號(hào)員工交換的工作站的Q(b)值。最后，根據(jù)不同的Q(b)值，按照下列偽代碼選取更新變異后的個(gè)體。

圖5 定向變異

定向變異的執(zhí)行偽代碼如下所示：

Input:交叉后的粒子1If所有Q(b)<=02 原始粒子P1不進(jìn)行變異,不更新個(gè)體3ElseifQ(b)>0的數(shù)目大于34 在排序前三的變異個(gè)體中,隨機(jī)選擇一個(gè)5Elseif6 選擇最大值的變異個(gè)體7EndOutput:變異后的粒子

2.5 局部搜索

為了提高PSOGA的搜索能力，在算法中增加了局部搜索。當(dāng)每一代迭代結(jié)束時(shí)，將執(zhí)行局部搜索。每個(gè)粒子中隨機(jī)選擇3個(gè)工作站，如圖6所示，隨機(jī)選擇工作站1、3和4，即交換工作站的工作人員，可形成6個(gè)鄰域解。

圖6 鄰域解的產(chǎn)生

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

為測(cè)試算法性能，用提出的混合粒子群優(yōu)化算法(PSOGA)與標(biāo)準(zhǔn)粒子群算法(PSO)、遺傳算法(GA)進(jìn)行對(duì)比。算法在Matlab2016軟件編程環(huán)境，在2.3 GHz、4.00 GB RAM DELL XPS13計(jì)算機(jī)上執(zhí)行。如表1所示，參數(shù)w1和w2設(shè)定了三種組合進(jìn)行計(jì)算。①僅考慮裝配線平衡率[1,0]；②同時(shí)考慮裝配線平衡率和多技能工的技能培訓(xùn)收益[0.5,0.5]；③優(yōu)先考慮多技能工的技能培訓(xùn)收益能力[0,1]。測(cè)試數(shù)據(jù)來源于斷路器裝配車間實(shí)際生產(chǎn)問題，該裝配線包括21名員工，16個(gè)工作站，如表2所示，表中“-”表示當(dāng)前員工的技能不能滿足當(dāng)前工作站的需要，即不能分配到該工作站上。

表1 參數(shù)設(shè)置

表2 工作站操作時(shí)間 (單位：s)

續(xù)表

如表3所示，分別采用PSOGA，PSO和GA這3種方法對(duì)表2中的數(shù)據(jù)進(jìn)行計(jì)算得到結(jié)果，算法運(yùn)行10次的平均值。第1列是3種算法，第2列是不同的權(quán)重設(shè)置，第3列是目標(biāo)函數(shù)平均值，第4列是獲得的最優(yōu)值，第5列是算法運(yùn)行的時(shí)間平均值。從表3中可以看出，PSOGA和GA的計(jì)算能力非常好，每次都能找到這個(gè)實(shí)例的最優(yōu)解，PSO相對(duì)較差；PSOGA在其求解能力與GA相當(dāng)?shù)耐瑫r(shí)收斂速度快于GA。PSO在計(jì)算時(shí)間上約為1.2 s，PSOGA約為2.1 s，GA約為9 s。從計(jì)算時(shí)間和優(yōu)化結(jié)果綜合比較，本文提出的GAPSO算法更有優(yōu)勢(shì)。由于表2中的問題規(guī)模較小，表3中的實(shí)驗(yàn)結(jié)果的區(qū)分度不夠明顯，經(jīng)過大規(guī)模問題的實(shí)驗(yàn)可以得出本文提出的PSOGA是非常有效的，但是限于篇幅有限，大規(guī)模問題數(shù)據(jù)的驗(yàn)證不再贅述。

表3 不同算法的計(jì)算結(jié)果

圖7顯示了這3種算法迭代過程中每代最優(yōu)個(gè)體的適應(yīng)度結(jié)果。紅色曲線代表PSO，深色曲線代表PSOGA，淺色曲線代表GA。PSOGA和PSO算法期初波動(dòng)較大，GA期初波動(dòng)較小，說明PSOGA期初種群的多樣性保持的比較好，不容易陷入局部最優(yōu)；GA相對(duì)較早搜索停滯，不再更新，PSO最后得到算法最優(yōu)解，PSOGA算法相對(duì)其他兩種算法得到最優(yōu)個(gè)體。如圖8所示，為所得員工分配示意圖。

圖7 每代最佳個(gè)體適應(yīng)值迭代圖

圖8 員工分配示意圖

4 結(jié)束語

本文考慮了多技能員工分配和培訓(xùn)問題的裝配線平衡問題。提出了一種混合粒子群優(yōu)化算法，用于平衡裝配線和提高員工技能訓(xùn)練的收益，以期望獲得更合理的多技能員工分配方案。本文利用混合粒子群算法、粒子群算法和遺傳算法進(jìn)行了不同規(guī)模的實(shí)驗(yàn)。計(jì)算結(jié)果表明，混合粒子群算法在解的質(zhì)量和時(shí)間上優(yōu)于粒子群算法和遺傳算法。同時(shí)，驗(yàn)證了混合粒子群算法在解決多技能員工調(diào)度問題上的可行性和有效性和穩(wěn)定性。

對(duì)此，后續(xù)研究可以更多關(guān)注多技能員工的分配對(duì)復(fù)雜裝配系統(tǒng)各個(gè)方面的影響；設(shè)計(jì)更好的算法或調(diào)整算法的結(jié)構(gòu)組件，以獲得更好的結(jié)果；考慮到員工的精神疲勞、學(xué)習(xí)能力以及多技能員工分配的及時(shí)性，希望能夠?qū)崿F(xiàn)更加全面的分配目標(biāo)。