基于混合混沌粒子群算法的裝配線平衡問題研究

魯建廈，朱 愷，董巧英

(浙江工業大學 機械工程學院，浙江 杭州 310014)

基于混合混沌粒子群算法的裝配線平衡問題研究

魯建廈，朱 愷，董巧英

(浙江工業大學 機械工程學院，浙江 杭州 310014)

為了實現裝配線多目標最優化平衡，建立了以裝配線平衡率與平滑指數最優化為目標函數的多目標裝配線平衡模型.由于粒子群算法在求解時易發生“早熟”現象，陷入局部最優的缺陷，因此引入模擬退火算法與混沌思想，設計了一種三者相融合的混合混沌粒子群算法.算法借助混沌所具有的遍歷性、隨機性及規律性，對粒子速度的更新調整進行干預；利用模擬退火算法在一定范圍內以變化的概率接受較差解的特點，有效抑制“早熟”現象，實現對于裝配線的平衡優化，通過實例驗證了算法的有效性.

裝配線平衡；融合優化；模擬退火；混沌；粒子群算法

裝配線平衡問題(Assembly line balancing problem，簡稱ALBP)一直都是制造領域中極為重要的一項研究課題，其平衡與否將直接對企業的生產效率、生產成本、市場競爭力產生巨大影響.Bryton于1954年首次系統論述了裝配線平衡問題，并提出了一種“會聚過程法”來解決ALBP[1].Scholl等[2]采用分支定界法來高效尋找裝配線平衡的最優解，基于“局部下界”理念提高算法求解效率.Mcmullen等[3]采用模擬退火算法來解決帶有平行工作站的多目標的裝配線平衡問題.彭慧等[4]對混流裝配線第二類平衡問題展開研究，建立以加權平均負荷和生產節拍加權和的求解模型，并采用遺傳算法進行模型求解.劉煒琪等[5]提出一種改進的多目標粒子群算法來求解所建立的以最小化超載時間、總切換時間以及產品變化率為優化目標的模型.李明等[6]采用變異粒子群算法來求解ALBP，在標準粒子群算法的基礎上，對設定步長內位置沒有更新的個體采用多點變異的方法來提升種群的多樣性，并通過縱向進化與橫向搜索的機制，提升算法綜合搜索性能.實際生產過程中，多項衡量指標均會對裝配線的平衡與否產生影響，單一性的指標衡量無法準確做到真正意義上的最優化平衡.因此，需要考慮多目標衡量的裝配線平衡優化，研究以裝配線平衡率與平滑指數相融合來衡量裝配線的平衡優化程度.

1 裝配線平衡模型構建

裝配線平衡問題的定義為：裝配生產線上，被加工對象依序沿裝配線流動，在滿足各作業元素裝配生產優先順序的約束前提下，合理優化分配各作業元素至一定數量的線上工作站，確保各工作站的作業時間總和基本相近且不超過生產節拍，盡可能減少工人與機器停頓等待現象的出現，實現生產目標的最優化[7].根據優化目標的區別，裝配線平衡問題通常分為三類：1) ALBP-I型：已知裝配線的生產節拍，求最小化的工作站總數；2) ALBP-II型：已知裝配線的工作站總數，求裝配線生產節拍的最小化；3) ALBP-III型：已知裝配線的生產節拍和工作站總數，求裝配線平滑指數的最小化.

在平衡優化過程中，企業既對裝配線的平衡率非常看重，平衡率越高則表明整條裝配線的效率更好；又對裝配線的平滑指數密切關注，平滑指數越小則表明裝配線上各工作站彼此間的工作負荷更為均衡，裝配線整體平衡性更佳.因此，采用目標加權平均的方法同時考慮裝配線平衡率和平滑指數，以融合優化的思維來解決裝配線平衡優化問題.在裝配線工作站總數給定的前提下，將裝配線平衡率與平滑指數融合為新的最優化目標函數，其數學描述如下所述：

1) 平衡模型建立的條件假設.裝配線上只生產單一品種的一類產品；作業元素為最小且不可再分的作業單位，其作業時間為確定值；作業元素在滿足作業優先關系的前提下可被分配至任意工作站上，但任意作業元素都必須且只能分配至一個確定的工作站；作業元素的分配不受工作站約束，作業元素的作業時間不因工作站而不同；裝配線的生產節拍不小于任意工作站時間；裝配線上不存在并行工作站；裝配線上所有工作人員的技能水平不存在差異，可完成任意工作站上的裝配作業；不考慮生產過程中的空間、成本和資源等約束，忽略工作人員的行走路徑時間等.

2) 目標函數.裝配線平衡率最大化，即裝配線上總的空閑時間最短，裝配線生產效率更高，函數表達為

(1)

式中：M為工作站總數；N為裝配線上所有作業元素的總數；CT為裝配線的生產節拍；ti為裝配線上第i個作業元素的作業時間.

裝配線平滑指數最小化，即裝配線上各工作站彼此間的工作負荷更為均衡，整體平衡性更佳，函數表達為

(2)

式中Tk為裝配線上第k個工作站的作業時間.

總的目標函數F為

(3)

約束條件為

Sa∩Sb=Φ(a,b=1,2,…,M且a≠b)

(4)

(5)

Tk≤CTk=1,2,…,M

(6)

?i，如果Pij=1,i∈Sa,j∈Sb，則a≤b

(7)

式中：Sa，Sb分別為裝配線上工作站a和工作站b上所分配到的作業元素集合；S為裝配線所有工作站上的作業元素集合；Pij=1表示i是j的緊前作業元素；i∈Sk(k=1,2,…,M)表示作業元素i在工作站k上完成.式(3)為裝配線平衡優化的目標函數，由裝配線平衡率和裝配線平滑指數兩部分共同組成；式(4)表示每一個作業元素只能分配至一個確定的工作站上；式(5)表示所有作業元素都將分配至裝配線上的工作站；式(6)表示裝配線的生產節拍不小于任意工作站時間；式(7)表示任一作業元素的分配都必須符合作業優先關系.

2 混合混沌粒子群算法設計

作為典型的NP組合優化問題，當前求解裝配線平衡模型的算法主要有：遺傳算法、模擬退火算法、蟻群算法、粒子群算法等，各類算法各具特點，但也都存在著各自的不足之處.粒子群算法具有概念簡單，設定參數較少，便于實現等特點，但在尋優過程中也易發生“早熟”現象，陷入局部最優[8].因此，將模擬退火算法與混沌思想引入標準粒子群算法中，以三者融合后的混合混沌粒子群算法來求解裝配線平衡模型.

基于NFL(No free lunch，簡稱NFL)定理，并不存在某一種算法面對所有求解問題都是最有效的，任何算法都有其所適宜的應用領域[9].因此，通過算法的混合來實現其適應域與優化性能的改善提升成為了較為有效的一種手段.考慮到裝配線平衡問題及所建立的融合優化多目標函數模型的復雜性，以及粒子群算法所存在的不足與缺陷，故采用混合算法來進行問題的求解.

2.1 基本粒子群算法

粒子群算法(Particle swarm optimization，簡稱PSO)從本質上來說是一種基于仿生的迭代算法，通過運算過程中的反復迭代來尋求問題的最優解[10].粒子在每一次尋優迭代過程中通過比較兩個“極值”來更新自身的速度與位置.個體極值為粒子自身當前尋找到的最優位置，其可以看作粒子自身的尋優經驗；全局極值為整個群體當前尋找到的最優位置，其可以看作粒子種群的尋優經驗.

設一個包含M個粒子的粒子群在D維空間中飛行，粒子i在D維空間中的飛行速度與位置表示為

(8)

(9)

2.2 混合混沌粒子群算法描述

雖然粒子群算法在求解過程中具有多項優勢，但其對于算法的初始設值較為敏感及依賴，全局搜索效率較差，影響求解精度[11].因此提出將模擬退火算法與混沌思想引入粒子群算法中，借助混沌所具有的遍歷性、隨機性及規律性引入粒子速度的更新調整過程中，使系統表現出完全混沌特性；引入模擬退火算法，在一定范圍內以變化的概率接受較差解，使其能有效跳出局部最優并抑制“早熟”現象，并采用基于適應度函數值與接受概率的初始化方法對模擬退火算法中的重要影響參數溫度初始值進行初始化，進一步提升混合算法的搜索性能.融合后的混合混沌粒子群算法(Hybrid chaotic particle swarm optimization algorithm，簡稱H-CPSO)有效提升了算法求解的綜合優化性能，可將其應用于裝配線的平衡優化.圖1為混合混沌粒子群算法的求解流程圖.

圖1 混合混沌粒子群算法流程圖Fig.1 Hybrid chaotic particle swarm optimization algorithm flow chart

2.3 裝配線平衡模型與算法的映射

裝配線平衡問題為離散型的組合優化問題[12]，而H-CPSO算法不能直接運用于求解離散空間的組合優化問題，因此需要對混合算法以及平衡問題模型中的相關元素進行對應[13].求解空間中，每一個可行的作業序列定義為一個粒子，粒子的總數即種群規模，所有可行的作業序列集合構成了整個粒子群[14].

1)粒子速度.在n維解空間中，粒子速度vi=(v1,v2,…,vn)，粒子的初始速度由隨機確定產生，并依據引入混沌思想的速度更新公式進行迭代更新.

2)粒子位置.粒子的位置對應于裝配線上的一個作業序列，xi(k)為第i個粒子在第k次迭代時的位置.

3)粒子的適應度函數.多目標平衡模型以裝配線平衡率與平滑指數為最優化目標，故適應度函數對應為給定工作站總數M的函數F，其表達為

(10)

2.4 求解裝配線平衡模型的混合算法設計

1)編碼與解碼.為了將離散的編碼序列與連續的粒子位置迭代進化相對應起來，選用隨機數表示法來對粒子進行編碼.其編碼及解碼的工作流程所述如下：

編碼規則：采用隨機數表示法對粒子進行編碼.

編碼過程：首先，對粒子的每一維度隨機生成一組介于0～1之間的隨機數，隨機數的大小即為對應粒子的權重；然后，根據權重大小對粒子進行排序，并依序進行迭代計算.

解碼規則：粒子位置中的各作業元素依據權重大小分配至若干工作站[15]，解碼結果為輸出一個工作站劃分集合Dk={D1,D2,…,Dm}.

解碼過程：選定一個新的工作站k，將其作業時間置零；在滿足作業元素優先關系的情況下，將排序后隨機數數值更大的作業元素i分配至工作站k，工作站k的作業時間Tk=∑ti，若Tk≤CT，則將作業元素i放置于工作站k內，否則返回上一步驟；若當前分配的作業元素為粒子位置中的最后一個作業元素，解碼結束，否則返回上一步驟.

2)種群初始化.為確保H-CPSO算法中粒子群種群生產的多樣性與合理性，綜合運用隨機生成任務序列法與位置權重法來完成種群初始化，通過隨機選擇任務分配至任務排列序列，并優先選擇權重數值更大的任務[16].粒子群的生成以及粒子速度與位置的初始化計算式為

I={x10,x20,…,xm0}

(11)

(12)

(13)

3)初始溫度.初始溫度是混合混沌粒子群算法全局優化搜索性能的重要影響參數，依據初始粒子群中最大目標函數值f(xi(0))max與最小目標函數值f(xi(0))min的差值以及初始接受概率pτ，計算初始溫度TP0，其計算式為

TP0=(f(xi(0))min-f(xi(0))max)/lnpτ= -|Δf|/lnpτ

(14)

4)粒子的速度與位置更新.粒子速度與位置的更新，可在初始化速度與位置的基礎上，依據迭代公式進行更新.對于粒子速度的更新，可在確定初始參數ω，c1，c2的情況下，將粒子自身最優位置所對應的隨機數與當前位置所對應的隨機數相減，同理將粒子全局最優位置所對應的隨機數與當前位置所對應的隨機數相減，分別與c1r1和c2r2做乘積，計算式如式(8)所述；同時采用混沌思想中的Logistic模型對粒子速度更新公式中的r1和r2進行混沌優化，其計算式為

ri(0)=random[0,1]

(15)

ri1(k)=ri2(k)=ri(k)

(16)

ri(k+1)=4ri(k)·(1-ri(k))

(17)

對于粒子位置的更新，公式可表述為將粒子當前位置對應的隨機數與更新后速度所對應的隨機數相加，得到的即為粒子更新后的位置所對應的隨機數，其計算式如式(9)所述.

5)降溫速率.H-CPSO算法中的退火過程采用線性降溫方式，其計算式為

TPk+1=λ·TPk

(18)

3 計算實例

為了驗證混合混沌粒子群算法對于裝配線平衡問題的求解有效性，選用經典實例庫中的MITCHELL問題，分別采用標準粒子群算法與混合混沌粒子群算法進行平衡模型求解，對比分析平衡優化效果.

3.1 參數設定

MITCHELL問題的作業順序圖如圖2所示，分別求解裝配線工作站數量為4～9個的6種情況.根據前期測試經驗，綜合考慮混合算法的求解精度、搜索性能以及運算效率等因素，混合混沌粒子群算法的參數設定為：種群規模m=40；慣性權重ω=0.9；學習因子c1=c2=2；初始接受概率pτ=0.8；最大迭代次數Gmax=300；降溫速率λ=0.98.

圖2 MITCHELL問題作業順序圖Fig.2 Task sequence diagram of problem MITCHELL

3.2 實例計算結果分析

在裝配線工作站數量分別為4～9個的6種情況下，求得采用標準粒子群算法與混合混沌粒子群算法的裝配線作業分配方案，求解結果對比見表1.

表1 MITCHELL問題求解結果對比

從表1中可以看到：不論何種工作站數量下，混合混沌粒子群算法所對應的目標函數值均小于標準粒子群算法所對應的目標函數值，說明混合算法對于裝配線的平衡優化效果優于標準粒子群算法，進一步驗證了混合混沌粒子群算法對于求解裝配線平衡問題具有較為理想的效果.

4 結 論

針對裝配線平衡問題，將衡量裝配線是否最優化的多項參考指標進行融合優化，以裝配線平衡率與平滑指數最優化為目標函數建立多目標裝配線平衡模型.在標準粒子群算法的基礎上，利用混沌所特有的遍歷性、隨機性以及規律性和模擬退火算法的全局尋優特點，設計三者相融合的混合混沌粒子群算法；并運用混合算法求解裝配線的平衡優化模型.計算實例結果表明，所設計的混合混沌粒子群算法對比標準粒子群算法具有更佳的全局尋優能力，效率與可靠性進一步提升，對于裝配線平衡問題具有較好的求解效果.

[1] DRISCOLL J, THILAKAWARDANA D. The definition of assembly line balancing difficulty and evaluation of balancing solution quality[J]. Robotics and computer integrated manufacturing，2001，12(5)：81-86.

[2] SCHOLL A, KLEIN R. SALOME：a bi-direction branch-and-bound procedure for assembly line balancing[J]. Informs journal of computing，1997，9(4)：319-334.

[3] MCMULLEN P. R, FRAZIER G.V. Using simulated annealing to solve a multi objective assembly line balancing problem with parallel workstations[J]. International journal of production research，1998，36(10)：2717-2741.

[4] 彭慧，徐克林，侶占華，等.采用遺傳算法的混流裝配線平衡多目標優化[J].現代制造工程，2011(11)：49-53.

[5] 劉煒琪，劉瓊，張超勇，等.基于混合粒子群算法求解多目標混流裝配線排序[J].計算機集成制造系統，2011，17(12)：2590-2598.

[6] 李明，張則強，劉濟洲，等.變異粒子群算法在裝配線平衡問題中的應用[J].組合機床與自動化加工技術，2014，16(10)：27-33.

[7] 陳勇，章金紅，魯建廈，等.基于GA-TS混合算法的多裝配線調度建模[J].浙江工業大學學報，2013，41(4)：355-359.

[8] 劉海江，湯偉，張含葉，等.基于改進粒子群算法求解第二類裝配線平衡問題[J].中國工程機械學報，2014，12(6)：508-513.

[9] 陳志楊，劉妍.改進粒子群搜索的二維皮革排樣優化算法[J].浙江工業大學學報，2015，43(5)：492-496.

[10] 魯建廈，胡海芬，董巧英，等.基于博弈粒子群算法的混流混合車間調度研究[J].浙江工業大學學報，2015，43(4)：398-404.

[11] 張則強，余慶良，胡俊逸，等.隨機混流裝配線平衡問題的一種混合粒子群算法[J].機械設計與研究，2013，29(2)：60-63.

[12] MOHD F. R, WINDO H. A review on assembly sequence planning and assembly line balancing optimization using soft computing approaches[J]. The international journal of advanced manufacturing technology，2012，59(1)：335-349.

[13] SENER A，ADIL B. Modeling and solving mixed-model assembly line balancing problem with setups. Part I: a mixed integer linear programming model[J]. Journal of manufacturing systems，2014，33(1)：177-187.

[14] SENER A. Performance evaluation of ant colony optimization-based solution strategies on the mixed-model assembly line balancing problem[J]. Engineering optimization，2014，46(4/6)：842-862.

[15] ALENA O，CHRISTIAN O. How to design effective priority rules: example of simple assembly line balancing[J]. Computers & industrial engineering，2014，69：43-52.

[16] GEMA C，ALBERT C. Combining matheuristics and MILP to solve the accessibility windows assembly line balancing problem level 2 (AWALBP-L2)[J]. Computers & operations research，2014，48：113-123.

(責任編輯：劉 巖)

Research on assembly line balancing problem based on hybrid chaotic particle swarm optimization algorithm

LU Jiansha, ZHU Kai, DONG Qiaoying

(College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

In order to achieve the multi objective optimization of assembly line balancing, a multi objective assembly line balancing model was constructed with the objectives of maximization of assembly line balancing rate and minimization of smoothing index. The particle swarm optimization algorithm tends to be “premature” and falls into the local optimum. So the simulated annealing algorithm and chaos theory are introduced, a hybrid chaotic particle swarm optimization algorithm with three phase fusion was designed. The characteristics of ergodic, stochastic and regularity of chaos was used to intervene the particle velocity updating and adjustment. The simulated annealing algorithm was adopted to inhibit the “premature” phenomenon, an example was given to verify the model and algorithm, and the results prove the method is effective.

assembly line balancing; fusion optimization; simulated annealing; chaos; particle swarm optimization algorithm

2016-05-16

魯建廈(1963—)，男，浙江余姚人，教授，博士生導師，研究方向為精益生產、生產調度和制造業信息化，E-mail：ljs@zjut.edu.cn.

TB491

A

1006-4303(2017)01-0114-05