任務(wù)分區(qū)及工位約束下裝配線第二類平衡研究

徐立云， 蔡炳杰， 曲寶升， 李愛平

(同濟(jì)大學(xué) 現(xiàn)代制造技術(shù)研究所，上海 201804)

?

任務(wù)分區(qū)及工位約束下裝配線第二類平衡研究

徐立云， 蔡炳杰， 曲寶升， 李愛平

(同濟(jì)大學(xué) 現(xiàn)代制造技術(shù)研究所，上海 201804)

裝配線平衡直接影響產(chǎn)品產(chǎn)量，也是在裝配線布局初始或重構(gòu)時(shí)所必須面臨的問題.針對(duì)第二類裝配線平衡問題(ALBP-2)，構(gòu)建了一種考慮優(yōu)先關(guān)系約束、任務(wù)分區(qū)約束和工位約束的多目標(biāo)優(yōu)化模型.為提高模型求解效率，采用逐步縮小節(jié)拍搜索范圍的動(dòng)態(tài)步長方法，提出基于自動(dòng)機(jī)回溯算法的改進(jìn)粒子群算法，提高了任務(wù)分配合理性，快速搜索出具有最小節(jié)拍和負(fù)載平滑系數(shù)的任務(wù)分配方案.引入任務(wù)分配矩陣表示每個(gè)工位上的任務(wù)分配情況，使結(jié)果描述更加明確.通過案例分析驗(yàn)證了所提模型和方法的有效性.

第二類裝配線平衡問題； 粒子群算法； 多目標(biāo)優(yōu)化； 任務(wù)分區(qū)約束； 工位約束

裝配是指將若干零部件結(jié)合成產(chǎn)品的過程，是汽車、電器等制造行業(yè)生產(chǎn)產(chǎn)品的核心環(huán)節(jié).規(guī)模生產(chǎn)中常見的裝配線是將裝配過程分解成若干個(gè)任務(wù)，并將這些任務(wù)分配到不同的工位上執(zhí)行的一種表現(xiàn)形式.裝配線平衡問題(ALBP)是裝配線設(shè)計(jì)布局的重要問題之一.根據(jù)優(yōu)化目標(biāo)不同，裝配線平衡問題可以分為兩類：在生產(chǎn)節(jié)拍與加工任務(wù)已知下，求最小工位數(shù)量的第一類裝配線平衡問題(ALBP-1)；在工位數(shù)與加工任務(wù)已知下，求最小節(jié)拍的第二類裝配線平衡問題(ALBP-2)[1].針對(duì)ALBP-2，國內(nèi)外很多學(xué)者進(jìn)行了深入的研究，主要研究方向?yàn)樗惴ǜ倪M(jìn)與模型優(yōu)化.對(duì)于算法改進(jìn)，大量學(xué)者將蟻群算法、粒子群算法、混合粒子群算法等智能算法及規(guī)則算法應(yīng)用到了ALBP-2上[1-5].在模型優(yōu)化方面，周亮[6]通過減少一組約束以改進(jìn)ALBP-2數(shù)學(xué)模型.Hamta等[7]研究了涉及最小節(jié)拍、最小設(shè)備成本及最小平滑系數(shù)的多目標(biāo)第二類裝配線平衡問題.Saif等[8]解決了任務(wù)操作時(shí)間不確定的第二類裝配線平衡問題.吳爾飛[9]提出了雙邊裝配線第二類平衡問題的數(shù)學(xué)模型，在模型中不僅考慮單邊裝配線存在的優(yōu)先關(guān)系約束，而且還考慮任務(wù)操作方位以及雙邊并行作業(yè)的要求.錢雄文[10]提出了多人共站裝配線第二類平衡問題，并通過實(shí)例驗(yàn)證了算法的可行性.

文獻(xiàn)[6-10]針對(duì)ALBP-2所構(gòu)建的數(shù)學(xué)優(yōu)化模型很好地解決了相應(yīng)的案例問題，但是對(duì)于更加普遍的問題，模型則沒有很好地表示工位和任務(wù)的約束.并且由于約束的表示又是建模過程中的重難點(diǎn)，因此對(duì)ALBP-2中的約束問題進(jìn)行研究有重要意義.為深入探討ALBP-2的約束問題，本文以單品種單邊裝配線平衡為問題背景，構(gòu)建多約束、多目標(biāo)優(yōu)化模型，采用逐步縮小節(jié)拍搜索范圍的動(dòng)態(tài)步長方法及基于自動(dòng)機(jī)回溯算法的改進(jìn)粒子群算法，使裝配線達(dá)到平衡，且得到更加符合實(shí)際情況的任務(wù)分配結(jié)果.在結(jié)果描述方面，采用任務(wù)分配矩陣以表示每個(gè)工位上的任務(wù)分配情況.最后，通過實(shí)例分析，驗(yàn)證了模型及方法的有效性.

1　問題描述及數(shù)學(xué)模型

1.1問題描述及相關(guān)假設(shè)

單品種單邊裝配線是最普遍的裝配線之一，該類裝配線除了考慮典型的優(yōu)先關(guān)系約束外，還會(huì)存在如下約束：①任務(wù)分區(qū)約束(task zoning constraints)，出于設(shè)備、工藝與安全性考慮，部分工位只能接受特定的一些任務(wù)；②工位約束(workstation related constraints)，某些任務(wù)由于任務(wù)性質(zhì)只能分配到特定工位.針對(duì)該類裝配線，以往研究在數(shù)學(xué)模型構(gòu)建過程中往往忽略實(shí)際工作過程中的部分約束，如文獻(xiàn)[10]只考慮到優(yōu)先關(guān)系約束，使得結(jié)果與實(shí)際情況有一定差距.

本文在同時(shí)考慮優(yōu)先關(guān)系約束、任務(wù)分區(qū)約束及工位約束的情況下，建立ALBP-2優(yōu)化模型.假設(shè)：①每個(gè)任務(wù)都有穩(wěn)定的任務(wù)時(shí)間；②必須將所有任務(wù)都分配到工位中；③工位個(gè)數(shù)是確定的；④每個(gè)任務(wù)都已經(jīng)是最小任務(wù)單元，不能劃分；⑤任務(wù)的分配不能違反優(yōu)先關(guān)系約束、任務(wù)分區(qū)約束及工位約束.因此，已知一個(gè)存在優(yōu)先關(guān)系約束、任務(wù)分區(qū)約束及工位約束的任務(wù)集，任務(wù)個(gè)數(shù)為n，工作數(shù)為m，在滿足約束的前提下，分配各任務(wù)使裝配線的節(jié)拍最小并使各工位的負(fù)荷盡可能相等.

1.2數(shù)學(xué)模型的建立

1.2.1變量定義

本文主要變量及其含義定義如下： I為任務(wù)矩陣，I=(1,2,…,n)為行向量，由所有任務(wù)序號(hào)構(gòu)成； I1,I2為子任務(wù)矩陣，I1，I2均由I部分元素構(gòu)成；t(i)為任務(wù)i的操作時(shí)間，i為I內(nèi)元素；P為優(yōu)先關(guān)系矩陣，P=(Pi1,i2)n×n,如果任務(wù)i1是任務(wù)i2的優(yōu)先任務(wù)，Pi1,i2=1，否則為0；J為工位矩陣，J=(1,2,…,m)，由所有I位序號(hào)構(gòu)成；CT為裝配線的節(jié)拍；B為裝配線的平衡率；ST(j)為工位j的裝配時(shí)間，j為J內(nèi)元素；n為任務(wù)數(shù)；m為工位數(shù).

1.2.2任務(wù)分配矩陣

為了描述任務(wù)在各工位的分配情況，引入任務(wù)分配矩陣

(1)

式中：Seq的每一行非零元素代表該工位上分配到的任務(wù)序號(hào).該矩陣有如下特點(diǎn)：①行最簡(jiǎn)且行滿秩矩陣；②非零元素值為1到n，且彼此不重復(fù). 其中①，②分別保證了所有工位分配到了任務(wù)以及任務(wù)的惟一性.

圖1為某Seq矩陣示意圖，代表含義如表1所示.

圖1　任務(wù)分配矩陣示意圖Fig.1　Task allocation matrix表1　任務(wù)在工位上的分配結(jié)果Tab.1　Allocation results of tasks in stations

工位序號(hào)1234567任務(wù)序號(hào){2}{1}{4,5}{6}{7,3}{8}{9,10,11}

1.2.3任務(wù)分配時(shí)間矩陣

為了描述各工位用時(shí),定義任務(wù)分配時(shí)間矩陣為

(2)

矩陣中的元素滿足

(3)

則第j號(hào)工位用時(shí)

(4)

裝配線節(jié)拍為各工位裝配的最長用時(shí)

(5)

1.2.4ALBP-2數(shù)學(xué)模型

決策變量：xij, 0-1變量，當(dāng)任務(wù)元素i被分配至第j工位時(shí)，xij=1, 否則xij=0.

(6)

ST(j)≤CT,j=1,2,…,m

(7)

(8)

Flength(Fintersect(Seq(j1,:),I1))+

Flength(Fintersect(Seq(j2,:),I1))+…+

Flength(Fintersect(Seq(jl,:),I1))=Flength(I1)，

l≤m

(9)

Flength(Fintersect(Seq(j,:),I2))=

Flength(Fintersect(Seq(j,:),I))

(10)

假設(shè)有A,B行向量，那么Fintersect(A,B)表示行向量A，B的交集元素所組成的行向量；Flength(A)表示行向量A的維數(shù)；Seq(j，：)表示由Seq中第j行元素構(gòu)成的行向量.

單品種單邊裝配線中，較小的節(jié)拍意味著更高的生產(chǎn)效率，較小的負(fù)載平滑系數(shù)意味著更少的設(shè)備閑置時(shí)間.構(gòu)建目標(biāo)函數(shù)如下:

主要目標(biāo)

Z1=minCT

(11)

次要目標(biāo)

(12)

式(6)保證同一任務(wù)只能分配到一個(gè)工位上；式(7)保證每個(gè)工位用時(shí)不超過節(jié)拍；式(8)保證不能違反任務(wù)優(yōu)先關(guān)系；式(9)是工位約束，保證子任務(wù)集I1中的每個(gè)任務(wù)必須分配到工位j1或j2,…,或jl；式(10)是任務(wù)分區(qū)約束，保證工位j上僅能分配到子任務(wù)集I2中的任務(wù).

2　求解思路與算法設(shè)計(jì)

2.1求解思路

針對(duì)上文中所構(gòu)建的模型，論文基于動(dòng)態(tài)步長及改進(jìn)粒子群算法進(jìn)行問題求解.采用動(dòng)態(tài)步長方法是為了提高算法效率.通過粒子群算法，雖然能夠產(chǎn)生不同的分配方案，但這些方案本身卻有很大的局限性：任務(wù)只是單向地流向工位，各個(gè)工位間無法實(shí)現(xiàn)任務(wù)的相互流通.因此，基于自動(dòng)機(jī)回溯算法對(duì)各個(gè)方案進(jìn)行回溯調(diào)整，盡可能使各工位負(fù)載趨于相同.具體步驟如下：①定界——由已知條件確定最優(yōu)節(jié)拍的大致所在范圍，同時(shí)指定初步長.②分組——根據(jù)步長將該范圍區(qū)間進(jìn)行分段，得到幾個(gè)區(qū)間端點(diǎn)節(jié)拍.③基于自動(dòng)機(jī)回溯算法的改進(jìn)粒子群算法計(jì)算——從小到大逐個(gè)取步驟②中得到的節(jié)拍，分別進(jìn)行以負(fù)載平滑系數(shù)為適應(yīng)度的改進(jìn)PSO算法計(jì)算，得到指定節(jié)拍下的最優(yōu)負(fù)載平滑系數(shù)及所對(duì)應(yīng)的任務(wù)分配矩陣.④當(dāng)前組最優(yōu)保留——節(jié)拍最小是主要優(yōu)化目標(biāo)，但節(jié)拍過小將無法獲得合理的任務(wù)分配矩陣.所以，當(dāng)節(jié)拍從小到大搜索時(shí)，首次得到合理的任務(wù)分配矩陣對(duì)應(yīng)的節(jié)拍就是當(dāng)前組的最優(yōu)節(jié)拍，進(jìn)而計(jì)算得到的最優(yōu)負(fù)載平滑系數(shù)與對(duì)應(yīng)任務(wù)分配矩陣為該組最佳.⑤縮小搜索空間——以步驟④中得到的最優(yōu)節(jié)拍值為區(qū)間中點(diǎn)，以現(xiàn)有步長為區(qū)間半徑，確定新的最優(yōu)節(jié)拍所在區(qū)間.然后縮短步長，進(jìn)入步驟②開始新一組的搜索.⑥選優(yōu)及結(jié)果輸出—— 循環(huán)達(dá)到終止步長時(shí)，取節(jié)拍最小的那一組為最優(yōu)結(jié)果.同時(shí)輸出該節(jié)拍下計(jì)算得到的任務(wù)分配矩陣.

2.2算法設(shè)計(jì)

2.2.1動(dòng)態(tài)步長算法

本文在求解過程中，采用逐步縮小節(jié)拍搜索范圍的動(dòng)態(tài)步長方法來提高整體算法效率，原理如圖2所示，具體表現(xiàn)如下：

圖2　動(dòng)態(tài)步長原理Fig.2　Theory of dynamic step

(1) 定界確定節(jié)拍變動(dòng)范圍.CT,min由式(13)求得.CT,max取帶有絕對(duì)冗余量的設(shè)定節(jié)拍.

(13)

(2) 參數(shù)初始化動(dòng)態(tài)步長方法中有3個(gè)較為重要的參數(shù)α，β，dt，它們分別表示初始步長，控制精度因子及當(dāng)前步長.

(3) 進(jìn)入計(jì)算主體

(14)

(15)

(16)

式(15)中，針對(duì)CT,l應(yīng)用1.2.4中提出的模型求解Δl及Seq,l的過程是利用改進(jìn)PSO算法進(jìn)行求解的環(huán)節(jié).Δl,Seq,l分別為CT,l對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值與最優(yōu)任務(wù)分配矩陣.CT從小到大搜索一直達(dá)到CT,j時(shí)，在該次搜索內(nèi)首次產(chǎn)生合理任務(wù)分配矩陣，從而完成該種群的改進(jìn)PSO算法運(yùn)算，得到該種群最佳的任務(wù)分配矩陣Seq,j與對(duì)應(yīng)的適應(yīng)度函數(shù)值Δj.

(17)

依據(jù)式(17)計(jì)算后縮小了最優(yōu)節(jié)拍所在范圍，然后直接結(jié)束該組的搜索.

(4) 縮短步長令dt=α/2 ，重復(fù)步驟(3)，得到第二組粒子群的各項(xiàng)最佳值：CT,j，Δj，Seq,j以及一個(gè)更精確CT,opt所在的范圍[CT,min,CT,max].

(5) 循環(huán)循環(huán)至終止步長dt=α/β，得到該組的CT,j，Δj，Seq,j.輸出最小節(jié)拍CT,opt=CT,j(由所有組中最小的CT,j來近似CT,opt)對(duì)應(yīng)分配方案為Seq,opt=Seq,j.

(6) 修正動(dòng)態(tài)步長取值是以非整數(shù)變化，故通過步驟(5)得到的CT,opt理論上會(huì)比真實(shí)值大，需要進(jìn)行修正.可采用步驟(5)中最后得到的任務(wù)分配矩陣Seq,opt來修正CT,opt，修正節(jié)拍為

(18)

2.2.2改進(jìn)PSO算法

(20)

式中：w為慣性權(quán)重；c1，c2為學(xué)習(xí)因子；r1，r2為[0,1]之間的隨機(jī)數(shù)；Pi=(Pi1,Pi2,…,PiD)，為個(gè)體極值；Pg=(Pg1,Pg2,…,PgD)，為全局極值.之后進(jìn)行迭代，循環(huán)至k=Maxgen(循環(huán)代數(shù)上限)，最后得到該種群下最優(yōu)目標(biāo)函數(shù)值Δl(Δl=gbest)與最優(yōu)任務(wù)分配矩陣Seq,l.

2.2.3初始任務(wù)分配矩陣的構(gòu)建

在完成對(duì)調(diào)后的任務(wù)排序矩陣b基礎(chǔ)上生成任務(wù)分配矩陣，即進(jìn)行任務(wù)的分配.該部分算法的核心思想是對(duì)任務(wù)排序矩陣b按指定節(jié)拍分段，然后逐段替代原始為零矩陣的任務(wù)分配矩陣中的元素.這個(gè)過程的目標(biāo)是生成滿足優(yōu)先關(guān)系約束且任務(wù)在指定節(jié)拍下能合理分配——不出現(xiàn)最后一個(gè)工位上沒任務(wù)或最后一個(gè)工位上按節(jié)拍要求分配后還有多余任務(wù)——的任務(wù)分配矩陣，對(duì)于不合格的粒子直接剔除.圖3為一個(gè)分配案例.

2.2.4自動(dòng)機(jī)回溯算法

自動(dòng)機(jī)回溯算法主要功能是對(duì)相鄰任務(wù)在相鄰工位間作嘗試性流動(dòng)，若能達(dá)到流動(dòng)后的任務(wù)分配方案滿足約束(9)和(10)，同時(shí)具有更好的負(fù)載平滑系數(shù)，則予以保留生成新的任務(wù)分配矩陣.否則，將任務(wù)分配矩陣恢復(fù)到任務(wù)流動(dòng)前的形式[12].這種算法使任務(wù)不斷地嘗試尋找更優(yōu)的流動(dòng)途徑，得到更優(yōu)的任務(wù)分配矩陣.算法遍歷方式是隨機(jī)的，即任意選擇兩個(gè)相鄰工位進(jìn)行任務(wù)的嘗試性流動(dòng)，同時(shí)設(shè)置循環(huán)次數(shù)上限值作為隨機(jī)遍歷的終止條件.

圖3　任務(wù)分配矩陣生成示意圖Fig.3　Formation of task allocation matrix

圖4示例中①和②是可行的流動(dòng)方案，序號(hào)1到11表示任務(wù)序號(hào)，矩形的長度表示任務(wù)操作時(shí)間.任務(wù)流動(dòng)調(diào)整的特點(diǎn)是在滿足優(yōu)先關(guān)系約束下，得到具有更高負(fù)載平滑系數(shù)的任務(wù)分配方案.圖5是圖4中相鄰任務(wù)在相鄰工位間流動(dòng)所對(duì)應(yīng)的任務(wù)分配矩陣的變化.任務(wù)分配矩陣與任務(wù)分配時(shí)間矩陣具有對(duì)應(yīng)關(guān)系，當(dāng)任務(wù)流動(dòng)后根據(jù)式(4)，(5)，(12)可得到新的負(fù)載平滑系數(shù).

圖4　任務(wù)回溯示意圖Fig.4　Task backtracking

圖5　任務(wù)分配矩陣中的任務(wù)流動(dòng)Fig.5　Task flow in task allocation matrix

3　案例分析

某裝配流水線共有7個(gè)工位，29個(gè)裝配任務(wù).裝配任務(wù)需要滿足表2中所示的先后次序，同時(shí)任務(wù)1，2只能分配到工位1或2上，任務(wù)8只能分配到工位3或4上.工位5只能接受任務(wù){(diào)2,3,4,6,8,10,11,12,13,14,15,16,17,18,20,21,22,24,25,26,29}，工位7上只能接受任務(wù){(diào)1,2,3,4,5,6,7,8,9,12,13,21,22, 23,23,24,25,26,27,28,11,29}.

在Win7 64位操作系統(tǒng)、8G內(nèi)存和Intel(R) Core(TM)2 Duo CPU E8400(3.00GHZ)環(huán)境下，在MATLAB 2013a中編寫相應(yīng)算法程序.算法中各參數(shù)設(shè)置如下：種群規(guī)模Sizepop=100，最大迭代次數(shù)Maxgen=200，慣性權(quán)重w=1，學(xué)習(xí)因子c1=1.5，c2=1.5.初步長α=1，控制精度因子β=50，遍歷循環(huán)次數(shù)上限Nc=50.

表2　某流水線任務(wù)操作時(shí)間及緊前任務(wù)Tab.2　Task operation time and immediate preceding task of an assembly line

算法中沒有采用精英保留策略，理論上組數(shù)越大，得到的最優(yōu)節(jié)拍越好，算法計(jì)算的組數(shù)為β=50.本文算法程序運(yùn)算時(shí)間為298 s.圖6表示組號(hào)與主要目標(biāo)-最優(yōu)節(jié)拍的關(guān)系.圖7表示組號(hào)與次要目標(biāo)-最優(yōu)負(fù)載平滑系數(shù)的關(guān)系，發(fā)現(xiàn)有多個(gè)組的縱坐標(biāo)相同，這反映了在諸多組中搜索出了相同的解，說明算法在一定程度上能避免解的丟失.圖8表示最優(yōu)節(jié)拍所對(duì)應(yīng)的收斂曲線，反映在節(jié)拍最小下，通過任務(wù)回溯與粒子迭代尋優(yōu)，最終獲得的各工位負(fù)載比較相近.表3表示裝配線任務(wù)分配結(jié)果.

通過計(jì)算可知，最優(yōu)節(jié)拍出現(xiàn)在第50組，理論最優(yōu)節(jié)拍CT,opt=48.005 7 s，對(duì)應(yīng)的負(fù)載平滑系數(shù)Z2=5.477 2 s，瓶頸工位為5號(hào)工位.最優(yōu)任務(wù)分配矩陣為

圖6　組號(hào)與最優(yōu)節(jié)拍的關(guān)系Fig.6　Group number vs optimum cycle time

圖7　組號(hào)與負(fù)載平滑系數(shù)的關(guān)系

Fig.7Group numbervswork-loading smoothness index

圖8　最優(yōu)組的適應(yīng)度迭代曲線Fig.8　Fitness iteration of optimum group

Seq=

根據(jù)式(18)，修正后最優(yōu)節(jié)拍為

min{48.0057,48}=48s

表3　裝配線任務(wù)分配結(jié)果Tab.3　Task allocation result of assembly line

裝配線平衡率為

100%≈96.43%

上述任務(wù)分配方案滿足企業(yè)的實(shí)際生產(chǎn)需求，這對(duì)于企業(yè)生產(chǎn)線裝配工藝規(guī)劃具有較好的指導(dǎo)和借鑒作用.

4　結(jié)語

本文針對(duì)ALBP-2，考慮了優(yōu)先關(guān)系約束、任務(wù)分區(qū)約束和工位約束，完成了優(yōu)化模型的建立，使模型更貼近實(shí)際.采用逐步縮小節(jié)拍搜索范圍的動(dòng)態(tài)步長方法，同時(shí)提出了一種基于自動(dòng)機(jī)回溯算法的改進(jìn)粒子群算法，提高任務(wù)分配合理性，快速搜索出具有最小節(jié)拍和負(fù)載平滑系數(shù)的ALBP-2任務(wù)分配方案.最后通過案例驗(yàn)證了所提模型及方法的有效性.

[1]魯建廈，蔣玲玲，李修琳. 基于混合粒子群算法求解裝配線第二類平衡問題[J].中國機(jī)械工程，2010(4):420.

LU Jiansha，JIANG Lingling，LI Xiulin. Hybrid particle swarm optimization algorithm for assembly line balancing Problem-2[J]. Chinese Journal of Mechanical Engineering，2010(4): 420.

[2]鄭巧仙.求解裝配線平衡問題的蟻群算法研究[D].武漢:武漢大學(xué)，2013.

ZHANG Qiaoxian. Research on ant colony algorithm for assembly line balancing[D]. Wuhan: Wuhan University，2013.

[3]李明，唐秋華，鄭巧仙，等. 第2類裝配線平衡問題的改進(jìn)規(guī)則組合算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2015(1): 88.

LI Ming，TANG Qiuhua，ZHENG Qiaoxian，etal. Improved rules combination algorithm of type 2 assembly line balancing problem[J]. Computer Integrated Manufacturing Systems，2015(1):88.

[4]Mutlu ?，Polat O，Supciller A A. An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II [J]. Computers & Operations Research, 2013，40: 418.

[5]Petropoulos D， Nearchou A C. A particle swarm optimization algorithm for balancing assembly lines [J]. Dimitris I Petropoulos and Andreas C Nearchou, 2011，31(2):118.

[6]周亮.裝配線平衡的最優(yōu)化模型與算法研究[D].南京:南京理工大學(xué)，2005.

ZHOU Liang. Study on assembly line balancing optimal models and algorithms [D]. Nanjing: Nanjing University of Science and Technology，2005.

[7]Hamta N，F(xiàn)atemiGhomi S M T，Jolai F，etal. A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect [J]. International Journal of Production Economics，2013，141: 99.

[8]Saif U，Guan Z，Liu W，etal. Pareto based artificial bee colony algorithm for multi objective single model assembly line balancing with uncertain task times[J]. Computers & Industrial Engineering，2014，76: 1.

[9]吳爾飛.雙邊裝配線平衡技術(shù)的研究[D].上海:上海交通大學(xué)，2009.

WU Erfei. Research on balancing two-sided assembly line[D]. Shanghai :Shanghai Jiaotong University，2009.

[10]錢雄文.多人共站裝配線平衡問題的研究與優(yōu)化[D].上海:上海交通大學(xué)，2012.

QIAN Xiongwen. Multi-manned assembly line balancing problem [D]. Shanghai :Shanghai Jiaotong University，2012.

[11]徐立云，徐昌飛，鄧偉，等.基于SA-PSO算法的發(fā)動(dòng)機(jī)缸體機(jī)加工線平衡研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014(2):16.

XU Liyun，XU Changfei，DENG Wei，etal. Machining line balancing of engine cylinder block based on SA-PSO algorithm [J]. Transactions of Chinese Society for Agriculture Machinery，2014(2): 16.

[12]王慈光.編組站動(dòng)態(tài)配流模型與算法研究[J].鐵道學(xué)報(bào)，2004，26(1):1.

WANG Ciguang. Research on the model and algorithm of dynamic wagon-flow allocating in a marshalling station [J]. Journal of the China Railway Society，2004，26(1):1.

Assembly Line Balancing Problem-2 with Task Zoning Constraints and Workstation Related Constraints

XU Liyun, CAI Bingjie, QU Baosheng, LI Aiping

(Institute of Advanced Manufacturing Technology, Tongji University, Shanghai 201804, China)

The balance of assembly line has a great effect on the output of products, and is also a problem to be dealt with at the phases of designing and reconfiguring. Aimed at the current assembly line balancing problem type-2(ALBP-2), a multi-objective model was proposed, taking task sequence constraints, task zoning constraints and workstation related constraints into account, to minimize cycle time and work-loading smoothness index. First, a dynamic step length method was applied, which gradually shrank the searching span of cycle time, to improve the efficiency of computing. Then, an improved PSO algorithm based on a Back Algorithm (BA) was introduced to promote the rationality of tasks-allocating. After that task allocation matrix was described to show details of task allocations in stations and clarify the result. Finally, a case was illustrated to prove the effectiveness of the proposed method.

assembly line balancing problem-2(ALBP-2); PSO algorithm; multi-objective optimization; task zoning constraints; workstation related constraints

2015-01-17

國家科技重大專項(xiàng)(2013ZX04012071)

徐立云(1973—)，男，教授，博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)橹悄苤圃?、系統(tǒng)建模與優(yōu)化、產(chǎn)品數(shù)字化設(shè)計(jì)與管理.

E-mail：Lyxu@#edu.cn

TB491

A