魯建廈，朱 愷，董巧英

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014)

基于混合混沌粒子群算法的裝配線(xiàn)平衡問(wèn)題研究

魯建廈，朱 愷，董巧英

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014)

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

裝配線(xiàn)平衡；融合優(yōu)化；模擬退火；混沌；粒子群算法

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

1 裝配線(xiàn)平衡模型構(gòu)建

裝配線(xiàn)平衡問(wèn)題的定義為：裝配生產(chǎn)線(xiàn)上，被加工對(duì)象依序沿裝配線(xiàn)流動(dòng)，在滿(mǎn)足各作業(yè)元素裝配生產(chǎn)優(yōu)先順序的約束前提下，合理優(yōu)化分配各作業(yè)元素至一定數(shù)量的線(xiàn)上工作站，確保各工作站的作業(yè)時(shí)間總和基本相近且不超過(guò)生產(chǎn)節(jié)拍，盡可能減少工人與機(jī)器停頓等待現(xiàn)象的出現(xiàn)，實(shí)現(xiàn)生產(chǎn)目標(biāo)的最優(yōu)化[7].根據(jù)優(yōu)化目標(biāo)的區(qū)別，裝配線(xiàn)平衡問(wèn)題通常分為三類(lèi)：1) ALBP-I型：已知裝配線(xiàn)的生產(chǎn)節(jié)拍，求最小化的工作站總數(shù)；2) ALBP-II型：已知裝配線(xiàn)的工作站總數(shù)，求裝配線(xiàn)生產(chǎn)節(jié)拍的最小化；3) ALBP-III型：已知裝配線(xiàn)的生產(chǎn)節(jié)拍和工作站總數(shù)，求裝配線(xiàn)平滑指數(shù)的最小化.

在平衡優(yōu)化過(guò)程中，企業(yè)既對(duì)裝配線(xiàn)的平衡率非常看重，平衡率越高則表明整條裝配線(xiàn)的效率更好；又對(duì)裝配線(xiàn)的平滑指數(shù)密切關(guān)注，平滑指數(shù)越小則表明裝配線(xiàn)上各工作站彼此間的工作負(fù)荷更為均衡，裝配線(xiàn)整體平衡性更佳.因此，采用目標(biāo)加權(quán)平均的方法同時(shí)考慮裝配線(xiàn)平衡率和平滑指數(shù)，以融合優(yōu)化的思維來(lái)解決裝配線(xiàn)平衡優(yōu)化問(wèn)題.在裝配線(xiàn)工作站總數(shù)給定的前提下，將裝配線(xiàn)平衡率與平滑指數(shù)融合為新的最優(yōu)化目標(biāo)函數(shù)，其數(shù)學(xué)描述如下所述：

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

2) 目標(biāo)函數(shù).裝配線(xiàn)平衡率最大化，即裝配線(xiàn)上總的空閑時(shí)間最短，裝配線(xiàn)生產(chǎn)效率更高，函數(shù)表達(dá)為

(1)

式中：M為工作站總數(shù)；N為裝配線(xiàn)上所有作業(yè)元素的總數(shù)；CT為裝配線(xiàn)的生產(chǎn)節(jié)拍；ti為裝配線(xiàn)上第i個(gè)作業(yè)元素的作業(yè)時(shí)間.

裝配線(xiàn)平滑指數(shù)最小化，即裝配線(xiàn)上各工作站彼此間的工作負(fù)荷更為均衡，整體平衡性更佳，函數(shù)表達(dá)為

(2)

式中Tk為裝配線(xiàn)上第k個(gè)工作站的作業(yè)時(shí)間.

總的目標(biāo)函數(shù)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分別為裝配線(xiàn)上工作站a和工作站b上所分配到的作業(yè)元素集合；S為裝配線(xiàn)所有工作站上的作業(yè)元素集合；Pij=1表示i是j的緊前作業(yè)元素；i∈Sk(k=1,2,…,M)表示作業(yè)元素i在工作站k上完成.式(3)為裝配線(xiàn)平衡優(yōu)化的目標(biāo)函數(shù)，由裝配線(xiàn)平衡率和裝配線(xiàn)平滑指數(shù)兩部分共同組成；式(4)表示每一個(gè)作業(yè)元素只能分配至一個(gè)確定的工作站上；式(5)表示所有作業(yè)元素都將分配至裝配線(xiàn)上的工作站；式(6)表示裝配線(xiàn)的生產(chǎn)節(jié)拍不小于任意工作站時(shí)間；式(7)表示任一作業(yè)元素的分配都必須符合作業(yè)優(yōu)先關(guān)系.

2 混合混沌粒子群算法設(shè)計(jì)

作為典型的NP組合優(yōu)化問(wèn)題，當(dāng)前求解裝配線(xiàn)平衡模型的算法主要有：遺傳算法、模擬退火算法、蟻群算法、粒子群算法等，各類(lèi)算法各具特點(diǎn)，但也都存在著各自的不足之處.粒子群算法具有概念簡(jiǎn)單，設(shè)定參數(shù)較少，便于實(shí)現(xiàn)等特點(diǎn)，但在尋優(yōu)過(guò)程中也易發(fā)生“早熟”現(xiàn)象，陷入局部最優(yōu)[8].因此，將模擬退火算法與混沌思想引入標(biāo)準(zhǔn)粒子群算法中，以三者融合后的混合混沌粒子群算法來(lái)求解裝配線(xiàn)平衡模型.

基于NFL(No free lunch，簡(jiǎn)稱(chēng)NFL)定理，并不存在某一種算法面對(duì)所有求解問(wèn)題都是最有效的，任何算法都有其所適宜的應(yīng)用領(lǐng)域[9].因此，通過(guò)算法的混合來(lái)實(shí)現(xiàn)其適應(yīng)域與優(yōu)化性能的改善提升成為了較為有效的一種手段.考慮到裝配線(xiàn)平衡問(wèn)題及所建立的融合優(yōu)化多目標(biāo)函數(shù)模型的復(fù)雜性，以及粒子群算法所存在的不足與缺陷，故采用混合算法來(lái)進(jìn)行問(wèn)題的求解.

2.1 基本粒子群算法

粒子群算法(Particle swarm optimization，簡(jiǎn)稱(chēng)PSO)從本質(zhì)上來(lái)說(shuō)是一種基于仿生的迭代算法，通過(guò)運(yùn)算過(guò)程中的反復(fù)迭代來(lái)尋求問(wèn)題的最優(yōu)解[10].粒子在每一次尋優(yōu)迭代過(guò)程中通過(guò)比較兩個(gè)“極值”來(lái)更新自身的速度與位置.個(gè)體極值為粒子自身當(dāng)前尋找到的最優(yōu)位置，其可以看作粒子自身的尋優(yōu)經(jīng)驗(yàn)；全局極值為整個(gè)群體當(dāng)前尋找到的最優(yōu)位置，其可以看作粒子種群的尋優(yōu)經(jīng)驗(yàn).

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

(8)

(9)

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

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

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

2.3 裝配線(xiàn)平衡模型與算法的映射

裝配線(xiàn)平衡問(wèn)題為離散型的組合優(yōu)化問(wèn)題[12]，而H-CPSO算法不能直接運(yùn)用于求解離散空間的組合優(yōu)化問(wèn)題，因此需要對(duì)混合算法以及平衡問(wèn)題模型中的相關(guān)元素進(jìn)行對(duì)應(yīng)[13].求解空間中，每一個(gè)可行的作業(yè)序列定義為一個(gè)粒子，粒子的總數(shù)即種群規(guī)模，所有可行的作業(yè)序列集合構(gòu)成了整個(gè)粒子群[14].

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

2)粒子位置.粒子的位置對(duì)應(yīng)于裝配線(xiàn)上的一個(gè)作業(yè)序列，xi(k)為第i個(gè)粒子在第k次迭代時(shí)的位置.

3)粒子的適應(yīng)度函數(shù).多目標(biāo)平衡模型以裝配線(xiàn)平衡率與平滑指數(shù)為最優(yōu)化目標(biāo)，故適應(yīng)度函數(shù)對(duì)應(yīng)為給定工作站總數(shù)M的函數(shù)F，其表達(dá)為

(10)

2.4 求解裝配線(xiàn)平衡模型的混合算法設(shè)計(jì)

1)編碼與解碼.為了將離散的編碼序列與連續(xù)的粒子位置迭代進(jìn)化相對(duì)應(yīng)起來(lái)，選用隨機(jī)數(shù)表示法來(lái)對(duì)粒子進(jìn)行編碼.其編碼及解碼的工作流程所述如下：

編碼規(guī)則：采用隨機(jī)數(shù)表示法對(duì)粒子進(jìn)行編碼.

編碼過(guò)程：首先，對(duì)粒子的每一維度隨機(jī)生成一組介于0～1之間的隨機(jī)數(shù)，隨機(jī)數(shù)的大小即為對(duì)應(yīng)粒子的權(quán)重；然后，根據(jù)權(quán)重大小對(duì)粒子進(jìn)行排序，并依序進(jìn)行迭代計(jì)算.

解碼規(guī)則：粒子位置中的各作業(yè)元素依據(jù)權(quán)重大小分配至若干工作站[15]，解碼結(jié)果為輸出一個(gè)工作站劃分集合Dk={D1,D2,…,Dm}.

解碼過(guò)程：選定一個(gè)新的工作站k，將其作業(yè)時(shí)間置零；在滿(mǎn)足作業(yè)元素優(yōu)先關(guān)系的情況下，將排序后隨機(jī)數(shù)數(shù)值更大的作業(yè)元素i分配至工作站k，工作站k的作業(yè)時(shí)間Tk=∑ti，若Tk≤CT，則將作業(yè)元素i放置于工作站k內(nèi)，否則返回上一步驟；若當(dāng)前分配的作業(yè)元素為粒子位置中的最后一個(gè)作業(yè)元素，解碼結(jié)束，否則返回上一步驟.

2)種群初始化.為確保H-CPSO算法中粒子群種群生產(chǎn)的多樣性與合理性，綜合運(yùn)用隨機(jī)生成任務(wù)序列法與位置權(quán)重法來(lái)完成種群初始化，通過(guò)隨機(jī)選擇任務(wù)分配至任務(wù)排列序列，并優(yōu)先選擇權(quán)重?cái)?shù)值更大的任務(wù)[16].粒子群的生成以及粒子速度與位置的初始化計(jì)算式為

I={x10,x20,…,xm0}

(11)

(12)

(13)

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

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

(14)

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

ri(0)=random[0,1]

(15)

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

(16)

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

(17)

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

5)降溫速率.H-CPSO算法中的退火過(guò)程采用線(xiàn)性降溫方式，其計(jì)算式為

TPk+1=λ·TPk

(18)

3 計(jì)算實(shí)例

為了驗(yàn)證混合混沌粒子群算法對(duì)于裝配線(xiàn)平衡問(wèn)題的求解有效性，選用經(jīng)典實(shí)例庫(kù)中的MITCHELL問(wèn)題，分別采用標(biāo)準(zhǔn)粒子群算法與混合混沌粒子群算法進(jìn)行平衡模型求解，對(duì)比分析平衡優(yōu)化效果.

3.1 參數(shù)設(shè)定

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

圖2 MITCHELL問(wèn)題作業(yè)順序圖Fig.2 Task sequence diagram of problem MITCHELL

3.2 實(shí)例計(jì)算結(jié)果分析

在裝配線(xiàn)工作站數(shù)量分別為4～9個(gè)的6種情況下，求得采用標(biāo)準(zhǔn)粒子群算法與混合混沌粒子群算法的裝配線(xiàn)作業(yè)分配方案，求解結(jié)果對(duì)比見(jiàn)表1.

表1 MITCHELL問(wèn)題求解結(jié)果對(duì)比

從表1中可以看到：不論何種工作站數(shù)量下，混合混沌粒子群算法所對(duì)應(yīng)的目標(biāo)函數(shù)值均小于標(biāo)準(zhǔn)粒子群算法所對(duì)應(yīng)的目標(biāo)函數(shù)值，說(shuō)明混合算法對(duì)于裝配線(xiàn)的平衡優(yōu)化效果優(yōu)于標(biāo)準(zhǔn)粒子群算法，進(jìn)一步驗(yàn)證了混合混沌粒子群算法對(duì)于求解裝配線(xiàn)平衡問(wèn)題具有較為理想的效果.

4 結(jié) 論

針對(duì)裝配線(xiàn)平衡問(wèn)題，將衡量裝配線(xiàn)是否最優(yōu)化的多項(xiàng)參考指標(biāo)進(jìn)行融合優(yōu)化，以裝配線(xiàn)平衡率與平滑指數(shù)最優(yōu)化為目標(biāo)函數(shù)建立多目標(biāo)裝配線(xiàn)平衡模型.在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上，利用混沌所特有的遍歷性、隨機(jī)性以及規(guī)律性和模擬退火算法的全局尋優(yōu)特點(diǎn)，設(shè)計(jì)三者相融合的混合混沌粒子群算法；并運(yùn)用混合算法求解裝配線(xiàn)的平衡優(yōu)化模型.計(jì)算實(shí)例結(jié)果表明，所設(shè)計(jì)的混合混沌粒子群算法對(duì)比標(biāo)準(zhǔn)粒子群算法具有更佳的全局尋優(yōu)能力，效率與可靠性進(jìn)一步提升，對(duì)于裝配線(xiàn)平衡問(wèn)題具有較好的求解效果.

[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] 彭慧，徐克林，侶占華，等.采用遺傳算法的混流裝配線(xiàn)平衡多目標(biāo)優(yōu)化[J].現(xiàn)代制造工程，2011(11)：49-53.

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

[6] 李明，張則強(qiáng)，劉濟(jì)洲，等.變異粒子群算法在裝配線(xiàn)平衡問(wèn)題中的應(yīng)用[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2014，16(10)：27-33.

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

[8] 劉海江，湯偉，張含葉，等.基于改進(jìn)粒子群算法求解第二類(lèi)裝配線(xiàn)平衡問(wèn)題[J].中國(guó)工程機(jī)械學(xué)報(bào)，2014，12(6)：508-513.

[9] 陳志楊，劉妍.改進(jìn)粒子群搜索的二維皮革排樣優(yōu)化算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2015，43(5)：492-496.

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

[11] 張則強(qiáng)，余慶良，胡俊逸，等.隨機(jī)混流裝配線(xiàn)平衡問(wèn)題的一種混合粒子群算法[J].機(jī)械設(shè)計(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.

(責(zé)任編輯：劉 巖)

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—)，男，浙江余姚人，教授，博士生導(dǎo)師，研究方向?yàn)榫嫔a(chǎn)、生產(chǎn)調(diào)度和制造業(yè)信息化，E-mail：ljs@zjut.edu.cn.

TB491

A

1006-4303(2017)01-0114-05