基于改進遺傳算法的混流手機殼產(chǎn)線動態(tài)平衡研究

顏家新YAN Jia-xin；黃麗HUANG Li

（①攀枝花學院智能制造學院，攀枝花 617000；②攀枝花學院經(jīng)濟與管理學院，攀枝花 617000）

0 引言

個性化的購買趨勢使傳統(tǒng)高度自動化的生產(chǎn)模式難以適應市場需求，促使制造企業(yè)選擇多品種、小批量的柔性生產(chǎn)方式。然而，柔性化的生產(chǎn)模式會增加生產(chǎn)系統(tǒng)的組織、調(diào)度和最優(yōu)控制的難度，如果不能制定合理的生產(chǎn)作業(yè)計劃，則會導致生產(chǎn)效率低下，難以保證交貨期[1]，將會嚴重影響企業(yè)效益。因此，混流制造系統(tǒng)調(diào)度問題的研究和探索十分必要。

混流裝配線投產(chǎn)排序是通過滿足某些約束條件來解決一些復雜組合優(yōu)化問題，是柔性制造系統(tǒng)中排序的一種典型問題。投產(chǎn)排序的目的是通過根據(jù)不同產(chǎn)品訂單的工藝路線或交貨時間從而合理制定分配資源、優(yōu)化性能指標為企業(yè)制定出最優(yōu)的投產(chǎn)排序方案，從而為企業(yè)帶來最低的生產(chǎn)成本和最高的經(jīng)濟效益。因此，設(shè)計出能夠適應市場內(nèi)外環(huán)境變化、持續(xù)保持動態(tài)平衡的裝配線，已成為現(xiàn)代企業(yè)急不可待的需求之一。

學者楊武成[2]針對第一類混流裝配線平衡問題，兼顧工作站數(shù)、工人數(shù)和工作站負荷均衡，引入了新變量和不對稱約束來構(gòu)建新的數(shù)學模型。提出了一種改進的雞群算法求解，研究結(jié)果表明：在算例驗證中，對比傳統(tǒng)的模型，新模型多找出8 個算例的最優(yōu)解，且尋優(yōu)速度更快。

學者劉禹[3]針對現(xiàn)有生產(chǎn)平衡技術(shù)中研究較少的第二類生產(chǎn)線平衡問題，將工業(yè)工程方法與改進遺傳算法相結(jié)合，提出一種用改進遺傳算法來分析、解決生產(chǎn)線平衡問題的方法技術(shù)，并把這種方法應用到實際生產(chǎn)線平衡問題的改善上，取得了較好的效果。

學者張曉文[4]針對初始生產(chǎn)線平衡的串-并聯(lián)生產(chǎn)系統(tǒng)，采用可靠度恢復因子描述設(shè)備維護前后的可靠度演變，建立了一種基于可靠度的以總成本最小為優(yōu)化目標的串-并聯(lián)生產(chǎn)系統(tǒng)機會維護模型，采用蒙特卡洛仿真的方法獲得最優(yōu)的預防性維護和機會維護的閾值，從而得到滿意的維護計劃。

在裝配線的動態(tài)平衡問題中考慮串-并聯(lián)生產(chǎn)系統(tǒng)的研究很少，而本文的研究又為裝配線的動態(tài)平衡問題提供了考慮串-并聯(lián)生產(chǎn)系統(tǒng)的新方向。本文針對混流裝配線串-并聯(lián)生產(chǎn)系統(tǒng)的多目標優(yōu)化問題，建立了以降低生產(chǎn)節(jié)拍和工作站負荷為目標的優(yōu)化模型，運用了雙種群遺傳算法的模型求解方法，實現(xiàn)了針對生產(chǎn)線生產(chǎn)節(jié)拍和工作站負荷的優(yōu)化目標。

1 案例分析與改善

1.1 問題描述

成都J 有限公司手機殼裝配線為研究對象，該公司的總裝線為一條混流生產(chǎn)線，在該總裝線上裝配型號A、B、C 為三種結(jié)構(gòu)相似的手機殼。公司每天兩個班次，每個班次的有效工作時間為8H；手機殼的每日計劃總產(chǎn)量為2500 件，其中，手機殼三種型號的計劃產(chǎn)量為A:B:C=1000:1000:500。各工作站作業(yè)任務(wù)和串并聯(lián)關(guān)系見表1，各工作站產(chǎn)品作業(yè)時間見圖1。

表1 各工作站作業(yè)任務(wù)和串并聯(lián)關(guān)系

其中，手機殼裝配線初始平衡的有效工作時間T=2×8×3600=57600s；日需求Dq=2500 件；K=16 個工作站，每個工作站的作業(yè)時間見圖，根據(jù)生產(chǎn)線平衡公式得出，T=25s/件；線平衡率P=58.11%；線平滑指數(shù)SI=1.52；根據(jù)以上數(shù)據(jù)裝配線的初始平衡在一個基本滿意狀態(tài)。

1.2 數(shù)學建模

設(shè)定相關(guān)參數(shù)符號如下：

N：裝配任務(wù)總數(shù)；

i：產(chǎn)品作業(yè)任務(wù)編號，I 總的產(chǎn)品裝配作業(yè)任務(wù)數(shù)（i=1，2，…，I）；

Q：產(chǎn)品品種編號（Q=1，2，3）；

Wq：第q 種產(chǎn)品的需求比例；

K：工作站數(shù)；

CT0：裝配線理論生產(chǎn)節(jié)拍；

Ak：第k 個工作站被占用時為1，未占用時為0；

Tiq：作業(yè)任務(wù)第q 種產(chǎn)品作業(yè)時間；

F：工作站中各工序為串聯(lián)時為1，并聯(lián)時則為0；

設(shè)定決策變量如下：

Xik作業(yè)任務(wù)分配到第個工作站時為1，否則為0。

模型假設(shè)：

①每個作業(yè)任務(wù)的加工緊前緊后關(guān)系已知；

②每個作業(yè)任務(wù)的加工標準工時已知；

③不同品種的相同裝配任務(wù)均安排在同一個工作站；

④確定每個作業(yè)任務(wù)的裝配時間，裝配線上不同產(chǎn)品具有相同作業(yè)任務(wù)，但是裝配時間可能不同；

⑤原有的舊裝配線基本平衡，且各作業(yè)人員能勝任所分配的裝配任務(wù)；

⑥混流裝配線上裝配的產(chǎn)品類型不同，但是裝配的產(chǎn)品具有相同的工藝和結(jié)構(gòu)。

式（1）是保證N 項裝配任務(wù)都只被分配到其中的一個工作站k。

式（2）是表示作業(yè)任務(wù)必須滿足裝配任務(wù)順序約束；

式（3）是表示K 個工作站的作業(yè)總時間均不能超過擬定的生產(chǎn)節(jié)拍CT0；

式（4）是表示在新的平衡中，i 裝配任務(wù)被分配到工作站K 的決策變量是0/1 型。

設(shè)置綜合評價函數(shù)：

在分析混流裝配線中出現(xiàn)的實際問題后，建立出工作地的工作負荷均衡和工作地實際生產(chǎn)節(jié)拍最小化兩個優(yōu)化目標的數(shù)學模型。

①目標函數(shù)一：在滿足理論生產(chǎn)節(jié)拍的基礎(chǔ)上，且工作地數(shù)已知的情況下，要使實際生產(chǎn)節(jié)拍足夠小。其數(shù)學模型如（5）所示。

②目標函數(shù)二：采用各工作地負荷均衡指數(shù)SI 來進行判斷，即取每個工作地裝配時間加權(quán)值的方差。在滿足生產(chǎn)節(jié)拍的同時，各工作地負荷均衡指數(shù)SI 要盡量小。其數(shù)學模型如（6）所示。

綜合評價函數(shù)：運用加權(quán)法對多目標優(yōu)化問題中的多個目標按其重要程度賦以適當?shù)臋?quán)重系數(shù)，把復雜的多目標優(yōu)化問題轉(zhuǎn)變?yōu)閱文繕藛栴}進行求解，這樣不僅能夠降低求解的難度還能保證生成解的質(zhì)量。式（7）式表示最小綜合評價值Z，其中a，b 為權(quán)重系數(shù)，滿足a+b=1。

計算目標權(quán)重：

①優(yōu)化目標重要程度的判斷矩陣構(gòu)建：

生產(chǎn)節(jié)拍最小化能夠提高裝配線的裝配效率，它是保證產(chǎn)品能夠按時交付的關(guān)鍵目標。因此，生產(chǎn)節(jié)拍比工作站平滑指數(shù)重要。根據(jù)這兩個目標之間的重要程度可以構(gòu)造出多目標的判斷矩陣如表2 所示。

表2 多目標判斷矩陣

②目標權(quán)重的計算：依據(jù)上述多目標的判斷矩陣，可以計算得出兩個優(yōu)化目標的權(quán)重。運用MATLAB 的eig 函數(shù)計算判斷矩陣的最大特征值和最大特征向量。

A=[1 4/3；3/4 1]；

[x，y]=eig（A）；%求得x 為特征向量矩陣，y 為特征值矩陣。

[mm]=find（y=max（max（y）））；%找到y(tǒng) 中對應最大的特征值所在列m。

w=x（:，m）/sum（x（:，m））%w 即為矩陣A 的權(quán)重。

計算結(jié)果：最大特征值為2，特征向量的分量值對應著每個優(yōu)化目標的權(quán)重。w=[0.5714；0.4286]。

③一致性檢驗：判斷矩陣由分析者憑個人知識及經(jīng)驗建立起來的，難免存在一些誤差。為使判斷結(jié)果與實際相吻合，需要對判斷矩陣進行一致性的檢驗。但由于二階矩陣完全一致故不需要一致性檢驗。

因此生產(chǎn)節(jié)拍、工作站平滑指數(shù)優(yōu)化目標權(quán)重為：

a=0.5714，b=0.4286

1.3 算法設(shè)計

雙種群遺傳算法的特點是具有兩個子種群。并且這兩個子種群分別單獨進化，他們只是在保留各種群最優(yōu)染色體后，依著規(guī)定的規(guī)則相互之間進行交流。這種方式的優(yōu)勢在于：每個子種群的即可以單獨進化去確保其各自種群的特性，而在子種群間互相交流則確保了可行解快速的收斂的同時，也擴大了搜索范圍，增強了種群的多樣性，也避免了陷入局部最優(yōu)的困境。

雙種群遺傳算法流程如圖2 所示，改進遺傳算法解決混流生產(chǎn)線平衡問題時，設(shè)置以下參數(shù)：

圖2 算法流程圖

①種群數(shù)量N。參考文獻[3]推薦的初始種群規(guī)模在20-160 之間。

②交叉概率C。即種群中染色體進行交叉的概率。

③變異概率M。即種群中染色體發(fā)生變異概率。文獻[3]推薦的經(jīng)驗值為0.005-0.2。

④遺傳代數(shù)G。

⑤綜合評價函數(shù)Z。為式（7）中的值，目標函數(shù)值越小越符合條件。

⑥選擇策略S。為了避免在遺傳中對最優(yōu)解的破壞，選擇保優(yōu)策略。選擇策略為在每代遺傳中保留10%的最優(yōu)父代替換新一代中相應個數(shù)的最差染色體組成新種群。這樣既保留了父代最優(yōu)解，同時也保證了能夠產(chǎn)生足夠多的子代進行交叉、變異，最大程度的保證了新一代染色體的優(yōu)秀度。

⑦交換和保留策略E。找到種群1 中經(jīng)過交叉、變異之后的最優(yōu)染色體，并標記位置和存儲綜合評價指標Z；找到種群2 中進過交叉、變異之后的最優(yōu)染色體，并標記位置和存儲綜合評價指標Z。將種群1 的最優(yōu)染色體和種群2 的最優(yōu)染色體進行交換。比較兩種群最優(yōu)染色體的Z值。將最小Z 值的染色體視作最好的染色體并保留下來。

1.4 算例分析

企業(yè)調(diào)整生產(chǎn)計劃，改進現(xiàn)有的產(chǎn)品裝配工藝，將原來的裝配作業(yè)元素除塵優(yōu)化，新加入裝配作業(yè)元素自動除塵、復判，且手機殼三種型號的日均產(chǎn)量調(diào)整為A:B:C=500:1500:1000，三種產(chǎn)品總需求量為3000 片。改變后該生產(chǎn)線總共有21 個工序，16 個工作站。表3 為三種產(chǎn)品經(jīng)過21 道工序所對應的加工時間。表4 為兩個種群具體算法參數(shù)設(shè)置。

表3 各工序加工時間

表4 各種群算法參數(shù)

1.5 優(yōu)化結(jié)果

適應度進化曲線如圖3 所示。從曲線的走勢來看收斂性良好，在運行到第26 代即找到了近似最優(yōu)解。

圖3 適應度進化曲線

最優(yōu)排布如圖4 所示。圖中字段列表示工作站的編號。gs 列中數(shù)字表示該工作站包含幾個工序。Ct 列代表計算出的該工作站的生產(chǎn)節(jié)拍。Job 代表生成的工作站里包含的工序，其中數(shù)字代表在表3 中工序的順序。flag 代表該工作站的串并聯(lián)關(guān)系。為0 時代表為并聯(lián)，為1 時代表為串聯(lián)。

圖4 最優(yōu)染色體

2 方案評價

各工作站作業(yè)時間如圖5 所示。結(jié)果表明裝配線平衡率提升了8.43%，各工作站生產(chǎn)負荷減少了0.9305。

圖5 工作站作業(yè)時間

經(jīng)過混流裝配線平衡后的各工作站生產(chǎn)節(jié)拍比平衡前更加均衡，尤其對于每一個工作站的生產(chǎn)負荷來看分配更均衡。這樣提高生產(chǎn)線的整體運行效率，在一定程度上降低了生產(chǎn)線運作成本，提高了J 公司的運作管理水平。

3 小結(jié)

以成都有限公司為案例，均衡分配工作站裝配任務(wù)，重新規(guī)劃布局。提高企業(yè)混流裝配線生產(chǎn)的柔性、提高企業(yè)生產(chǎn)效率、縮短轉(zhuǎn)產(chǎn)時間、降低企業(yè)生產(chǎn)成本，使企業(yè)在現(xiàn)今市場更具有競爭力。

然而，本文是以最小工作節(jié)拍和最小工作負荷為優(yōu)化目標，針對不同優(yōu)化目標的組合的生產(chǎn)線平衡問題還有待于進一步研究。本文沒有考慮串并聯(lián)生產(chǎn)系統(tǒng)對人的影響，針對串并聯(lián)生產(chǎn)系統(tǒng)對人因的影響還有待于進一步研究。