王 強(qiáng)，張含葉，王 利

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

0 引言

鋼卷的品種和數(shù)量隨顧客需求的變化而變化，在最短的時(shí)間內(nèi)，應(yīng)該能最大限度地滿足不同客戶的個(gè)性化需求。鋼卷的混流包裝線能夠適應(yīng)多品種生產(chǎn)的需要，在基本不改變現(xiàn)有生產(chǎn)手段、生產(chǎn)條件和生產(chǎn)能力的前提下，通過改變生產(chǎn)組織方式，在一定的時(shí)間內(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]、差分進(jìn)化算法[15]等。本文采用改進(jìn)粒子群算法對對混流鋼卷包裝線平衡問題進(jìn)行研究。

1 問題描述

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

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

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

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

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

2.1 變量定義

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

2.2 目標(biāo)函數(shù)

其中：

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

2.3 約束條件

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

表1 變量定義

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

3.1 基本粒子群算法

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

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

3.2 改進(jìn)粒子群算法

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

改進(jìn)粒子群算法的流程如下：

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)，計(jì)算適應(yīng)度函數(shù)；

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

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

4 實(shí)例求解

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

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

[17]，將改進(jìn)粒子群算法中的參數(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軟件對其進(jìn)行編程求解，結(jié)果如表3所示。

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

[1]苑明海,李東波,于敏建.面向大規(guī)模定制的混流裝配線平衡研究[J].計(jì)算機(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ù)報(bào)告[R].上海:同濟(jì)大學(xué)現(xiàn)代制造技術(shù)研究所,2012.

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