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

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

（中國礦業(yè)大學(xué)（北京） 能源與礦業(yè)工程學(xué)院，北京 100083）

0 引言

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

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

1 T 公司生產(chǎn)線平衡問題的數(shù)學(xué)描述

1.1 T 公司生產(chǎn)線數(shù)據(jù)及生產(chǎn)線流程圖

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

T 公司的65F6 機型生產(chǎn)線的主要工時統(tǒng)計表見表1。

表1 65F6 機型作業(yè)工序節(jié)拍

T 公司初始生產(chǎn)線流程圖如圖1 所示。

圖1 初始生產(chǎn)線流程圖

1.2 生產(chǎn)線評價指標(biāo)及目標(biāo)函數(shù)

目前主流的生產(chǎn)線平衡評價指標(biāo)為生產(chǎn)線平衡率與生產(chǎn)線平滑系數(shù)，其定義以及計算公式如下[3]：

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

式中：P為生產(chǎn)線平衡率；T（Si）為編號為i的作業(yè)單元的作業(yè)時間；maxT（Si）為作業(yè)時間最長的作業(yè)單元；m為工作站數(shù)量。

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

式中：SI為生產(chǎn)線平滑指數(shù)；CT為生產(chǎn)線生產(chǎn)節(jié)拍；T（Si）為編號為i的作業(yè)單元的作業(yè)時間；m為工作站數(shù)量。

主要改善目標(biāo)是根據(jù)上述兩個評價指標(biāo)，通過工作站的劃分，提高生產(chǎn)線的整體平衡率，降低生產(chǎn)線平滑指數(shù)。據(jù)此，設(shè)立目標(biāo)函數(shù)為：

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

基于上述數(shù)學(xué)模型與生產(chǎn)線的實際情況，擬定如下約束條件：

（1）作業(yè)單元最?。阂粋€作業(yè)單元在一次分配中只能存在于同一個工作站。

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

∪ni=1Si = E（5）

（3）所有工作站的加工時間均低于生產(chǎn)線節(jié)拍。

（4）作業(yè)單元的分配需要服從作業(yè)單元之間的優(yōu)先關(guān)系，即作業(yè)單元的分配需要滿足0-1 矩陣：

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

2 T 公司生產(chǎn)線的雙種群遺傳算法設(shè)計

2.1 作業(yè)單元編碼

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

本文結(jié)合實際生產(chǎn)過程中工藝流程獲得優(yōu)先關(guān)系矩陣，進(jìn)而對作業(yè)單元進(jìn)行編碼，得到雙種群遺傳算法中的初始染色體。

2.2 譯碼

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

本文對CT 值的探索方式進(jìn)行改進(jìn)，基于生產(chǎn)線節(jié)拍自身所存在的變化規(guī)律進(jìn)行譯碼，其主要步驟如下：

（1）以理論最優(yōu)解作為初始值，初始化生產(chǎn)線節(jié)拍，計算公式見6。

式中：T為生產(chǎn)線上所有單元加工完成的時間之和；M為預(yù)設(shè)的生產(chǎn)線初始工作站數(shù)量。

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

（3）對設(shè)計生產(chǎn)節(jié)拍的增量，根據(jù)生產(chǎn)線的性質(zhì)以及生產(chǎn)節(jié)拍的定義，我們?nèi)】赡茉隽繛棣= 第i+1個工作站的首個作業(yè)單元作業(yè)時間（i= 1，2，3，…，m- 1）。

（4）確定節(jié)拍增量后將節(jié)拍增量與初始節(jié)拍相加得到增量后的生產(chǎn)線節(jié)拍。

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

2.3 適度評估

本研究的問題歸屬于第二類生產(chǎn)線平衡問題，預(yù)期目標(biāo)為生產(chǎn)線平衡率盡可能大的同時，生產(chǎn)線平滑指數(shù)盡可能小，因此本文預(yù)設(shè)適度函數(shù)為：

式中：

2.4 選擇

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

2.5 交叉

傳統(tǒng)的遺傳算法因為引入適度函數(shù)，會導(dǎo)致局部最優(yōu)解的出現(xiàn)概率較大，為了防止此類情況，引入第二種群，第一個種群進(jìn)行全局搜索，提供最優(yōu)超平面，第二種群進(jìn)行局部子搜索，保證算法的收斂速度。

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

2.6 變異

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

定義大變異算子：

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

2.7 種群基因交換

為了充分發(fā)揮雙種群遺傳算法全局搜索的優(yōu)勢，算法每一次迭代均進(jìn)行如下的基因交換：

（1）交換兩個種群中適應(yīng)度最高的個體。

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

3 實際案例

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

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

通過對不同數(shù)量的工作站情況下取得最優(yōu)工序排布情況進(jìn)行統(tǒng)計，結(jié)果見表2。

表2 不同工作站數(shù)量下的最優(yōu)工序排布

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

因此，最優(yōu)工作站數(shù)量為5。同時，根據(jù)現(xiàn)場實際情況對最優(yōu)解進(jìn)行調(diào)整，最終結(jié)果見表3。

表3 最優(yōu)工作站數(shù)量下的生產(chǎn)線數(shù)據(jù)

4 基于Flexsim 改進(jìn)效果仿真驗證

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

圖2 劃分工作站后的生產(chǎn)線線仿真模型

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

圖3 改善后的生產(chǎn)線流程圖

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

5 結(jié)束語

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