張家驊，李愛平

（1.同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海201804；2.無錫工藝職業(yè)技術(shù)學(xué)院機(jī)電與信息工程學(xué)院，江蘇宜興214206）

隨著社會(huì)對產(chǎn)品個(gè)性化、多樣化需求的不斷提高，企業(yè)采用混流裝配線在同一條裝配線上生產(chǎn)多種產(chǎn)品?；炝餮b配線可以降低庫存，滿足顧客的多樣化與個(gè)性化需求，縮短產(chǎn)品的上市時(shí)間，提高企業(yè)的競爭力。近年來，汽車企業(yè)開始采用混流裝配線生產(chǎn)發(fā)動(dòng)機(jī)，以應(yīng)對激烈的市場競爭［1-3］。

隨行托盤作為裝配線輔助機(jī)具，被許多發(fā)動(dòng)機(jī)企業(yè)所采用來起到輸送、定位和輔助自動(dòng)裝配發(fā)動(dòng)機(jī)的作用。為了降低投入成本，便于托盤在生產(chǎn)過程中循環(huán)使用，需要布置環(huán)形裝配線，讓托盤能回流到裝配線起始工位。在發(fā)動(dòng)機(jī)環(huán)形裝配線上，托盤數(shù)量是固定的。面對動(dòng)態(tài)、激烈的市場，企業(yè)通過開發(fā)多款發(fā)動(dòng)機(jī)共用托盤，實(shí)現(xiàn)了發(fā)動(dòng)機(jī)環(huán)形裝配線的混流生產(chǎn)。

要使混流裝配線有效運(yùn)行，混流裝配線排序是需要解決的關(guān)鍵問題之一，該問題一直是學(xué)術(shù)界和企業(yè)界的研究重點(diǎn)［4-5］。針對直線型、雙邊型和U型等混流裝配線，目前已有大量研究結(jié)果［6-8］。但這些研究均沒有考慮發(fā)動(dòng)機(jī)裝配線的實(shí)際特點(diǎn)，無法直接應(yīng)用到實(shí)際生產(chǎn)中。王炳剛［1］雖然開展了發(fā)動(dòng)機(jī)混流裝配線排序問題的研究，但只考慮緩沖區(qū)容量約束，沒有考慮托盤數(shù)量約束。由于托盤數(shù)量對閉環(huán)制造系統(tǒng)有重要影響［9］，因此該方法不能直接應(yīng)用到發(fā)動(dòng)機(jī)環(huán)形混流裝配線排序上。

為了保證發(fā)動(dòng)機(jī)環(huán)形混流配線的有效運(yùn)行，本文針對該類裝配線的排序問題開展研究，提出了一種自適應(yīng)多目標(biāo)遺傳算法和離散事件仿真相結(jié)合的多目標(biāo)排序方法。采用本方法，可以得到一組可行的產(chǎn)品投產(chǎn)排序方案，指導(dǎo)企業(yè)安排生產(chǎn)。

1 環(huán)形混流裝配線解析-仿真模型

圖1 為典型的汽車發(fā)動(dòng)機(jī)總裝配線。該線有1條環(huán)形主裝線和1條部件分裝線組成，主裝線上有1個(gè)并行設(shè)備工位，發(fā)動(dòng)機(jī)托盤在環(huán)形主裝線上進(jìn)行循環(huán)?，F(xiàn)有的混流裝配線排序方法，通過建立精確的解析模型求解可行的排序方案，但解析模型往往簡化了研究對象的復(fù)雜生產(chǎn)特點(diǎn)。對于具有固定數(shù)量托盤的環(huán)形裝配線，現(xiàn)有研究表明，只有離散事件仿真是該類裝配線最有效和最精確的研究方法［9-10］。因此，為了得到發(fā)動(dòng)機(jī)環(huán)形混流裝配線排序方案，本文通過結(jié)合離散仿真方法，建立了解析-仿真混合模型。

圖1 典型的汽車發(fā)動(dòng)機(jī)裝配線Fig.1 Classic engine assemble line

1.1 問題描述

發(fā)動(dòng)機(jī)環(huán)形混流裝配線由多個(gè)工作站和線上緩沖區(qū)組成，通過線上緩沖區(qū)將裝配線布置成環(huán)形（見圖1），裝配線上的托盤數(shù)量固定。裝配線上混合裝配P種產(chǎn)品，在一個(gè)計(jì)劃期內(nèi)，對第p（p=1，2，…，P）種產(chǎn)品的需求量為Dp，則對所有產(chǎn)品的總需求量為生產(chǎn)采用最小生產(chǎn)循環(huán)（Minimal Production Set，MPS）策略：h表示各種產(chǎn)品需求量Dp（p=1，2，…，P）的最大公約數(shù)；dp=Dp/h表示一個(gè)MPS內(nèi)生產(chǎn)產(chǎn)品p的數(shù)量為一個(gè)MPS內(nèi)個(gè)P種產(chǎn)品的總生產(chǎn)量。當(dāng)p種產(chǎn)品按照一定順序以最小生產(chǎn)循環(huán)投入裝配線時(shí)，循環(huán)次數(shù)h，即完成最終的生產(chǎn)需求。

1.2 最小化零部件消耗速率波動(dòng)

汽車行業(yè)中，為了降低庫存和減少在制品數(shù)量，關(guān)鍵零部件使用速率均勻化是準(zhǔn)時(shí)化（Just in Time，JIT）生產(chǎn)方式的基本要求［12］。最小化零部件消耗速率波動(dòng)的解析模型如下：

式中：k為第k個(gè)生產(chǎn)階段，k=1，2，…，d；r為零件的種類，r=1，2，…，R；xp，k為k個(gè)生產(chǎn)階段中產(chǎn)品p的累積量；cr，p為產(chǎn)品p需要零件r的數(shù)量；dp為第p種產(chǎn)品的需求量；sp，k為p在第k個(gè)階段生產(chǎn)sp，k=1，否則為為在前第k個(gè)產(chǎn)品零部件實(shí)際消耗率是k階段理論零部件消耗率。式（2）表示xp，k等于k個(gè)位置中產(chǎn)品p的累積量，式（3）表示在投產(chǎn)的順序中每個(gè)位置只能有一個(gè)產(chǎn)品，式（4）保證到k個(gè)階段共生產(chǎn)k個(gè)不同產(chǎn)品。

1.3 最大化生產(chǎn)率

生產(chǎn)率是評價(jià)環(huán)形生產(chǎn)線的一個(gè)重要指標(biāo)［4，14］，該目標(biāo)可以表示為

本文采用仿真模型來獲得環(huán)形混流裝配線的生產(chǎn)率，圖2為所研究的可同時(shí)生產(chǎn)三款發(fā)動(dòng)機(jī)的環(huán)形混流裝配線仿真模型。生產(chǎn)率采用的是每天的生產(chǎn)量（臺/d）。

圖2 發(fā)動(dòng)機(jī)環(huán)形混裝線仿真模型Fig.2 The model of the engine closed-loop line

仿真模型在離散事件軟件Plant Simulation 14.0中建立，其中有兩個(gè)Source對象：一個(gè)Source對象生成待裝配產(chǎn)品，一個(gè)Source對象生成安放產(chǎn)品的托盤。

2 自適應(yīng)多目標(biāo)遺傳算法

遺傳算法被認(rèn)為是求解混流裝配線排序問題的一個(gè)有效的方法［14］。為了求解上文提出的解析-仿真混合模型，本文設(shè)計(jì)了一種內(nèi)嵌離散事件仿真的自適應(yīng)多目標(biāo)遺傳算法。圖3為算法的具體流程圖。

在該算法中，染色體按照產(chǎn)品投產(chǎn)順序編碼；將生成的染色體作為離散事件仿真模型的輸入?yún)?shù)；離散事件仿真運(yùn)行仿真模型后，返回生產(chǎn)量結(jié)果，與零部件消耗速率波動(dòng)量一起進(jìn)行適應(yīng)度評估。算法的具體環(huán)節(jié)如下所述。

圖3 自適應(yīng)多目標(biāo)遺傳算法流程圖Fig.3 Flow chart of the algorithm

2.1 編碼方案和初始種群

采用整數(shù)或字母排列編碼，每一種染色體編碼方案對應(yīng)一種排序方案。將一個(gè)最小循環(huán)生產(chǎn)循環(huán)（MPS）中的產(chǎn)品品種序號用有序整數(shù)進(jìn)行標(biāo)號，每一個(gè)產(chǎn)品種類對應(yīng)一個(gè)實(shí)數(shù)，染色體中每一個(gè)基因值表示產(chǎn)品品種序號，染色體長度等于一個(gè)MPS的產(chǎn)品的總的需求量d。

例如，一個(gè)MPS中有8個(gè)3種不同品種的產(chǎn)品分別為3個(gè)品種1，3個(gè)品種2，2個(gè)品種3。品種1、品種2和品種3分別在染色體中用整數(shù)1、2、3表示，該排序方案可用圖4所示染色體表示。初始種群按照設(shè)定的種群規(guī)模，采取隨機(jī)方式生成。

圖4 染色體編碼示意圖Fig.4 Encoding scheme of a chromosome

2.2 適應(yīng)度值評估

本文共有兩個(gè)優(yōu)化目標(biāo)：一個(gè)是最小化零部件消耗速率波動(dòng)f1；一個(gè)是最大化生產(chǎn)量f2。算法采用保留最小適應(yīng)度值方法，因此，f1和f2的適應(yīng)度評估函數(shù)如下：

式中：Cmax為f2估計(jì)的最大值，經(jīng)過多次模擬獲得，本文為1 500臺/d；Fit（f1）通過適應(yīng)度函數(shù)計(jì)算獲得，F(xiàn)it（f2）由離散仿真軟件獲得。

2.3 組件對象模型（COM）技術(shù)

組件對象模型（Component Object Model，COM）提供了使多個(gè)影響程序或組件對象協(xié)同工作并互相通訊的能力。通過COM技術(shù)，可以實(shí)現(xiàn)離散仿真軟件內(nèi)嵌入混合遺傳算法程序內(nèi)，進(jìn)行數(shù)據(jù)交換。

2.4 快速非支配排序

采用Pareto分層和擁擠距離機(jī)制對非支配解集進(jìn)行排序，從而確定各個(gè)解之間的支配關(guān)系與優(yōu)先關(guān)系。

2.5 競標(biāo)賽選擇

從種群中隨機(jī)選擇2個(gè)個(gè)體，按照競標(biāo)賽規(guī)則進(jìn)行適應(yīng)值比較，適應(yīng)值較大的個(gè)體被選擇進(jìn)入下一代。

2.6 交叉與變異算子

交叉算子采用雙點(diǎn)交叉，對于第一個(gè)父代染色體P1，隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)位置，交叉點(diǎn)內(nèi)的基因位置和內(nèi)容復(fù)制給子代S1。在父代P2中從前到后刪去兩個(gè)交叉點(diǎn)內(nèi)相同內(nèi)容，然后從前到后，將P2中的基因內(nèi)復(fù)制給S1。調(diào)換P1和P2的操作，生成第二個(gè)子代S2。圖5為雙點(diǎn)交叉示意圖。

圖5 雙點(diǎn)交叉示意圖Fig.5 Scheme of two-point crossover

變異算子采用換位變異。任意選取染色體中的一個(gè)位置，將該位置的內(nèi)容與染色體內(nèi)其他位置進(jìn)行互換，完成換位變異。如圖6所示，選中的基因可以和染色中其他任意位置的基因互換。

圖6 換位變異示意圖Fig.6 Scheme of swap mutation

2.7 自適應(yīng)變異調(diào)整策略

遺傳算法容易陷入局部收斂，為了提高算法的尋優(yōu)能力，引入自適應(yīng)變異調(diào)整策略。該策略通過判斷算法的收斂程度，自動(dòng)調(diào)整變異系數(shù)。

多目標(biāo)解集S的收斂性可以用動(dòng)態(tài)收斂性指標(biāo)（CP）表示［15］：

式中：dti為解集S中的第i個(gè)解與上一代非支配解集中解T的最小Euclidean距離；CP∈［0，1］，如果CP接近0，說明算法逐漸收斂，通過增大變異概率，提高種群多樣性。本文所用自適應(yīng)變異策略如表1所示。

表1 自適應(yīng)變異策略Tab.1 Scheme of the adaptive mutation

3 實(shí)例研究

3.1 實(shí)例描述

某廠發(fā)動(dòng)機(jī)裝配車間在一條環(huán)形混裝線上混合生產(chǎn)三款分別是排量為1.0 T的3缸，和排量1.4 T、1.5 T的4缸發(fā)動(dòng)機(jī)，產(chǎn)品型號用字母A、B、C表示。裝配線由36個(gè)工位組成，采用端面摩擦積放式輥道傳送托盤；工作站間的輸送輥道還起到線上緩沖區(qū)作用；裝配線上現(xiàn)有托盤數(shù)目100個(gè)，各種發(fā)動(dòng)機(jī)在各個(gè)工作站的操作時(shí)間如表2所示，各發(fā)動(dòng)機(jī)所需要的5C件（指凸輪軸、曲軸、連桿、缸體和缸蓋）如表3所示，裝配線布局圖如圖2所示。

表2 產(chǎn)品操作時(shí)間Tab.2 Operation time of tasks s

表3 產(chǎn)品5C件需求量Tab.3 The requirement of 5C

企業(yè)下達(dá)的某次計(jì)劃MPS中A∶B∶C產(chǎn)品比例7∶5∶5，可得到該比例下車間每日裝配產(chǎn)品可能的投產(chǎn)排序方案有(7+5+5)！(7！×5！×5！)=4 900 896種。裝配車間需要在這些序列中，確定裝配線上產(chǎn)品的投產(chǎn)順序。

3.2 算法性能分析

程序采用Matlab進(jìn)行編寫，離散時(shí)間仿真軟件采用Plant Simulation 14.0。經(jīng)前期調(diào)試后，算法的參數(shù)設(shè)置如下：初始種群規(guī)模Pop=20，錦標(biāo)賽選擇競賽規(guī)模Tour=2，交叉概率Pc=0.8，初始變異概率Pm=0.2，迭代次數(shù)Mg=100，離散事件仿真模擬時(shí)間24 h。

首先分析本文提出的自適應(yīng)多目標(biāo)遺傳算法（AMOGA）的性能。圖7為隨著迭代所展現(xiàn)出的解的變化。進(jìn)化開始時(shí)，解分布在零散區(qū)域內(nèi)。隨著進(jìn)化代數(shù)的增加，解開始向前端聚集，從第10代可以看到，解已經(jīng)在前端聚集；在第90代時(shí)，解基本已經(jīng)到達(dá)前沿。從解的進(jìn)化可以看到，這兩個(gè)目標(biāo)值是相互沖突的，不能同時(shí)優(yōu)化兩個(gè)目標(biāo)。圖8將AMGOA算法的兩個(gè)適應(yīng)度值與經(jīng)典多目標(biāo)算法NSGA-II計(jì)算的兩個(gè)適應(yīng)度值的收斂曲線進(jìn)行了對比，其中NSGA-II采用了與本文相同的參數(shù)設(shè)置。圖中可見，盡管適應(yīng)度值2在兩個(gè)算法中都收斂到相同的最優(yōu)值，但是適應(yīng)度值1采用本文的算法可以收斂到最小值100，而NSGA-II智能收斂到105，這是由于本文算法通過自適應(yīng)變異策略，避開了局部最優(yōu)，提高了算法的搜索性能。

圖7 不同算法的Pareto結(jié)果比較Fig.7 Comparison of Pareto results of different algorithms

圖8 不同算法的適應(yīng)度值的收斂趨勢Fig.8 Convergence of fitness of algorithms

3.3 結(jié)果分析

從表4中可以看到，零部件消耗速率波動(dòng)量最小的是方案1，生產(chǎn)量最大的是方案9，兩個(gè)目標(biāo)是互相沖突的，為了提高生產(chǎn)率，需要犧牲零部件消耗速率的波動(dòng)量。但在表中可發(fā)現(xiàn)，如果生產(chǎn)量低于1 151臺/d，零部件消耗速率波動(dòng)量會(huì)下降到150以下。即，如果生產(chǎn)率下降0.8%，零部件消耗速率波動(dòng)會(huì)降低56.05%。這個(gè)結(jié)論對安排生產(chǎn)有指導(dǎo)作用。

表4 托盤數(shù)目100個(gè)約束下的排序方案Tab.4 Sequencing results under pallet=100

4 結(jié)語

本文針對具有固定托盤數(shù)量的發(fā)動(dòng)機(jī)環(huán)形混流裝配線排序問題，提出了一種自適應(yīng)多目標(biāo)遺傳算法和離散事件仿真相結(jié)合的多目標(biāo)排序方法。通過對算法引入自適應(yīng)變異調(diào)整策略，克服了傳統(tǒng)算法結(jié)果容易陷入局部最優(yōu)的問題，提高了算法的尋優(yōu)能力，改善了解的質(zhì)量。該方法克服了純解析模型不能考慮固定托盤數(shù)目約束的建模難點(diǎn)，能指導(dǎo)企業(yè)更好制定環(huán)形混流生產(chǎn)線的投產(chǎn)排序問題。