改進粒子群算法對鋼卷混流包裝線平衡問題的研究

王 強，張含葉，王 利

（1.九江學(xué)院 機械與材料工程學(xué)院，九江 332005；2.九江學(xué)院 教務(wù)處，九江 332005）

0 引言

鋼卷的品種和數(shù)量隨顧客需求的變化而變化，在最短的時間內(nèi)，應(yīng)該能最大限度地滿足不同客戶的個性化需求。鋼卷的混流包裝線能夠適應(yīng)多品種生產(chǎn)的需要，在基本不改變現(xiàn)有生產(chǎn)手段、生產(chǎn)條件和生產(chǎn)能力的前提下，通過改變生產(chǎn)組織方式，在一定的時間內(nèi)，在同一條包裝生產(chǎn)線上包裝出不同代碼的多品種鋼卷產(chǎn)品。因此，鋼卷混流包裝生產(chǎn)線能夠快速響應(yīng)市場需求的變化，節(jié)約流動資金，降低成本，提高產(chǎn)品的競爭力。

混流包裝生產(chǎn)線平衡問題屬于NP-Hard問題[1]，采用傳統(tǒng)的精確方法求解比較困難。隨著科技的發(fā)展，許多人工智能方法被用來求解混流裝配線平衡問題，例如：遺傳算法[2～7]、蜂群算法[8,9]、蟻群算法[10～14]、差分進化算法[15]等。本文采用改進粒子群算法對對混流鋼卷包裝線平衡問題進行研究。

1 問題描述

混流鋼卷包裝線平衡問題可以描述為：在計劃期內(nèi)，在同一包裝線上混合連續(xù)地包裝M種系列產(chǎn)品的鋼卷，這M種鋼卷結(jié)構(gòu)相似、工藝相近，每個品種鋼卷的包裝由若干任務(wù)組成，這些任務(wù)都有嚴格的順序要求，產(chǎn)品包裝中任務(wù)之間的關(guān)系可以用作業(yè)順序圖來描述。

圖1 裝配優(yōu)先關(guān)系圖

圖1為三種產(chǎn)品A、B和C的裝配優(yōu)先關(guān)系圖，因為不同品種產(chǎn)品的裝配優(yōu)先關(guān)系圖之間存在差異，所以在研究混流產(chǎn)品裝配線平衡問題時，常用的方法是將其合并為一個綜合裝配優(yōu)先關(guān)系圖，如圖2所示。

圖2 綜合裝配優(yōu)先關(guān)系圖

2 數(shù)學(xué)模型

2.1 變量定義

本文用到的變量及其含義如表1所示。

2.2 目標函數(shù)

其中：

w1和w2均為權(quán)重系數(shù)。

2.3 約束條件

其中，式(2)確保任一作業(yè)元素只能分配到某一工作站中；式(3)為裝配優(yōu)先關(guān)系約束；式(4)為節(jié)拍約束；式(5)表示變量的取值范圍。

表1 變量定義

3 算法設(shè)計

3.1 基本粒子群算法

在每一代，粒子Xα的速度和位置更新公式分別為：

式(6)中右邊第一項為粒子先前速度的繼承；第二項為“認知”部分，是一個增強學(xué)習(xí)過程；第三項為“社會”部分，表示粒子間的信息共享與相互合作。在搜索過程中粒子一方面記憶它們自己的經(jīng)驗，同時考慮其同伴的經(jīng)驗。當(dāng)單個粒子覺察同伴經(jīng)驗較好的時候，它將進行適應(yīng)性的調(diào)整，尋求一致認知過程。

3.2 改進粒子群算法

對式(6)進行改進，改進后的粒子群算法如下：

改進粒子群算法的流程如下：

Step 1：確定參數(shù)：種群規(guī)模PS、加速常數(shù)c1和c2、權(quán)重系數(shù)w1和w2、最大迭代次數(shù)Tmax；

Step 2：產(chǎn)生初始種群；

Step 3：根據(jù)式(1)和約束條件(2)～(5)，計算適應(yīng)度函數(shù)；

Step 5：判斷是否滿足終止條件（本文以迭代次數(shù)是否達到預(yù)設(shè)的代數(shù)Tmax作為終止條件），如果滿足，則進入Step 6；否則，轉(zhuǎn)入Step 2；

Step 6：輸出最優(yōu)解，算法結(jié)束。

4 實例求解

已知Z企業(yè)[16]現(xiàn)有的多條包裝生產(chǎn)線均為單一品種包裝生產(chǎn)線，由于各種產(chǎn)品需求量相差較大，表現(xiàn)在包裝生產(chǎn)線上就是各條線有忙有閑，工作負荷分布不均，為了提高包裝生產(chǎn)線的利用率，有必要引入混流包裝生產(chǎn)線。通過調(diào)研發(fā)現(xiàn)A、B兩種鋼卷產(chǎn)品結(jié)構(gòu)相似、工藝相近，因此對其混流包裝生產(chǎn)線進行優(yōu)化設(shè)計，其綜合作業(yè)優(yōu)先關(guān)系圖和作業(yè)元素時間分別如圖3和表2所示。

該企業(yè)一天的生產(chǎn)時間為8小時，采用兩班制，即57600秒。根據(jù)需求量的要求，包裝線每天至少生產(chǎn)產(chǎn)品480個。兩種產(chǎn)品包裝數(shù)量占總包裝數(shù)量的比例分別為qA=2/3，qB=1/3，則初始生產(chǎn)節(jié)拍為C=57600/480=120秒。

[17]，將改進粒子群算法中的參數(shù)設(shè)置如下：PS=80，c1=c2=2.05，w1=10，w2=1，Tmax=100。將c1=c2=2.05代入式(10)和式(9)得：?=4.1，χ=0.7298。

根據(jù)第3節(jié)中的求解流程，采用MATLAB軟件對其進行編程求解，結(jié)果如表3所示。

則該鋼卷混流包裝線的平衡率為：

圖3 產(chǎn)品A和產(chǎn)品B的綜合作業(yè)優(yōu)先關(guān)系圖

表2 產(chǎn)品A和產(chǎn)品B的作業(yè)元素作業(yè)時間

表3 鋼卷包裝生產(chǎn)線平衡結(jié)果

由此可以看出，采用改進粒子群算法求解鋼卷混流包裝線平衡問題取得了較好的平衡效果。

5 結(jié)束語

針對鋼卷混流包裝生產(chǎn)線的平衡問題，以工作站數(shù)和各工作站作業(yè)時間均方差的線性組合最小化為目標函數(shù)，采用改進粒子群算法對其進行求解，結(jié)果表明改進粒子群算法可以有效地求解鋼卷混流包裝生產(chǎn)線的平衡問題。

參考文獻：

[1]苑明海,李東波,于敏建.面向大規(guī)模定制的混流裝配線平衡研究[J].計算機集成制造系統(tǒng),2008,14(1):79-83.

[2]TANG Q H, LIANG Y L, ZHANG L P, et al. Balancing mixedmodel assembly lines with sequence-dependent tasks via hybrid genetic algorithm[J].Journal of Global Optimization, 2016,65(1):83-107.

[3]HAQ A N, RENGARAJAN K, JAYAPRAKASH J.A hybrid genetic algorithm approach to mixed-model assembly line balancing[J]. International Journal of Advanced Manufacturing Technology, 2006, 28(3-4): 337-341.

[4]TIACCI L, SAETTA S, MARTINI A. Balancing mixed-model assembly lines with parallel workstations through a genetic algorithm approach[J]. International Journal of Industrial Engineering:Theory Applications and Practice,2006,13(4):402-411.

[5]MAMUN A A, KHALED A A, ALI S M, et al. A heuristic approach for balancing mixed-model assembly line of type i using genetic algorithm[J].International Journal of Production Research,2012, 50(18): 5106-5116.

[6]YU JF, YINYH. Assembly line balancing based on an adaptive genetic algorithm[J].International journal of advanced manufacturing technology,2010,48(1-4):347-354.

[7]AKPINAR S, BAYHAN G M. A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints[J].Engineering applications of artificial intelligence,2011,24(3): 449-457.

[8]YUAN B, ZHANG C Y, SHAO X Y, et al. An effective hybrid honey bee mating optimization algorithm for balancing mixedmodel two-sided assembly lines[J].Computers and Operations Research,2015,53:32-41.

[9]SAIF U, GUAN Z L, LIU W Q, et al. Multi-objective artificial bee colony algorithm for simultaneous sequencing and balancing of mixed model assembly line[J].International journal of advanced manufacturing technology,2014, 75(9-12):1809-1827.

[10]AKPINAR S, BAYHAN G M. Performance evaluation of ant colony optimization-based solution strategies on the mixed-model assembly line balancing problem[J].Engineering Optimization,2014,46(6):842-862.

[11]AKPINAR S, MIRAC B G, BAYKASOGLU A.Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks[J].Applied Soft Computing Journal, 2013,13(1):574-589.

[12]YAGMAHAN B.Mixed-model assembly line balancing using a multi-objective ant colony optimization approach[J].Expert Systems with Applications. 2011, 38(10):12453-12461.

[13]ZHANG Z Q,CHENG W M,ZHONG B, et al. Hybrid behavior ant colony optimization for mixed-model assembly line balancing problem[J].Journal of Mechanical Engineering,2009,45(5):95-101.

[14]Blum C. Beam-ACO for Simple Assembly Line Balancing[J].Informs journal on computing, 2008, 20(4): 618-627.

[15]ZHANG X M, HAN X C. The Balance Problem Solving of the Car Mixed-model Assembly Line Based on Improved Differential Evolution Algorithm[J].Applied Mechanics and Materials, 2012(220-223):178-183.

[16]劉海江.寶發(fā)展鋼產(chǎn)品包裝工藝技術(shù)報告[R].上海:同濟大學(xué)現(xiàn)代制造技術(shù)研究所,2012.

[17]段曉東,王存睿,劉向東.粒子群算法及其應(yīng)用[M].沈陽:遼寧大學(xué)出版社,2007.