基于雙種群遺傳算法的T 公司生產線平衡改善

趙龍基，劉 洋，鄭 璇，吳鴻宇

（中國礦業大學（北京） 能源與礦業工程學院，北京 100083）

0 引言

隨著第四次工業革命的到來，全球的制造業正在遭受著前所未有的沖擊和變革。各個工業發達國家相繼制定了國家戰略規劃，以求在這次變革中抓住新的發展機遇。近年來，中國發展進入新常態，發展速度逐漸放緩，企業出現了產能過剩、制造成本升高、客戶流失的現象，競爭程度日益激烈。因此，企業在面對激烈的競爭環境下，不僅要重視技術研發，更要注重生產管理，改變原有的生產方式，合理分配生產資源，優化生產線，提高生產效率。

對生產線進行平衡性改善是工業工程專業領域最初始也是最基本的問題，能夠合理調配企業內部生產，消除生產過剩、作業間不平衡所導致的效率損失[1]。傳統制造業對生產線的研究是將生產工藝進行細分，并根據細分后的工作內容，將生產線作業過程劃分為不同的作業單元的階段[2]。此類研究方式優點在于易于提高工人作業熟練度，單元生產效率快。但此類劃分方式容易導致劃分后工作任務分配不平衡，不同的工序作業時間相差較大，生產線整體節拍高、部分工位生產力浪費嚴重，需要進行后續改進。國外關于生產線優化方面的研究始很長的時間，但直到21 世紀，國內的專家和學者才開始對生產線優化進行深入研究，目前在研究過程中主要用到工業工程技術、數學模型、仿真建模等優化工具等。 VanchaiLaem 運用工作研究相關方法，以冷凍食品加工生產線為研究對象，通過優生產工藝流程，對工序進行重排優化和合理布局，生產線平衡率提升了12.48%，單個產品生產成本降低了16.65%。Pornthipa 通過調研分析生產流程，找出了生產中的瓶頸工序。然后應用生產線平衡相關理論和ECRS 四大改善原則對生產流程進行優化，并用小車運輸代替人工搬運，達到了節省生產人員14 位，生產效率提升至94.2%的效果。Kitaw 通過對服裝生產過程進行仿真模擬，識別出瓶頸工序，并應用工業工程方法為解決瓶頸工序、生產效率低及服裝產品周期短、生產周期長等問題提供了優化方案。國內外學者對裝配生產線優化的問題研究主要是基于改進算法和建立仿真模型，主要包括粒子群算法、遺傳算法、蜂群算法等。因此，本研究采用雙種群遺傳算法以及Flexsim 軟件對T 公司生產線平衡問題進行優化求解最終達到提升生產線平衡率以及降低生產節拍的目的。

1 T 公司生產線平衡問題的數學描述

1.1 T 公司生產線數據及生產線流程圖

T 公司作為一家傳統的制造企業，其生產線作業方案制定主要是按照工藝方式與作業順序，工位安排與產線布局粗糙，不同工作站之間作業時間相差較大，不同作業單元的工人勞動強度懸殊，由此帶來工人工作人員情緒低落，工人安全與產品質量難以保障，生產效率低下、生產成本增加。基于以上原因，對T 公司目前生產線進行平衡性改善研究，提高生產線平衡率、重新規劃工作站是提高產量，降低成本的有效方式。目前T 公司生產線平衡率現階段為85.85%，生產線平滑指數為3.85。生產節拍為49.11 s。整條生產線利用率最低的流程的加工率只有17.2%，利用率排名前十的工序加工率平均值為84.63%。

T 公司的65F6 機型生產線的主要工時統計表見表1。

表1 65F6 機型作業工序節拍

T 公司初始生產線流程圖如圖1 所示。

圖1 初始生產線流程圖

1.2 生產線評價指標及目標函數

目前主流的生產線平衡評價指標為生產線平衡率與生產線平滑系數，其定義以及計算公式如下[3]：

生產線平衡率：生產線平衡率通常用來形容整條生產線作業時間的平衡程度，同時也可定量展示生產線的連貫性，其計算式為：

式中：P為生產線平衡率；T（Si）為編號為i的作業單元的作業時間；maxT（Si）為作業時間最長的作業單元；m為工作站數量。

平滑指數：平滑指數通常被用來衡量某一單個工作站與整條生產線的平均生產時間之間的偏離程度，其計算式為：

式中：SI為生產線平滑指數；CT為生產線生產節拍；T（Si）為編號為i的作業單元的作業時間；m為工作站數量。

主要改善目標是根據上述兩個評價指標，通過工作站的劃分，提高生產線的整體平衡率，降低生產線平滑指數。據此，設立目標函數為：

式中：n為工作站序號；α=β= 0.5。P越接近1，生產線平衡效果越好；生產線的平滑指數SI與工作站負荷的均衡程度成反比。α與β為分別賦予生產線平衡率以及生產線平滑指數的權重，為兩者賦予相等的重要程度，在分母中的SI之后加0.01 是為了避免SI為0 時產生無窮大干擾求解。目標函數就是綜合生產平衡率和生產平衡指數，對生產線進行評價的一個值，并通過采用雙種群遺傳算法來防止平衡指數收斂過快，從而避免至得出局部最優解。

基于上述數學模型與生產線的實際情況，擬定如下約束條件：

（1）作業單元最小：一個作業單元在一次分配中只能存在于同一個工作站。

（2）作業單元必須全部分配完成。

∪ni=1Si = E（5）

（3）所有工作站的加工時間均低于生產線節拍。

（4）作業單元的分配需要服從作業單元之間的優先關系，即作業單元的分配需要滿足0-1 矩陣：

若作業單元i為單元j的緊前工序，那么aij= 1，否則aij= 0。

2 T 公司生產線的雙種群遺傳算法設計

2.1 作業單元編碼

使用遺傳算法解決生產線平衡問題的首要步驟是采用一個能夠針對具體問題特征的編碼方式對作業單元進行編碼。采用實體編碼的方式進行編碼，把每一個單獨的作業單元作為一個單獨的基因，選擇作業單元序號所有排布情況中能夠滿足作業優先順序的排列方式作為染色體數據串，將其作為初始種群的染色體，這種編碼方式能夠比較完好地適應目標函數以及操作算子從而使得算法結果具有準確性[4]。

本文結合實際生產過程中工藝流程獲得優先關系矩陣，進而對作業單元進行編碼，得到雙種群遺傳算法中的初始染色體。

2.2 譯碼

譯碼就是在滿足約束條件的情況下，將染色體所包含的信息轉換為實際表現。根據生產線平衡問題類別的不同，譯碼的方式也會隨之發生改變[5]。

本文對CT 值的探索方式進行改進，基于生產線節拍自身所存在的變化規律進行譯碼，其主要步驟如下：

（1）以理論最優解作為初始值，初始化生產線節拍，計算公式見6。

式中：T為生產線上所有單元加工完成的時間之和；M為預設的生產線初始工作站數量。

（2）基于CT(初始)按照作業單元之間的優先順序將n個作業單元分配到m個工作站，設第個工作站的作業時間為T（si）。將工作站作業時間T（si）與初始作業節拍CT(初始)進行比較。當所有工作站的作業時間均小于作業節拍，則認為此種情況下的作業排布滿足最優解，停止搜索并輸出最優解。如果不滿足，則進行下一步操作。

（3）對設計生產節拍的增量，根據生產線的性質以及生產節拍的定義，我們取可能增量為Δi= 第i+1個工作站的首個作業單元作業時間（i= 1，2，3，…，m- 1）。

（4）確定節拍增量后將節拍增量與初始節拍相加得到增量后的生產線節拍。

（5）令CT= max{T（si）}如果CT(修正)> = min{T（si）+Δi}則重新返回第二步，繼續對CT進行修正，否則取得最小節拍，停止迭代。

2.3 適度評估

本研究的問題歸屬于第二類生產線平衡問題，預期目標為生產線平衡率盡可能大的同時，生產線平滑指數盡可能小，因此本文預設適度函數為：

式中：

2.4 選擇

用輪盤賭的方式進行父代選擇。輪盤賭方式的實際含義為：將所有父代被選擇的概率進行歸一化處理，并按照適應度分配每個個體被選擇為父代的概率。

2.5 交叉

傳統的遺傳算法因為引入適度函數，會導致局部最優解的出現概率較大，為了防止此類情況，引入第二種群，第一個種群進行全局搜索，提供最優超平面，第二種群進行局部子搜索，保證算法的收斂速度。

本文在具體運行算法的過程中，采用了兩點交叉的方式進行來獲得新的個體。

2.6 變異

為了保證能夠探尋全局，采用的雙種群遺傳算法對子種群1 設置大變異算子，子種群2 設置小變異算子。操作如下：

定義大變異算子：

式中：P1m為第一個子種群出現交叉的概率；P2m為第二個子種群出現交叉的概率；f1max為第一個子種群中適應度最大的個體適應度；f2max為第二個子種群中適應度最大的個體適應度；f1avg為第一個子種群所有個體的適應度；f2avg為第二個子種群所有個體的適應度。

2.7 種群基因交換

為了充分發揮雙種群遺傳算法全局搜索的優勢，算法每一次迭代均進行如下的基因交換：

（1）交換兩個種群中適應度最高的個體。

（2）在父代挑選結束后，隨機交換若干個個體。

3 實際案例

選擇較為經典的生產線模型——Jackson 模型進行試求解。令初始種群1 和2 中的個體數均為100；種群1 和2 的交叉概率分別為0.8 與0.2；種群2 的變異率為0.05；迭代300 次。

在上述條件下，求不同工站數目之下函數的最優解，從而確定能夠使得生產線平衡性最優的工位布置方式。

通過對不同數量的工作站情況下取得最優工序排布情況進行統計，結果見表2。

表2 不同工作站數量下的最優工序排布

從表2 可以看出，當工作站數量取5 的時候，目標函數取得最大值0.5542 生產線平衡率最高為97.79%，生產平滑指數為3.85。隨后無論工作站取4或者6、7、8，目標函數均無法取得超過0.5542 的最大值，且生產線平衡率與生產平滑指數也都無法超過5個工作站時的情況。

因此，最優工作站數量為5。同時，根據現場實際情況對最優解進行調整，最終結果見表3。

表3 最優工作站數量下的生產線數據

4 基于Flexsim 改進效果仿真驗證

為了更好地驗證工作站劃分帶來的效果，根據改進之后的工作站排布方式建立仿真模型，如圖2 所示。

圖2 劃分工作站后的生產線線仿真模型

由表3 可知，劃分工作站之后，工作站數量為5的工作耗時最少。在劃分工作站的過程中對作業單元進行了刪減，因此需要對產量進行在此仿真評估，搭建改進后的仿真模型如圖3 所示。

圖3 改善后的生產線流程圖

改善后運行模型，經過一個月后，得到生產線月產量為82453 臺，較未改善的月產量54543 臺提高了51.17%。生產節拍由最初的49.11 s 提升至32.48 s。

5 結束語

本研究通過采用雙種群遺傳算法對生產線數學模型進行求解，并統計百次運行下的最優目標函數分布情況。研究結果表明，生產線最終平衡率由公司現階段實施方案的85.85%提升至97.79%，生產線平滑指數為3.85。生產節拍由最初的49.11 s 降低至32.48 s。整條生產線中，利用率最低的流程的加工率從17.2%提升至52.13%，利用率排名前十的工序加工率平均值從84.63%降低至80.02%。整條生產線的平衡率得到有效提升。