高振豪++蘇貴影++余燕尾

摘 要：個(gè)性化需求的出現(xiàn)，致企業(yè)多品種、小批量的裝配線平衡出現(xiàn)失調(diào)問(wèn)題。針對(duì)第Ⅱ裝配線平衡問(wèn)題，分析成組技術(shù)與最小節(jié)拍的對(duì)應(yīng)關(guān)系，結(jié)合成組技術(shù)、遺傳算法建立數(shù)學(xué)模型，按照遺傳算法進(jìn)行編碼、譯碼、構(gòu)造適應(yīng)函數(shù)。成組技術(shù)問(wèn)題是組合優(yōu)化問(wèn)題，而遺傳算法正是目前求解組合最優(yōu)化的有效方法之一。因此，文章將成組技術(shù)與遺傳算法相融合，提出了一種基于遺傳算法的工序成組方法。

關(guān)鍵詞：第Ⅱ類(lèi)裝配線；遺傳算法；負(fù)荷平衡；成組技術(shù)

中圖分類(lèi)號(hào)：F253.9 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： The emergence of personalized demand， resulting in multi-species， small batch of assembly line balance imbalance problem. Aiming at the balance problem of the second assembly line， the correspondence between the group technology and the minimum beat is analyzed. Combining the grouping technique and the genetic algorithm to establish the mathematical model， the genetic algorithm is used to encode， decode and construct the adaptive function. Group technology is a combinatorial optimization problem， and genetic algorithm is one of the effective methods to solve the combinatorial optimization. Therefore， this paper combines group technology with genetic algorithm， and proposes a process grouping method based on genetic algorithm.

Key words： class Ⅱ assembly line； load balancing； genetic algorithm； group technology

0 引 言

對(duì)于日新月異的社會(huì)發(fā)展，隨之企業(yè)的裝配線負(fù)荷平衡就成為瓶頸問(wèn)題。裝配線的失衡會(huì)嚴(yán)重造成企業(yè)生產(chǎn)效率大大降低，裝配線負(fù)荷平衡可以有效解決工人、機(jī)器等待問(wèn)題，并使工作站之間負(fù)荷均衡，以保證生產(chǎn)效率的提高。從根本上講，裝配線平衡就是組合優(yōu)化問(wèn)題，但是該問(wèn)題涉及到產(chǎn)品設(shè)計(jì)研發(fā)和制造過(guò)程，這也就決定工作站先后順序以及作業(yè)元素邏輯關(guān)聯(lián)。市場(chǎng)需求多樣性的變化對(duì)裝配線的柔性要求增強(qiáng)，但在實(shí)際生產(chǎn)過(guò)程中由于工序的排列不合理、工作站負(fù)荷不均衡等一些因素導(dǎo)致裝配線不能順暢進(jìn)行。針對(duì)裝配線平衡目標(biāo)的不同，單一型裝配線平衡分四種：第Ⅰ類(lèi)：已知裝配線節(jié)拍C，優(yōu)化工作站數(shù)N；第Ⅱ類(lèi)：已知裝配線工作站數(shù)N，優(yōu)化節(jié)拍T；第Ⅲ類(lèi)：已知裝配線工作站數(shù)N，優(yōu)化均衡指數(shù)SI；第Ⅳ類(lèi)：已知裝配線工作站數(shù)N，優(yōu)化相關(guān)指數(shù)SN。

裝配線平衡（Assembly Line Balance，ALB）是個(gè)組合優(yōu)化問(wèn)題，屬于典型的NP-hard問(wèn)題，到目前為止沒(méi)有公認(rèn)的最優(yōu)算法。Salveson[1]首次提出ALB的線性規(guī)劃模型；Dooyoung[2]采用0-1整數(shù)規(guī)劃同時(shí)優(yōu)化裝配線工作站節(jié)拍問(wèn)題；Tonge[3]提出了一種啟發(fā)式算法優(yōu)化裝配線；Rubinovitz[4]等人研究了結(jié)合啟發(fā)式算法的裝配線平衡的遺傳算法。不過(guò)上述算法多為理論值，沒(méi)有完全結(jié)合實(shí)際狀況，導(dǎo)致可信度差；采用單純的遺傳算法（Genetic Algorithm，GA）優(yōu)化裝配線平衡問(wèn)題，因不滿足實(shí)際約束的可行解使最優(yōu)解不可行。

本文提出了一種結(jié)合成組技術(shù)的遺傳算法來(lái)優(yōu)化第Ⅱ類(lèi)裝配線的數(shù)學(xué)模型，運(yùn)用工序成組結(jié)合傳統(tǒng)的遺傳算法，既保留了原始遺傳算法的空間搜索能力又僅在可行解空間搜索。本文針對(duì)第Ⅱ類(lèi)裝配線采用該方法進(jìn)行優(yōu)化。

1 遺傳算法

遺傳算法（GA）是Holland受自然界生物進(jìn)化論啟發(fā)而提出來(lái)的，它是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局化概率搜索算法。隨著GA的開(kāi)啟可以克服啟發(fā)式方法的規(guī)則困難，同時(shí)提出了一種新的有效決策支持工具，而之前啟發(fā)式方法的產(chǎn)生主要是因?yàn)楝F(xiàn)實(shí)建模的需求但沒(méi)有萬(wàn)能的啟發(fā)式規(guī)則。GA依一定的概率進(jìn)行全局搜索，并且可以較大概率求得最優(yōu)解，GA過(guò)程中的適應(yīng)度函數(shù)的選擇，編碼和譯碼規(guī)則對(duì)裝配線平衡都有影響，鑒于此本文采用工序成組的非標(biāo)準(zhǔn)遺傳算子，保證解的可行性，同時(shí)采取最優(yōu)策略避免最優(yōu)解的丟失，其可定義為8元組[5]：

GA=（C，E，P ，M，Φ，Γ，ψ，T），T） （1）

上述式中8元組依次表示個(gè)體編碼方法、適應(yīng)度函數(shù)、群體范圍、選擇算子、交叉算子、變異算子、終止條件，本文處理每個(gè)單元的規(guī)則將結(jié)合裝配線實(shí)際情況具體操作。

2 設(shè)計(jì)裝配線遺傳算法模型

裝配線平衡（ALB）問(wèn)題的研究就是產(chǎn)品裝配過(guò)程中每個(gè)工作站工序的分配，使其作業(yè)元素按照一定的裝配操作順序進(jìn)行裝配，運(yùn)用遺傳算法（GA）就是每個(gè)工作站的工時(shí)接近節(jié)拍T或者差距最小。因此分配工序任務(wù)時(shí)需要降低工作站之間的空閑時(shí)間，平衡其作業(yè)時(shí)間。在運(yùn)用GA時(shí)需要結(jié)合實(shí)際約束，這些約束用數(shù)學(xué)表達(dá)如下：

（1）S ∪S ∪…S =D k=1，2，…，m；——工作站中工序的約束。

（2）S ∩S =φ i≠j；i，j=1，2，…，m；——工作站之間工序的約束。

（3）TS ≤T k=1，2，…，m；——工作站時(shí)間與節(jié)拍的約束。

（4）若M =1， i∈S ， j∈S ， 則x≤y， M=M 為優(yōu)先矩陣；——工序順序約束。

D表示工序集合，M表示工作站數(shù)k=1，2，…，m，S 表示第i個(gè)工作站工序集合。上述為裝配線基本約束，目標(biāo)一般就是衡量裝配線的指標(biāo)，盡量減少工作站之間的空閑時(shí)間，最終達(dá)到每個(gè)工作站總工時(shí)均衡，提升生產(chǎn)效率。

2.1 成組工序的裝配線遺傳算法模型

本文主要針對(duì)成組工序的第Ⅱ類(lèi)裝配線平衡問(wèn)題進(jìn)行研究[6]，運(yùn)用成組技術(shù)將工序集中分類(lèi)安排，使節(jié)拍T最小化，工序相似度最大，提高裝配線效率。用數(shù)學(xué)模型描述該裝配線問(wèn)題如下：

w 為某一個(gè)工序的某一特征的權(quán)重系數(shù)；x為工序代號(hào)；k為零件的特征要素?cái)?shù)，k=1，2，…，s；i，j為待分類(lèi)的工序數(shù)，i，j

=1，2，…，m；針對(duì)工序成組特征本文選取5M1E（人，機(jī)，料，法，測(cè)，環(huán)）六個(gè)方面，每個(gè)特征方面依據(jù)工藝及工作站要求賦予權(quán)重。權(quán)重系數(shù)反應(yīng)每個(gè)工序之間的相似度，需要滿足歸一條件，即∑wx =1k=1，2，…，6。余弦值越接近1，就表明夾角越接近0度，也就是兩個(gè)工序越相似，夾角等于0，即兩個(gè)工序相等。

2.2 編 碼

遺傳算法的優(yōu)化結(jié)果受編碼規(guī)則的影響，在實(shí)際裝配線生產(chǎn)過(guò)程中約束較多，一般的二進(jìn)制編碼會(huì)影響整個(gè)算法的每一步，因此在這里并不適用，所以需要選擇特殊的編碼方式。針對(duì)裝配線平衡問(wèn)題，由于受裝配線工序先后順序以及工藝設(shè)計(jì)的約束，所以可用裝配工序圖表示現(xiàn)有的流程制造。圖1是某裝配線的工序流程約束圖，連接點(diǎn)的弧表示工序順序，節(jié)點(diǎn)上方數(shù)字表示工序時(shí)間，裝配線的排列順序也就是成為一種優(yōu)化組合問(wèn)題，使工序先后邏輯順序編碼符合實(shí)際約束更為簡(jiǎn)單[7]。在排列工序時(shí)應(yīng)結(jié)合成組技術(shù)，按照工序的相似度進(jìn)行配列，最大可能分配同一個(gè)工作站，提高裝配線作業(yè)效率，降低工序之間的空閑時(shí)間。因此，本文采用工序成組的方法對(duì)染色體進(jìn)行編碼，每個(gè)工序?qū)?yīng)一個(gè)基因，每個(gè)工作站對(duì)應(yīng)一段基因位，按順序排好。圖2為圖1工序約束圖下的一個(gè)染色體。每個(gè)工作站的總工時(shí)不能超過(guò)節(jié)拍T。

2.3 譯 碼

編碼后的染色體要按照一定的規(guī)則進(jìn)行譯碼，該過(guò)程是將工序編碼表示的染色體（成組工序）中的每個(gè)基因（工序）順序分配各個(gè)工作站。在工作站給定的情況下，依據(jù)染色體中工序號(hào)順序最小化節(jié)拍T（最大化生產(chǎn)效率P）和工序的相似度最大[8]。首先在給定滿足工作站數(shù)的條件下，依照染色體的工序號(hào)，運(yùn)用模糊聚類(lèi)分析法——夾角余弦法對(duì)每個(gè)工序進(jìn)行分類(lèi)，再依據(jù)給定的工作站數(shù)以及工藝要求進(jìn)行分配，然后依據(jù)工作站上所分配工序求其時(shí)間。在此過(guò)程需要滿足以下條件：

（1）每個(gè)工作站的工時(shí)不能超過(guò)節(jié)拍時(shí)間，即TS ≤T；

（2）一個(gè)工序只能分配一個(gè)工作站；

（3）考慮到節(jié)拍的約束，若一個(gè)工序不能被分配到工作站，但該工序的緊后工序可以分配，則該工序優(yōu)先分配到工作站。

在譯碼過(guò)程需要借助平衡指數(shù)SI= 來(lái)衡量成組工序分配情況，即∑s 值的合理性。

2.4 適應(yīng)函數(shù)的構(gòu)造

由于該適應(yīng)函數(shù)是求極大值的過(guò)程，但是平衡指數(shù)是極小值問(wèn)題，因此需要進(jìn)一步轉(zhuǎn)化SI也為極大值。本文借助指數(shù)函數(shù)構(gòu)造適應(yīng)函數(shù)如下：

fi= +e

其中：SI= ，因此就有指數(shù)函數(shù)越小，相似度越大，節(jié)拍越小的染色體使適應(yīng)函數(shù)越大。

2.5 初始群體的選取

為保持最優(yōu)解的可行性和計(jì)算結(jié)果的精確性，本文采取的可行解都是在裝配線可操作的工序條件下進(jìn)行篩選。因此依據(jù)工序流程圖采用圖論中隨機(jī)拓?fù)渑判蚍椒ㄉ沙跏既后w，具體步驟如下：

（1）使當(dāng)前初始化染色體序列為空；

（2）隨機(jī)從工序流程圖中選擇一個(gè)無(wú)緊前工序安插在當(dāng)前序列尾部；

（3）在圖中刪除該節(jié)點(diǎn)以及所連接的邊，若已無(wú)節(jié)點(diǎn)則輸出當(dāng)前作業(yè)序列，否則轉(zhuǎn)（2）。

成組工序順序的輸出是建立在裝配線實(shí)際情況之上，可排列組合出新的成組工序，并生成初始群體。

2.6 選擇策略的確定

因需要適應(yīng)值較大的個(gè)體保留在群體中，本文采用確定式采樣選擇方法（Deterministic Simpling）。其具體操作過(guò)程如下：

（1）群體中每個(gè)個(gè)體在下一代中期望生存數(shù)目N ： N =M i=1，2，…，M。

（2）用N 的整數(shù)部分 N 確定每個(gè)對(duì)應(yīng)個(gè)體在下一代群體中生存數(shù)目，其中 N 表示取不大于x的最大整數(shù)。由該步可確定下一代群體中的∑ N 個(gè)個(gè)體。

（3）按照N 的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排列，順序取前M-∑ N 個(gè)個(gè)體加入到下一代群體中，至此完全確定出下一代群體中的M個(gè)個(gè)體，保持總的群體數(shù)量不變。

上述的選擇方法保證了較大的適應(yīng)群體被保留，避免最優(yōu)解流失，也就是最優(yōu)的可行性解的保留。

2.7 交叉和變異準(zhǔn)則

單點(diǎn)交叉算子（One-point Crossver）：它是指?jìng)€(gè)體編碼隨機(jī)選取某個(gè)交叉點(diǎn)，然后互換該點(diǎn)后的部分染色體，是一種最常用和最基本的一個(gè)交叉方式。由于初始群體是可行解，經(jīng)過(guò)單點(diǎn)交叉后產(chǎn)生的新一代個(gè)體也是可行解。初始群體具體操作方式如下：

（1）初始群體中隨機(jī)選取兩個(gè)進(jìn)行配對(duì)。若該群體數(shù)量為M，則有 M/2 對(duì)進(jìn)行配對(duì)；

（2）對(duì)于每個(gè)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某基因后的位置為交叉點(diǎn)。若染色體長(zhǎng)度為n，則共有n-1個(gè)交叉點(diǎn)數(shù)[9]；

（3）依據(jù)設(shè)定的交叉率（一般0.4～0.99）進(jìn)行交叉互換部分基因，從而產(chǎn)生兩個(gè)新的個(gè)體。

用上面兩個(gè)染色體說(shuō)明單點(diǎn)交叉操作，隨機(jī)選取交叉點(diǎn)：position 1=5，產(chǎn)生的新個(gè)體見(jiàn)圖3。

基本位變異算子（Simple Mutation）：依據(jù)變異率p 對(duì)當(dāng)前染色體上基因位進(jìn)行變異操作，本文為保證可行解的持續(xù)，采用位移變異方式。隨機(jī)選擇一個(gè)關(guān)系進(jìn)行變異操作，將其插入約束條件下的任意位置，而它的緊隨工序按照原來(lái)的順序排列，這也就保證了變異后的可行解持續(xù)性[10]。取工序6進(jìn)行變異，將其插入第十個(gè)位置，則8，10，7，9工序向前平移一個(gè)位置，工序11位置保持不變。具體操作過(guò)程如圖4：

2.8 終止代數(shù)

鑒于本文工序數(shù)目較少，終止代數(shù)取100，即進(jìn)化100代后結(jié)束運(yùn)算。

3 實(shí)例分析

基于第Ⅱ類(lèi)裝配線結(jié)合遺傳算法的敘述，本文采用仿真軟件Matlab2016a基于處理器為Intel（R）Core（TM）i5-4256U/2.4GHz，操作系統(tǒng)為64位四核window10平臺(tái)進(jìn)行模擬，交叉概率0.8，變異概率0.2。選取一條十一個(gè)工序四個(gè)工作站的裝配線為例，其總工時(shí)為46s，優(yōu)化結(jié)果如表1至表3：

目前裝配線平衡率P =P =P = =95.83%；minT為11S；均衡指數(shù)SI = =1.4；SI =SI

= =2即SI

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

針對(duì)第Ⅱ類(lèi)裝配線工序相關(guān)因素（5M1E）分析，提出了成組工序的作業(yè)序列，在此基礎(chǔ)運(yùn)用遺傳算法。該方法既保留了原有的GA遺傳算法搜索能力，又依據(jù)實(shí)際情況選擇初始群體和構(gòu)造交叉算子、變異算子，重要的是只在可行解范圍內(nèi)進(jìn)行搜索最優(yōu)可行解。交叉算子一般取0.4～0.99，變異過(guò)程中算子的隨機(jī)選取范圍0.3～0.5。在適應(yīng)度函數(shù)方面考慮了各個(gè)工序之間的相似度和裝配線的平衡率以及平衡指數(shù)，可以用來(lái)比較不同工作站內(nèi)工序相似度，增加工序的聚集度，提高工作效率。由于本算法中的相似度根據(jù)5M1E需要賦予相應(yīng)的權(quán)重，該過(guò)程會(huì)涉及到主管因素，所以在結(jié)果上會(huì)產(chǎn)生差異性，結(jié)合實(shí)例可見(jiàn)該算法以及相關(guān)指數(shù)還是取得相對(duì)滿意的結(jié)果。本文的成組工序遺傳算法的提出，為提高裝配線效率和改進(jìn)裝配線技術(shù)提出了參考依據(jù)。

參考文獻(xiàn)：

[1] Salveson M E. The assembly line balancing problem[J]. Journal of industrial Engineering， 1955，6（3）：18-25.

[2] Dooyoung Shim， Hobey Min. Flexible Line balancing practices in a just-in-timeenvionment[J]. Production and inventory management Journa1， 1991（4）：38-41.

[3] Tonge F M. Summary of a Heuristic line balancing Procedure[J]. Management Science， 1960，7（11）：21-42.

[4] Levitin， Rubinovitz， Jacob， et al. A genetic algorithm for robotic assemblyline balancing[J]. European Journal of Operational Research， 2006，168（3）：811-825.

[5] 周明，孫樹(shù)棟. 遺傳算法原理及應(yīng)用[M]. 北京：國(guó)防工業(yè)出版社，1999：19-20.

[6] 皮興忠，范秀敏，嚴(yán)雋琪. 用基于可行作業(yè)序列的遺傳算法求解第二類(lèi)裝配線平衡問(wèn)題[J]. 上海交通大學(xué)學(xué)報(bào)，2005，39（7）：1123-1127.

[7] 朱會(huì)霞，王福林，張勇，等. 改進(jìn)遺傳算法優(yōu)化非線性規(guī)劃問(wèn)題[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013（7）：117-125.

[8] 梁燕，金燁. 基于工位約束快速啟發(fā)式算法的混合裝配線分段優(yōu)化[J]. 上海交通大學(xué)學(xué)報(bào)，2007，41（9）：1501-1505.

[9] 鞠彥兵，李桂芬，王愛(ài)華. 基于遺傳算法的車(chē)間作業(yè)計(jì)劃仿真研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2006（10）：79-85.

[10] 吳君華，夏巨諶，曹山河. ALB問(wèn)題的數(shù)學(xué)模型及其優(yōu)化算法的研究[J]. 系統(tǒng)學(xué)報(bào)，1999，11（5）：358-361.

[11] 王麗穎，孫麗，王秀倫. 基于虛擬工序的小批量工序質(zhì)量控制方法研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2006，12（8）：1263-1266.

[12] 郭勝會(huì)，楊育，邢青松，等. 基于聯(lián)合作業(yè)序列的遺傳算法求解第二類(lèi)裝配線平衡問(wèn)題[J]. 機(jī)械，2011，11（38）：42-47.