面向成本的雙邊裝配線平衡和員工分配

邱玉蓮，彭嬋娟

（武漢科技大學(xué) 管理學(xué)院，湖北 武漢 430081）

1 引言

裝配線廣泛存在于制造業(yè)中，裝配線的平衡與否直接關(guān)系到裝配線的效率和企業(yè)的成本。作為一種特殊的裝配線形式，雙邊裝配線以其裝配線長(zhǎng)度短、搬運(yùn)成本低等[1]優(yōu)勢(shì)廣泛應(yīng)用于汽車、卡車等產(chǎn)品的總裝線上。

雙邊裝配線平衡問題根據(jù)目標(biāo)可主要分為兩類：第一類問題[2-3]，給定生產(chǎn)節(jié)拍，在滿足生產(chǎn)線約束條件的前提下最小化工位數(shù)量；第二類問題[4-6]，給定工位數(shù)量，在滿足生產(chǎn)線約束條件的前提下最小化生產(chǎn)節(jié)拍。目前國(guó)內(nèi)外主要研究集中于第一類雙邊裝配線平衡問題，已有多種算法[2-3]應(yīng)用于求解該NP難題。相較于第二類雙邊裝配線平衡問題，目前僅有遺傳算法[4]、蟻群算法[5]、粒子群算法[6]等用于求解該問題。由上可知，科研對(duì)第二類雙邊裝配線的平衡研究很少，但是第二類雙邊裝配線問題在實(shí)際中對(duì)于消除瓶頸工位、提高負(fù)載均衡有著廣泛的應(yīng)用前景。

以上研究均假設(shè)所有員工對(duì)相同操作的完成時(shí)間相同，但是在實(shí)際生產(chǎn)中由于員工技能的差異對(duì)相同的操作的完成時(shí)間可能不同[7]，例如殘疾人完成需要站立的操作耗時(shí)巨大，因此在實(shí)際生產(chǎn)中需要考慮員工的分配問題。同時(shí)在企業(yè)的裝配成本中，員工工資成本是其支出的主要部分[8]，所以企業(yè)越來越關(guān)注減少工資支出。由于工資成本的最優(yōu)化與裝配線的平衡可能出現(xiàn)沖突，所以需要采用多目標(biāo)優(yōu)化。

針對(duì)第II類多目標(biāo)雙邊裝配線平衡和員工分配問題，提出一種多目標(biāo)重啟模擬退火算法實(shí)現(xiàn)平衡和成本的同步優(yōu)化。設(shè)計(jì)了新的編碼和解碼方式以實(shí)現(xiàn)工位負(fù)載均衡和減少序列相關(guān)空閑時(shí)間，采用了重啟機(jī)制以獲得分布性更好的前沿解。同時(shí)將重啟模擬退火算法與快速非支配排序遺傳算法進(jìn)行對(duì)比，證明了算法的高效性。

2 雙邊裝配線平衡和員工分配

2.1 問題介紹

在雙邊裝配線上，如圖1所示。左右兩個(gè)工位合稱為成對(duì)工位，每個(gè)工位上均分配有相應(yīng)操作。第II類雙邊裝配線員工分配和平衡問題可分為兩個(gè)子問題，即員工分配和裝配線平衡問題。在員工分配中，每個(gè)工位分配一個(gè)員工，其對(duì)同一操作的完成時(shí)間可能區(qū)別于其他員工。在裝配線平衡中，每個(gè)操作在滿足有限關(guān)系約束、方向約束的情況下被分配到對(duì)應(yīng)的工位。

圖1 雙邊裝配線工位布置Fig.1 Task Assignment of Two-Sided Assembly Line

圖2 操作數(shù)為12的優(yōu)先關(guān)系圖Fig.2 Precedence Diagram for 12-Task Problem

對(duì)應(yīng)圖1分配方案的優(yōu)先關(guān)系圖，如圖2所示。圖2中，共有3類不同操作，分別為：操作方向?yàn)樽筮叺牟僮鳎↙），操作方向?yàn)橛疫叺牟僮鳎≧）和操作方向?yàn)槿我夥较虻牟僮鳎‥）。圖中，圓圈內(nèi)的數(shù)字代表操作，圓圈上的標(biāo)簽代表操作的作業(yè)時(shí)間和操作的方向。圓圈間的箭頭代表操作間的優(yōu)先關(guān)系，以操作1和4間的箭頭為例，其代表操作1是操作4的前序。

2.2 問題模型

為同步優(yōu)化工資成本和負(fù)載平衡，分別設(shè)計(jì)了如下兩個(gè)目標(biāo)，如式（1）、式（2）所示。依次對(duì)應(yīng)工資成本和負(fù)載均衡。為簡(jiǎn)化起見，以下主要說明兩個(gè)目標(biāo)函數(shù)，其它優(yōu)先關(guān)系、員工分配等約束請(qǐng)參考相關(guān)文獻(xiàn)[3，7]。

式中：i—操作；j—成對(duì)工位；k—成對(duì)工位的左右兩邊；J—成對(duì)工位集合；wi—單位時(shí)間內(nèi)操作i的工資；CT—節(jié)拍；SFjk—工位（j，k）最后一個(gè)操作的完成時(shí)間；STjk—工位（j，k）分別的操作的加工時(shí)間總和；xijk判斷操作i是否分配到工位（j，k），如果分配到工位（j，k）取值1，否則取值為0。

式（1）中工資成本設(shè)置文獻(xiàn)[8]，其中單位時(shí)間內(nèi)每個(gè)操作的工資水平由操作的難度決定，整個(gè)工位的單位工資水平由分配到該工位的最難的操作對(duì)應(yīng)的單位工資水平?jīng)Q定。式（2）的前半部分最小化工位最后完成時(shí)間的偏差，后半部分最小化工位實(shí)際分配負(fù)載的偏差。

3 重啟模擬退火算法

模擬退火算法廣泛應(yīng)用于各類優(yōu)化問題，例如裝配線平衡問題[2]。模擬退火算法是基于鄰域的局部搜索算法，由于所研究的問題為多目標(biāo)問題，設(shè)計(jì)了新的接受準(zhǔn)則和重啟機(jī)制。

3.1 編碼及解碼

由于考慮的問題涉及到裝配線平衡和員工分配兩個(gè)問題，所以采用了3個(gè)數(shù)組進(jìn)行編碼，分別為員工分配數(shù)組，操作分配數(shù)組和操作排序數(shù)組.以下以一個(gè)案例說明編碼和解碼情況，如圖3所示。其中，員工分配數(shù)組中第一個(gè)位置的3表示，第一個(gè)成對(duì)工位的左邊分配的員工編號(hào)為3.操作分配決定操作分配的成對(duì)工位，操作排序數(shù)組決定操作分配的優(yōu)先級(jí)。為獲得每個(gè)工位的詳細(xì)分配的方案，采用文獻(xiàn)[6]中解碼方式獲得滿足優(yōu)先關(guān)系約束和方向約束的分配方案。需要指明，以上解碼可作為文獻(xiàn)[4]中的解碼的一種改進(jìn)方式，其通過工位選擇策略實(shí)現(xiàn)成對(duì)工位內(nèi)部的負(fù)載均衡，通過操作選擇策略有效減少工位上的空閑時(shí)間。

圖3 編碼及解碼Fig.3 Encoding and Decoding Procedure

3.2 鄰域結(jié)構(gòu)設(shè)計(jì)

由于解碼中涉及了3個(gè)數(shù)組，所以設(shè)計(jì)了3種不同的領(lǐng)域結(jié)構(gòu)，介紹如下：（1）針對(duì)員工分配的領(lǐng)域結(jié)構(gòu)：采用交換操作。（2）針對(duì)操作分配的鄰域結(jié)構(gòu)：采用隨機(jī)選擇交換操作和變異操作兩個(gè)方式中的一種。變異操作隨機(jī)選擇一個(gè)操作，將其對(duì)應(yīng)的成對(duì)工位變成其他成對(duì)工位。（3）針對(duì)操作排序的鄰域結(jié)構(gòu)：采用插入操作。在鄰域結(jié)構(gòu)的選擇中，對(duì)應(yīng)每個(gè)數(shù)組，隨機(jī)產(chǎn)生一個(gè)0到1之間的小數(shù)，如果小于1/3，則對(duì)該數(shù)據(jù)進(jìn)行變動(dòng)。以上鄰域選擇方式允許變動(dòng)多個(gè)數(shù)組，有效增大搜索空間。

3.3 帕累托解集更新及接受準(zhǔn)則

當(dāng)使用鄰域結(jié)構(gòu)產(chǎn)生一個(gè)新解后，如果該解沒被其他任何解支配，則該解被添加到帕累托前沿解集，同時(shí)移除前沿解集中被支配的解。更新完帕累托前沿解集后，新產(chǎn)生的解替換原來的解S，即S←S′。當(dāng)新解被前沿中的某個(gè)解支配，采用多項(xiàng)概率密度函數(shù)[9]從2個(gè)優(yōu)化目標(biāo)中選取一個(gè)以判斷是否接受該解。在目標(biāo)概率密度函數(shù)中，每個(gè)目標(biāo)被選擇的概率設(shè)定為0.5.假設(shè)選擇其中一個(gè)目標(biāo)f（*），則目標(biāo)值的變化為Δ，Δ=f（S′）-f（S）。如果Δ≤0，則新解被接受并替代當(dāng)前解。否則，按照exp-Δ/（T×f（S））的概率接受該新解，式中：T—溫度參數(shù)。

3.4 重啟機(jī)制

為增強(qiáng)算法跳出局部最優(yōu)的能力，設(shè)計(jì)了一種重啟機(jī)制以獲取更多的前沿解，如圖4所示。如果連續(xù)dn次迭代均不能發(fā)現(xiàn)新的前沿解，則從當(dāng)前前沿解集中選擇一個(gè)解作為代替當(dāng)前解。改進(jìn)聚集距離[10]做了如下改進(jìn)：

（1）極值解的距離設(shè)定為1，而非原來的無窮大。

（2）將選擇的次數(shù)融入到聚集距離中，且前沿解的聚集距離隨著被選擇次數(shù)的增加而逐漸減少。

圖4 重啟機(jī)制流程圖Fig.4 The Procedure of Restart Mechanism

3.5 算法流程

在重啟模擬退火算法中，連續(xù)執(zhí)行NS次后鄰域搜索后，對(duì)溫度系數(shù)T按照T=αT進(jìn)行更新，式中：α—冷卻系數(shù)。詳細(xì)算法流程，如圖5所示。

圖5 重啟模擬退火算法流程圖Fig.5 The Procedure of Restarted Simulated Annealing

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

為驗(yàn)證重啟模擬退火算法的性能，生成了總共7組案例（P9，P12，P16，P24，P65，P148以及P205），并將重啟模擬退火算法與快速非支配排序遺傳算法進(jìn)行對(duì)比[10]。每個(gè)員工對(duì)操作i的加工時(shí)間為［ti×0.8，ti×1.2］之間的隨機(jī)數(shù)，ti為文獻(xiàn)[4]中操作 i的加工時(shí)間。為比較不同算法的性能，采取了3個(gè)評(píng)價(jià)指標(biāo)，分別為：非支配率、收斂性和分布性，其詳細(xì)計(jì)算參考文獻(xiàn)[3]。一般來說，非支配率的值越大，則該算法獲得前沿解越好。收斂性越小，則算法收斂性越好。分布性越小，則算法獲得的前沿解的分布性更好。

4.1 算法參數(shù)校驗(yàn)

所提出的算法采用多因素方差分析（ANOVA）進(jìn)行參數(shù)校驗(yàn)。初始溫度T0設(shè)置兩個(gè)水平，即0.5和1；冷卻系數(shù)設(shè)置3個(gè)水平，即0.9，0.95和0.98；每個(gè)溫度下的迭代次數(shù)NS設(shè)置3個(gè)水平，即500，1000和2000；重啟機(jī)制的促發(fā)次數(shù)dn設(shè)置為3個(gè)水平，即100，200和300.方差分析的結(jié)果，如表1所示。由可知α，NS和dn對(duì)應(yīng)的P值均小于0.01，即存在顯著性差異。按照P值遞增的順序依次選擇每個(gè)參數(shù)的最優(yōu)水平，滿足95%最小顯著差數(shù)間隔的置信水平的冷卻系數(shù)各個(gè)取值，如圖6所示。

表1 關(guān)于收斂性的多因素方差分析表Tab.1 VNOVA Results for Convergence

圖6 冷卻系數(shù)平均值Fig.6 Mean Plot for Cooling Rate

4.2 算法性能對(duì)比

為驗(yàn)證重啟模擬退火算法的性能，重啟模擬退火算法和快速非支配排序遺傳算法分別對(duì)7組案例進(jìn)行10次求解，算法的終止條件統(tǒng)一設(shè)定為運(yùn)行時(shí)間t=nt×nt×10ms。算法的平均結(jié)果，如表2所示。由表2可知，針對(duì)非支配率，重啟模擬退火算法在總共39個(gè)案例上優(yōu)于快速非支配排序遺傳算法。針對(duì)收斂性，重啟模擬退火算法有36個(gè)案例都優(yōu)于快速非支配排序遺傳算法；針對(duì)分布性，重啟模擬退火算法有34個(gè)案例優(yōu)于快速非支配排序遺傳算法。針對(duì)所有的大規(guī)模案例，P65，P148和P205，重啟模擬退火算法在所有案例上均優(yōu)于快速非支配排序遺傳算法。

表2 算法的平均結(jié)果對(duì)比Tab.2 Comparison Results for Average Results

5 結(jié)語

針對(duì)雙邊裝配線的員工分配和平衡問題，設(shè)計(jì)了最小化成本和最大化負(fù)載均衡兩個(gè)目標(biāo)，建立相關(guān)的多目標(biāo)的優(yōu)化模型。為求解以上NP難題，提出了一種重啟模擬退火算法。在算法實(shí)踐中，針對(duì)員工分配和平衡問題，分別設(shè)計(jì)了有效的鄰域結(jié)構(gòu)。為避免陷入局部最優(yōu)，基于改進(jìn)聚集距離提出了重啟機(jī)制，以獲得分布性更廣的前沿解。為驗(yàn)證重啟模擬退火算法的性能，生成了7組案例，并與快速非支配排序遺傳算法的性能進(jìn)行對(duì)比。試驗(yàn)結(jié)果表明，所提出的算法在收斂性和分布性上均優(yōu)于快速非支配排序遺傳算法。下一步研究可將重啟模擬退火算法應(yīng)用于其他多目標(biāo)優(yōu)化問題。

［1］J.J.Bartholdi.Balancing two-sided assembly lines：A case study［J］.The International Journal of Production Research，1993，31（10）：2447-2461.

［2］D.Khorasanian，S.R.Hejazi，G.Moslehi.Two-sided assembly line balancing considering the relationships between tasks［J］.Computers&Industrial Engineering，2013，66（4）：1096-1105.

［3］李大雙，張超勇，邵新宇.基于多目標(biāo)殖民競(jìng)爭(zhēng)算法的隨機(jī)型雙邊裝配線［J］.計(jì)算機(jī)集成制造系統(tǒng)，2014，20（11）：2774-2787.（Li Da-shuang，Zhang Chao-yong，Shao Xin-yu.Balancing stochastic twosided assembly line with multi-objective colonial competitive algorithm［J］.Computer Integrated Manufacturing Systems，2014，20（11）：2774-2787.）

［4］Y.K.KIM，W.S.SONG，J.H.KIM.A mathematical model and a genetic algorithm for two-sided assembly line balancing［J］.Computers&Operations Research，2009，36（3）：853-865.

［5］鄭巧仙，李明，李元香.求解雙邊裝配線平衡問題的改進(jìn)蟻群算法［J］.電子學(xué)報(bào)，2014，42（5）：841-845.（Zheng Qiao-xian，Li Ming，Li Yuan-xiang.An improved ant colony optimization for two-sided assembly line balancing problem［J］.Acta Electronica Sinica，2014，42（5）：841-845.）

［6］李梓響，唐秋華，林斌.第二類雙邊裝配線平衡的混合粒子群算法［J］.機(jī)械設(shè)計(jì)與制造，2015（1）：113-116.（Li Zi-xiang，Tang Qiu-hua，Lin Bin.A hybrid particle swarm optimization for two-sided assembly line balancing problem of type II［J］.Machinery Design&Manufacture，2015（1）：113-116.）

［7］P.Th.Zacharia，Andreas C.Nearchou.A population-based algorithm for the bi-objective assembly line worker assignment and balancing problem［J］.Engineering Applications of Artificial Intelligence，2016（49）：1-9.

［8］A.Roshani，P.Fattahi，A.Roshani，M.Salehi，A.Roshani.cost-oriented twosided assembly line balancing problem：a simulated annealing approach［J］.International Journal of Computer Integrated Manufacturing，2012，25（8）：689-715.

［9］S.Kulturel-Konak，A.E.Smith，B.A.Norman.Multi-objective tabu search using a multinomial probability mass function［J］.European Journal of Operational Research，2006，169（3）：918-931.

［10］K.Deb，A.Pratap，S.Agarwal，T.Meyarivan.A fast and elitist multiobjective genetic algorithm：NSGA-II［J］.IEEE Transactions Evolutionary Computation，2002，6（2）：182-197.