基于雙種群遺傳算法對(duì)A公司生產(chǎn)線改造以及平衡問(wèn)題研究*

楊 磊，徐曉鳴※，張海洋，曾偉鎮(zhèn)

（1.廣東海洋大學(xué)機(jī)械與動(dòng)力工程學(xué)院，廣東湛江 524088；2.小天才科技有限公司，廣東東莞 523846）

0 引言

在需求多樣化市場(chǎng)下，客戶對(duì)產(chǎn)品的交付質(zhì)量和交付周期要求越來(lái)越高，如何將客戶需求與批量生產(chǎn)相結(jié)合來(lái)組織生產(chǎn)，是企業(yè)面臨的一個(gè)難題。國(guó)內(nèi)外企業(yè)紛紛引進(jìn)精益生產(chǎn)方式，采取混流生產(chǎn)線，以期提高生產(chǎn)效率和降低節(jié)拍，提高企業(yè)自身的競(jìng)爭(zhēng)力[1-3]。然而，進(jìn)行混流生產(chǎn)線改造首先要解決其平衡問(wèn)題。

針對(duì)混流生產(chǎn)平衡研究中，根據(jù)研究?jī)?nèi)容不同，第一類是給定節(jié)拍時(shí)間，求最小工位數(shù)；第二類是給定生產(chǎn)線長(zhǎng)度，求最小化節(jié)拍時(shí)間；第三類是優(yōu)化生產(chǎn)線工位負(fù)荷均衡。以往的研究大致有以下幾種研究方法：工業(yè)工程改善方法、啟發(fā)式算法、仿真方法和智能算法。吳智勇等[2]通過(guò)建立補(bǔ)充生產(chǎn)機(jī)制、模式排產(chǎn)、作業(yè)改善等精益改善方案，提升了混流生產(chǎn)的問(wèn)題；許向川等[3]利用Flexsim 仿真的方法，建立仿真模型，通過(guò)精益改善，提升了生產(chǎn)線平衡率；周金平[4]利用Plant Simulation 仿真軟件研究混流生產(chǎn)的物料配送問(wèn)題，優(yōu)化最大完工時(shí)間。包建軍等[5]運(yùn)用啟發(fā)式算法對(duì)混流裝配線的平衡問(wèn)題進(jìn)行分析與優(yōu)化，并采用Flexsim 仿真驗(yàn)證優(yōu)化方案的有效性。邱伊健等[6]利用Flexsim 對(duì)混流生產(chǎn)線的瓶頸問(wèn)題，生產(chǎn)線平衡問(wèn)題進(jìn)行優(yōu)化，并進(jìn)一步利用遺傳算法優(yōu)化投產(chǎn)序列；李偉等[7]針對(duì)混流裝配線第二類平衡問(wèn)題，建立了基于作業(yè)空間和裝配工具約束等條件下的優(yōu)化模型，并利用遺傳算法進(jìn)行求解；鄭晨鳴等[8]考慮了作業(yè)時(shí)間隨機(jī)情形下，最小工作站數(shù)和各產(chǎn)品負(fù)荷均勻?yàn)槟繕?biāo)，設(shè)計(jì)改進(jìn)的遺傳算法并驗(yàn)證其有效性。

本文結(jié)合A 企業(yè)實(shí)際生產(chǎn)場(chǎng)景，通過(guò)合并工藝相似的產(chǎn)品生產(chǎn)線，在考慮工序之間優(yōu)先順序、產(chǎn)品需求信息和作業(yè)時(shí)間約束下，以生產(chǎn)節(jié)拍和負(fù)荷均衡為目標(biāo)，建立混流生產(chǎn)線第二類平衡問(wèn)題的多目標(biāo)混合整數(shù)規(guī)劃模型，設(shè)計(jì)求解模型的有效算法，有效提高混流生產(chǎn)線平衡率和降低生產(chǎn)線均衡指數(shù)，從而提高企業(yè)的生產(chǎn)效率。研究?jī)?nèi)容為企業(yè)改造混流生產(chǎn)線提供理論依據(jù)和技術(shù)支持，可以推廣到其他類型的混流生產(chǎn)線設(shè)計(jì)與改造上。

1 混流生產(chǎn)線平衡模型建立

在一個(gè)計(jì)劃期T內(nèi)，已知某混流生產(chǎn)線上有N個(gè)工作站完成M種產(chǎn)品的裝配作業(yè)，這些產(chǎn)品的工藝相近、結(jié)構(gòu)相似，屬于企業(yè)內(nèi)同一產(chǎn)品族的[9-10]。該混流生產(chǎn)線上所有類型產(chǎn)品所包含的工序數(shù)為S，每種產(chǎn)品需求為Dm，M種產(chǎn)品的總需求量為表示第m種產(chǎn)品在第i道工序上加工的時(shí)間，由于不同類型的產(chǎn)品工序上有所不同，所以如果第m種產(chǎn)品不含有第i道工序，那么tim= 0，qm為第m種產(chǎn)品占總需求的比例，其中qm=Dq∕D；Tmk為第m種產(chǎn)品在第k個(gè)工作站單件裝配的時(shí)間。

模型假設(shè)條件：（1）各個(gè)作業(yè)元素的操作時(shí)間不變；（2）混流生產(chǎn)線的工作站可以進(jìn)行一種或者多種作業(yè)元素的操作，員工均為多技能工，可以完成任何任務(wù)；（3）一個(gè)作業(yè)元素僅能被分配到工作站，一個(gè)作業(yè)元素只能在一個(gè)工作站內(nèi)完成該作業(yè)元素的全部?jī)?nèi)容；（4）產(chǎn)品作業(yè)元素的優(yōu)先關(guān)系已知，并且作業(yè)元素加工的優(yōu)先關(guān)系不可變動(dòng)。

該問(wèn)題數(shù)學(xué)模型如下：

式中：CT為混流生產(chǎn)線的實(shí)際生產(chǎn)節(jié)拍；C*為混流生產(chǎn)線的理論節(jié)拍，C*=T∕D；Pre(i)為依據(jù)作業(yè)元素的優(yōu)先關(guān)系，先于作業(yè)元素i完成的作業(yè)元素集合。

式（1）表示在相同權(quán)重下求取最小生產(chǎn)節(jié)拍和負(fù)荷指數(shù)；式（2）表示產(chǎn)品在生產(chǎn)線中最小生產(chǎn)節(jié)拍；式（3）表示生產(chǎn)線的負(fù)荷指數(shù)，式（4）表示每個(gè)作業(yè)元素都只能被分配到一個(gè)工作站進(jìn)行加工；式（5）作業(yè)元素的分配必須遵守優(yōu)先關(guān)系集合；式（6）表示工作站的作業(yè)時(shí)間不得大于理論節(jié)拍時(shí)間；式（7）表示作業(yè)元素分配的決策變量，1表示作業(yè)元素i被分配到第k工作站到，0則表示作業(yè)元素i未被分配到k工作站。

2 雙種群遺傳算法

傳統(tǒng)的遺傳算法中，只有一個(gè)初始種群開(kāi)始操作、交叉和編譯遺傳，也稱為單種群的遺傳算法。雖然這種算法簡(jiǎn)單快捷，但是它很容易陷入局部最優(yōu)解而且搜索空間有限，因此需要在這種算法的基礎(chǔ)上擴(kuò)大搜索空間，能夠跳出局部最優(yōu)解，所以需要一種改進(jìn)的遺傳算法要在不止一個(gè)的種群之中來(lái)開(kāi)展操作[11-12]。

雙種群遺傳算法思路是兩個(gè)子種群使其各自進(jìn)化，再選擇合適的節(jié)點(diǎn)，使其按照設(shè)定的規(guī)則進(jìn)行種群間的交流，這種方式使用起來(lái)并不算復(fù)雜，而且可以擴(kuò)大了搜索的空間而避免了陷入局部最優(yōu)的缺點(diǎn)。其中這兩個(gè)子種群都有它各自的作用，種群1 中的交叉概率Pc和變異概率Pm的值較大，這個(gè)種群稱為探測(cè)子種群，主要是在進(jìn)化過(guò)程不斷地超越平面，克服過(guò)早收斂，使算法可以保持較高的搜索效率；種群2 的交叉概率Pc和變異概率Pm的值較小，被稱為開(kāi)發(fā)子種群，主要可以在局部范圍內(nèi)尋找優(yōu)秀個(gè)體，并把這些個(gè)體保持下來(lái)。

2.1 編碼設(shè)計(jì)

編碼直接決定了遺傳算法后續(xù)的操作，如選擇算子、交叉算子和變異算子的實(shí)現(xiàn)，遺傳算法的計(jì)算性能是受編碼直接影響的。應(yīng)對(duì)不同的實(shí)際問(wèn)題，應(yīng)采取恰當(dāng)?shù)木幋a方式，這樣才不會(huì)產(chǎn)生大量的非可行解，使得計(jì)算過(guò)程變得十分冗余。通過(guò)優(yōu)先關(guān)系圖來(lái)設(shè)計(jì)編碼方式，以保證種群解的可行性，編碼設(shè)計(jì)思路如圖1所示。

圖1 優(yōu)先作業(yè)關(guān)系編碼

2.2 譯碼設(shè)計(jì)

譯碼的思路如下：對(duì)未知的生產(chǎn)節(jié)拍，進(jìn)行節(jié)拍預(yù)估，一般是預(yù)估一個(gè)理論節(jié)拍CT*，然后以一定的增量去進(jìn)行試探計(jì)算。

步驟1：初始化節(jié)拍，計(jì)算理論節(jié)拍令CT*等于這個(gè)理論節(jié)拍。

步驟2：以CT*為暫定節(jié)拍，并將作業(yè)元素按照作業(yè)元素優(yōu)先關(guān)系圖的邏輯關(guān)系將m個(gè)作業(yè)元素分配到n個(gè)工作站中?？梢缘玫矫總€(gè)工作站的時(shí)間：T1，T2，…，Tk，…，Tn，如果這些工作站的時(shí)間小于CT*，那么CT*就是這個(gè)狀態(tài)下的最小節(jié)拍，搜索就停止，如果不是那么進(jìn)行下一步計(jì)算。

步驟3：計(jì)算潛在增量Δ1,Δ2,Δ3,…,Δn，其中Δi是第i+1 個(gè)工作站的第一作業(yè)元素的時(shí)間(i= 1,2,3,…,k,…,n)。令目前的工作站中作業(yè)時(shí)間最大 的 作 為 實(shí) 際 節(jié) 拍CT，CT*= min{Tk+ Δi} ，如 果CT≤CT*那么CT就是這種分配方案下的最小節(jié)拍，搜索停止；如果不符合條件就返回步驟2繼續(xù)分配作業(yè)元素。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

本生產(chǎn)線平衡建立模型第一目標(biāo)是最小生產(chǎn)節(jié)拍，本文通過(guò)平衡率指標(biāo)來(lái)映射生產(chǎn)節(jié)拍，第二目標(biāo)函數(shù)則是負(fù)荷指數(shù)，所以構(gòu)建的適應(yīng)度函數(shù)為：

2.4 選擇算子設(shè)計(jì)

采取輪盤(pán)賭方式進(jìn)行選擇，將種群中的個(gè)體分別計(jì)算遺傳到下一代的概率，再計(jì)算每個(gè)個(gè)體的累計(jì)概率，當(dāng)個(gè)體適應(yīng)度越大被選中的概率也就越大。

2.5 交叉算子設(shè)計(jì)

交叉算子采取的是兩點(diǎn)三段交叉，首先在父代染色體選取兩個(gè)交叉點(diǎn)，將這交叉點(diǎn)兩段之間的基因截取，在父代2中尋找相同基因片段的排序，將父代2中排序的基因投放至父代1 的交叉點(diǎn)之間形成子代1。子代2 的形成，同理可得。如圖2所示。

圖2 交叉示例

2.6 變異算子設(shè)計(jì)

采用單點(diǎn)交叉，在父代染色體中獲取變異點(diǎn)，變異點(diǎn)之前的基因保持不變，變異點(diǎn)之后的基因根據(jù)刪除后的優(yōu)先關(guān)系矩陣重新編排。如圖3所示。

圖3 變異示例

3 案例應(yīng)用

3.1 現(xiàn)有門(mén)體預(yù)裝生產(chǎn)線的平衡分析

目前A 公司的門(mén)體預(yù)裝生產(chǎn)線的生產(chǎn)模式是可變品種的批量生產(chǎn)，取該生產(chǎn)線生產(chǎn)量最大的3 種產(chǎn)品BD330、BD144、BD96，其日需求量分別為500、500、250，A 公司的日有效工作時(shí)間為10 h，各種型號(hào)的工序加工時(shí)間如表1所示。

表1 工序加工時(shí)間

BD330、BD144、BD96的理論節(jié)拍分別為72 s、72 s、144 s，生產(chǎn)平衡率分別為0.531、0.373 和0.509，現(xiàn)場(chǎng)測(cè)得BD330、BD144、BD96 的實(shí)際生產(chǎn)節(jié)拍分別為77.35 s、77.35 s和60.26 s，僅BD96的實(shí)際生產(chǎn)節(jié)拍在計(jì)劃節(jié)拍內(nèi)，在計(jì)劃期內(nèi)只有BD96 可以完成預(yù)期的計(jì)劃。剩下兩種產(chǎn)品都只能通過(guò)加班加點(diǎn)的方式來(lái)進(jìn)行產(chǎn)品產(chǎn)量的補(bǔ)償。

3.2 門(mén)體的作業(yè)元素劃分

進(jìn)行混流生產(chǎn)線平衡的研究要將在生產(chǎn)線上生產(chǎn)的產(chǎn)品最小作業(yè)單元?jiǎng)澐殖鰜?lái)，根據(jù)A 公司門(mén)體預(yù)裝生產(chǎn)線的實(shí)際生產(chǎn)情況，按照作業(yè)元素劃分的原則，使每個(gè)作業(yè)工序劃分到不能進(jìn)行下一步劃分的程度劃分作業(yè)元素時(shí)，遵循的原則如下。

（1）工序在被拆分之前可以進(jìn)行標(biāo)準(zhǔn)時(shí)間測(cè)量。

（2）若遇到不能再進(jìn)一步拆解的工序，那么該工序就是最小的作業(yè)單元。

（3）某些工序存在特殊的加工方法，在拆分工序后也必須保持加工方法。

考慮實(shí)際的生產(chǎn)情況和劃分作業(yè)元素遵循的原則，將作業(yè)元素劃分如表2所示。

表2 作業(yè)元素劃分表

3.3 繪制出綜合優(yōu)先關(guān)系圖

過(guò)各個(gè)產(chǎn)品的作業(yè)元素優(yōu)先加工順序表以及對(duì)應(yīng)的加工時(shí)間，再通過(guò)各產(chǎn)品的作業(yè)元素優(yōu)先加工順序表和各產(chǎn)品之間的需求比例制作出混合作業(yè)元素的時(shí)間表，進(jìn)而繪制出綜合優(yōu)先關(guān)系圖，如圖4所示。

圖4 綜合優(yōu)先關(guān)系

3.4 混流生產(chǎn)線改造

根據(jù)綜合優(yōu)先關(guān)系圖，按照關(guān)系圖中的作業(yè)元素的加工順序邏輯，一個(gè)作業(yè)元素是另外一個(gè)作業(yè)元素的緊前工序則標(biāo)注1，若不是緊前工序則標(biāo)注0，按照這樣的規(guī)則建立綜合優(yōu)先關(guān)系矩陣。

基于平衡模型和雙種群遺傳算法，matlab 編程求解，將現(xiàn)有的門(mén)體加工作業(yè)元素進(jìn)行重新分配，將各作業(yè)元素分配至固定的工作站中。

作業(yè)元素分配的結(jié)果如下：

工作站1：作業(yè)元素1→2→4

工作站2：作業(yè)元素3→5

工作站3：作業(yè)元素6

工作站4：作業(yè)元素7

工作站5：作業(yè)元素8→10→13

工作站6：作業(yè)元素9→14→12→11

工作站7：作業(yè)元素15→16

工作站8：作業(yè)元素17

3.5 改造效果

通過(guò)混流改造后，計(jì)算可得混流生產(chǎn)線的平衡率為0.859、節(jié)拍為48.16 s，平滑指數(shù)為3.375。進(jìn)行混流改造后實(shí)際生產(chǎn)節(jié)拍遠(yuǎn)低于各個(gè)型號(hào)產(chǎn)品單獨(dú)生產(chǎn)時(shí)的實(shí)際生產(chǎn)節(jié)拍，平衡率也相比于之前各產(chǎn)品單獨(dú)生產(chǎn)時(shí)有了較大幅度的提升。

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)A 公司生產(chǎn)線研究，對(duì)其生產(chǎn)線進(jìn)行混流改造，通過(guò)建立生產(chǎn)線平衡問(wèn)題，應(yīng)用雙種群遺傳算法對(duì)其進(jìn)行工序的重新編排，求解出較優(yōu)的工序安排解，改造后優(yōu)化了生產(chǎn)效率，提高了生產(chǎn)效率，

研究表明針對(duì)多樣化的產(chǎn)品，在工序以及結(jié)構(gòu)相似的情況下，進(jìn)行相同工序的合并，相似工藝結(jié)構(gòu)的產(chǎn)品合并，進(jìn)行混流改造，可以滿足客戶需求，有效地提升生產(chǎn)效率，降低企業(yè)生產(chǎn)成本。同時(shí)，利用雙種群遺傳算法對(duì)工序的重新編排，可以擴(kuò)大搜索空間，防止陷入局部最優(yōu)，對(duì)混流生產(chǎn)線平衡問(wèn)題優(yōu)化有重大意義，該方法和技術(shù)可以推廣到其他類型的混流生產(chǎn)線設(shè)計(jì)與改造上。