基于JIT的多車間混流裝配計劃排序問題*

徐 兵，陶麗華，胡月梅

（長春工業(yè)大學(xué)機電工程學(xué)院，長春 130012）

基于JIT的多車間混流裝配計劃排序問題*

徐 兵，陶麗華，胡月梅

（長春工業(yè)大學(xué)機電工程學(xué)院，長春 130012）

為使JIT生產(chǎn)模式下多車間混流裝配線敏捷、高效地運行，研究了具有供需關(guān)系的多車間混流裝配線計劃排序問題。以JIT車間混流裝配線上車型切換次數(shù)、關(guān)鍵件型號切換次數(shù)、車身噴涂顏色變化和違反選裝件的選裝頻率次數(shù)最少為優(yōu)化目標(biāo)，采用加權(quán)平均法建立了多目標(biāo)優(yōu)化數(shù)學(xué)模型。針對遺傳算法容易陷入局部最優(yōu)和提前收斂的問題，提出了求解多車間混流裝配計劃排序的自適應(yīng)遺傳算法。通過交叉概率和變異概率的自適應(yīng)調(diào)整、局部尋優(yōu)和保優(yōu)策略，提高了算法的尋優(yōu)能力。最后通過算例驗證了算法的有效性。

多車間；混流裝配；計劃排序

0 引言

JIT生產(chǎn)模式以高效率、低在制、消除中斷和浪費而被越來越多的混流裝配企業(yè)所采用，它可以在基本不改變生產(chǎn)組織方式的前提下滿足用戶的多樣化需求，具有很高的靈活性。混流裝配生產(chǎn)模式已被越來越多的大型汽車制造企業(yè)所采用，與之相關(guān)的投產(chǎn)計劃排序問題也日益成為研究的熱點［1-3］。邵新宇［4］提出了基于部分屬性序列的多車間計劃排序問題。董義軍［5］研究了面向ATP、沒有供需關(guān)系的多工廠協(xié)同再調(diào)度問題。蘇生［6］提出了多個沒有供需關(guān)系的多工廠集成的計劃調(diào)度問題。鄭敏［7］研究了總裝線線邊物料消耗速率波動均衡、子裝配工負荷均衡和涂裝車間顏色切換問題。黃岡［8］提出了具有排序功能緩沖區(qū)的焊裝車間、涂裝車間、總裝車間計劃排序數(shù)學(xué)模型。但是，無論是數(shù)學(xué)建模還是算法研究對JIT生產(chǎn)要求的多車間協(xié)同的計劃排序問題考慮的較少。

在JIT生產(chǎn)模式下，一汽解放卡車廠焊裝車間、涂裝車間和總裝車間的生產(chǎn)工藝各不相同，其排序優(yōu)化目標(biāo)存在較大差異，甚至出現(xiàn)沖突，如果完全讓各車間獨立制定各自的排序計劃，必然會導(dǎo)致車間之間的物料供應(yīng)不上而影響日生產(chǎn)計劃的完成。因此，文章主要根據(jù)一汽解放卡車廠多車間一個流的JIT生產(chǎn)需求，假定協(xié)調(diào)總裝車間與各關(guān)鍵件分裝線生產(chǎn)平衡的日生產(chǎn)計劃已制訂，研究日生產(chǎn)計劃的優(yōu)化排序問題。

1 多車間混流裝配計劃排序模型

1.1 問題描述

一汽解放卡車的生產(chǎn)具有多品種小批量的特點，卡車的生產(chǎn)過程依次要經(jīng)過焊裝車間和涂裝車間，最后進入總裝車間完成整車裝配。為了提高各車間的生產(chǎn)效率，需要解決以下問題：

（1）在焊裝車間車型的改變需要一系列的生產(chǎn)準(zhǔn)備時間調(diào)整車身坐標(biāo)，因此，焊裝線要求盡量減少車型的變化。

（2）在涂裝車間當(dāng)兩個連續(xù)生產(chǎn)的卡車被噴成不同顏色時，必須用油漆清洗劑對噴槍進行一次徹底地清洗［9］，當(dāng)顏色變化頻繁時，不僅浪費時間，還浪費資源。因此，要求盡量將相同顏色的車排列在一起，以減少車身顏色的變化。

（3）在總裝車間，由于選裝件需要耗費操作者較長時間，如果連續(xù)裝配某種選裝件過多，會導(dǎo)致操作者疲勞，造成生產(chǎn)任務(wù)難以完成，甚至導(dǎo)致整個生產(chǎn)線停線。每種選裝件都設(shè)定一個選裝頻率，為了實現(xiàn)選裝件的生產(chǎn)負荷平衡，計劃排序必須要盡量滿足所有選裝件的選裝頻率，以提高總裝線的生產(chǎn)負荷均衡要求。另一方面，隨著總裝配線上關(guān)鍵件型號的切換次數(shù)的增加，錯、漏裝問題隨之而來，因此，總裝配線要盡量減少關(guān)鍵件型號的切換次數(shù)。

為了保證一汽解放卡車廠日生產(chǎn)計劃的順利完成，實現(xiàn)混流裝配的均衡化和準(zhǔn)時化，焊裝車間、涂裝車間和總裝車間需采用一個生產(chǎn)序列。因此，生產(chǎn)計劃排序不僅要考慮總裝車間的生產(chǎn)負荷平衡問題，還要考慮涂裝車間和焊裝車間生產(chǎn)效率的優(yōu)化，最大限度地建立一個平衡的生產(chǎn)系統(tǒng)，實現(xiàn)一個流的生產(chǎn)，提高整車的生產(chǎn)效率。

1.2 符號定義

JIT生產(chǎn)方式下，一汽解放卡車多車間混流裝配的前提條件為：

（1）根據(jù)日生產(chǎn)計劃，假定日生產(chǎn)不同型號的卡車共n輛，每輛車都具有型號、顏色屬性，n輛車的所有可能排產(chǎn)序列的集合為X，x∈X表示某一具體計劃排產(chǎn)序列，即x=（x1，x2，…xj…，xn），1≤j≤n，簡稱為排序x，xj表示排產(chǎn)序列x中的第j輛車。

（2）每一種車型都由0個或多個選裝件、若干關(guān)鍵件組成。每輛車只能為一種車型，噴涂一種顏色。每一種配置方案包括車的型號定義和顏色定義，即每一配置方案對應(yīng)一種具體的車型和一種具體的顏色。

（3）裝配生產(chǎn)中所涉及的零部件分為兩類，第一類是選裝件零部件，這類零部件僅在一部分型號的產(chǎn)品選配，第二類關(guān)鍵件零部件，所有產(chǎn)品均需要裝配此類零件，但不同型號的產(chǎn)品裝配該類零部件可能型號不同。

根據(jù)以上假設(shè)條件，定義如下參數(shù)：O：選裝件集合，o∈O表示某選裝件；

K：關(guān)鍵件集合，k∈K表示某關(guān)鍵件；

F：噴涂顏色集合，f∈F表示一種顏色；

T：車型的集合，t∈T表示一種車型；

P：配置方案的集合，p∈P表示某一種配置方案；

No：Mo表示選裝件o的選裝頻率，表示在生產(chǎn)序列x中的任意Mo個連續(xù)的車輛中，至多只能有No輛車裝配選裝件o。

定義以下0-1變量：

1.3 多車間混流裝配線數(shù)學(xué)模型

依據(jù)1.2節(jié)的定義，根據(jù)焊裝車間、涂裝車間和總裝車間計劃排序的要求，分別建立各車間生產(chǎn)計劃排序的優(yōu)化目標(biāo)，最后采用加權(quán)平均法建立JIT生產(chǎn)模式下的總裝車間計劃排序數(shù)學(xué)模型。

定義車型的變化次數(shù)為Z1，為了滿足焊裝車間盡量減少車型變化的需求，生產(chǎn)計劃排序x的優(yōu)化目標(biāo)為式（1）。

其中，式（2）表示每一個排序位置只能為某一種車型。式（3）表示每一排序位置只能為某一種配置方案。式（4）表示在排序x中若某一位置車型發(fā)生變換時記為1，否則為0。

定義車身噴涂顏色的變化次數(shù)為Z2，假定噴涂車間連續(xù)噴涂同種顏色車的能力足夠大。為了滿足涂裝車間盡量減少車身顏色變化的次數(shù)，計劃排序x的優(yōu)化目標(biāo)為（5）。

其中，式（6）表示每一位置只能噴涂某一種顏色。式（7）表示i位置車輛是否噴涂f顏色，若bfi為1，表示i位置噴涂f顏色；若bfi為0，表示i位置不噴涂f顏色。式（8）表示在排序x中某一位置發(fā)生顏色變換時zfi記為1，否則為0。

定義總裝配線違反選裝件選裝頻率的次數(shù)為Z3，為了滿足總裝車間各選裝件的選裝頻率，生產(chǎn)計劃排序x的優(yōu)化目標(biāo)為（9）。

式（10）表示每輛車只能有一種配置方案。式（11）表示i位置車輛的配置方案中是否包括選裝件o，1表示i位置車輛配置方案包括o選裝件；0表示i位置車輛配置方案不包括o選裝件。式（12）表示在排序x中從j位置開始的連續(xù)M0輛車違反o選裝件選裝頻率的次數(shù)。

定義總裝配線關(guān)鍵件型號切換的次數(shù)為Z4，為了滿足總裝車間盡量減少關(guān)鍵件型號變化的需求，生產(chǎn)計劃排序x的優(yōu)化目標(biāo)為（13）。

在JIT生產(chǎn)模式下，一汽解放卡車總裝配線生產(chǎn)計劃的優(yōu)化要盡量滿足式（1）、式（5）、式（9）和式（13）各目標(biāo)，是一種多目標(biāo)的優(yōu)化排序。加權(quán)法以其簡單易行、計算過程無需人工干預(yù)的特點廣泛應(yīng)用于多目標(biāo)求解問題。采用加權(quán)平均法確定生產(chǎn)計劃優(yōu)化排序總目標(biāo)如式（14）所示。

其中，wi分別為各目標(biāo)Zi的權(quán)重。由于違反選裝件頻率會引起操作者疲勞，導(dǎo)致總裝線停線，因此，Z3目標(biāo)比其它目標(biāo)重要它是保證卡車總裝配線正常運行的關(guān)鍵。而噴涂顏色的變化主要影響噴涂效率和成本，車型的變化及關(guān)鍵件型號切換導(dǎo)致錯裝和漏裝情況可通過智能識別等手段克服。因此，Z2比Z1和Z4目標(biāo)重要，本文采用層次分析法確定各目標(biāo)的權(quán)重如表1所示。

表1 各目標(biāo)的重要程度及權(quán)重

2 混流裝配計劃排序的自適應(yīng)遺傳算法

混流裝配計劃排序問題屬于組合優(yōu)化問題中的NP難題，遺傳算法（GA）對求解這類問題提供了有效手段。由于基本遺傳算法容易陷入局部最優(yōu)和提前收斂，文章采用自適應(yīng)遺傳算法［10］求解第1節(jié)提到的混流裝配計劃排序問題，通過自適應(yīng)交叉和自適應(yīng)變異可提高最優(yōu)解的搜索能力；通過局部尋優(yōu)和保優(yōu)策略可及時將優(yōu)良個體保存起來，以避免遺傳算法的提前收斂?；炝餮b配計劃排序的自適應(yīng)遺傳算法流程如圖1所示。

圖1 JIT作業(yè)排序自適應(yīng)遺傳算法流程

（1）編碼。將每種車型及其對應(yīng)的顏色作為一種配置方案用唯一的自然數(shù)作為配置號表示，車型和顏色都相同的車配置號是相同的。采用整數(shù)編碼，以生產(chǎn)計劃的序列作為染色體，配置號作為基因，在解碼時可以直接根據(jù)染色體進行解碼，方便適應(yīng)度值的計算。

（2）初始種群。隨機改變?nèi)旧w中基因的順序生成初始種群。

（3）適應(yīng)度函數(shù)。為了避免算法提前收斂，在遺傳的初期，為了增加種群中下一代個體的多樣性，限制高適應(yīng)度個體的復(fù)制數(shù)量，應(yīng)降低適應(yīng)度的幅度，以降低種群中個體適應(yīng)度的差異程度；在遺傳操作的后期，為了提高個體之間的競爭性，以便于對最優(yōu)解的進一步搜索，需要對適應(yīng)度幅度適當(dāng)拉伸，放大個體間適應(yīng)度的差異，因此，適應(yīng)度函數(shù)依據(jù)式（14）和遺傳代數(shù)設(shè)計為式（15），其中g(shù)en為當(dāng)前的遺傳代數(shù)。

（4）選擇。采用輪盤賭方法選擇繁殖個體?？刂泼看蟹N群被替換的比例（代溝）為90%，種群中的10%較優(yōu)個體直接作為繁殖個體。

（5）自適應(yīng)交叉概率和自適應(yīng)變異概率。交叉概率Pc和變異概率Pm選擇過大，利于新個體的產(chǎn)生，但易破壞種群中的優(yōu)良個體；而選擇太小，不利于新個體的產(chǎn)生，影響問題的進一步求解，難于搜索到最優(yōu)解。因此文章根據(jù)個體的適應(yīng)度設(shè)計Pc、Pm。對于每代的精英個體，即適應(yīng)度等于該代種群的最大適應(yīng)度的個體，設(shè)計Pc、Pm為0，對于適應(yīng)度小于精英個體而大于平均適應(yīng)度的個體，以及小于等于平均適應(yīng)度的個體，分別采用自適應(yīng)Pc和Pm，根據(jù)適應(yīng)度函數(shù)（15）設(shè)計自適應(yīng)交叉概率Pc和自適應(yīng)變異概率Pm如式（16）和式（17）所示。其中，Pac、Pam為適應(yīng)度等于平均適應(yīng)度的個體的交叉概率和變異概率，Plc、Plm適應(yīng)度大于平均適應(yīng)度或小于平均適應(yīng)度的個體相對Pac、Pam的適應(yīng)度變化的最大幅度值；Favg為平均適應(yīng)度值，F(xiàn)max為最大適應(yīng)度值，F(xiàn)min為最小適應(yīng)度值，F(xiàn)為兩個待交叉?zhèn)€體中較高個體的適應(yīng)度值。

（6）交叉方法。在配對的父染色體A1和A2中隨機選取一個交叉位，將A1交叉位置及左側(cè)的基因值作為子染色體A1′對應(yīng)位置的基因值，并在配對的另一個父染色體A2中隨機刪除這些基因值；然后，將父染色體A2中的基因從左向右依次填入子染色體A1′中的空白基因位。同理可得到子染色體A2′。其操作實例如圖1所示。

圖1 交叉操作實例

（7）變異。采用變換變異法，即在父染色體中隨機選取兩個基因位，交換其基因值。

（8）局部優(yōu)化。為了提高遺傳算法的局部搜索能力，對每代遺傳操作后生成的染色體，若該染色體的適應(yīng)度小于最優(yōu)個體的適應(yīng)度，還需通過數(shù)次反轉(zhuǎn)變異法基于該染色體進行局部搜索。方法是隨機選取該染色體中兩個基因位，然后將其之間的子基因串反轉(zhuǎn)，若反轉(zhuǎn)后的染色體的適應(yīng)度大于該染色體的適應(yīng)度，則用反轉(zhuǎn)后的染色體替換該染色體，否則，該染色體不變，直到滿足反轉(zhuǎn)的次數(shù)為止。通過局部搜索，可以提高后代染色體的質(zhì)量。

（9）保優(yōu)策略。為了防止遺傳進化過程中最優(yōu)個體的丟失，在每代進行遺傳操作后，若種群中的最佳個體比最優(yōu)個體好，則將該最佳個體替換最優(yōu)個體保存起來。若種群中的最佳個體比最優(yōu)個體差，則將最優(yōu)個體替換種群中的最差個體，以防止最優(yōu)個體流失。

3 算法示例及結(jié)果分析

JIT生產(chǎn)模式下一汽解放卡車總裝配線日生產(chǎn)計劃需要生產(chǎn)牽引卡車、載貨卡車、自卸卡車3種車型、6種配置共25輛卡車，日生產(chǎn)計劃如表2所示，各車型對關(guān)鍵件和選裝件的需求及選裝頻率如表3所示。

表2 日生產(chǎn)計劃

采用自適應(yīng)遺傳算法進行日生產(chǎn)計劃優(yōu)化排序，參數(shù)設(shè)置為種群大小40，遺傳代溝90%，Pac=0.92，Plc=0.3，Pam=0.03，Plm=0.01，各優(yōu)化目標(biāo)的權(quán)重如表1所示，遺傳進化80代，總目標(biāo)及各車間子目標(biāo)隨進化代數(shù)的變化過程如圖2所示。

表3 投產(chǎn)汽車配置

圖2 自適應(yīng)遺傳算法各優(yōu)化目標(biāo)搜索過程

圖2 中每個子圖括號里左側(cè)數(shù)據(jù)為子目標(biāo)達到最優(yōu)的代數(shù)，右側(cè)數(shù)據(jù)為最優(yōu)子目標(biāo)值。隨著遺傳代數(shù)的增加，總目標(biāo)值到72代以后趨向平穩(wěn)；車型變化次數(shù)經(jīng)過57代達到最優(yōu)，由17次減少到10次；顏色切換次數(shù)經(jīng)過72代達到最優(yōu)，顏色切換由12次減少到1次；選裝件沖突次數(shù)經(jīng)過48代達到最優(yōu)，違反選裝件頻率的次數(shù)由11次減少到0次，保證了總裝配線的均衡生產(chǎn)；關(guān)鍵件型號切換次數(shù)經(jīng)過57代達到最優(yōu)，關(guān)鍵件型號切換次數(shù)由54次減少到30次。JIT生產(chǎn)模式下25輛卡車混流裝配日生產(chǎn)計劃優(yōu)化排序結(jié)果如圖3所示。

圖3 混流裝配線日生產(chǎn)計化優(yōu)化排序

由圖3可見，混流裝配計劃排序的自適應(yīng)遺傳算法可最大限度地減少總裝配線的負荷沖突，完全能滿足焊裝車間、涂裝車間和總裝配車間計劃排序的生產(chǎn)需求，提高了生產(chǎn)計劃排產(chǎn)效率。

4 結(jié)束語

混流裝配線計劃排序問題是保證裝配線平衡、高效、準(zhǔn)時化的關(guān)鍵問題之一。文章為了實現(xiàn)多車間生產(chǎn)的負荷均衡，保證JIT生產(chǎn)的平順性和高效型，將焊裝、涂裝和總裝車間的生產(chǎn)計劃排序目標(biāo)綜合考慮，采用層次分析法確定各目標(biāo)的權(quán)重，并從違反選裝件的選裝頻率次數(shù)、車身噴涂顏色變化、車型切換次數(shù)、關(guān)鍵件型號切換次數(shù)四個方面出發(fā)，采用加權(quán)平均法建立多目標(biāo)綜合優(yōu)化數(shù)學(xué)模型。提出了混流裝配計劃排序的自適應(yīng)遺傳算法，通過交叉概率和變異概率的自適應(yīng)調(diào)整，可在遺傳進化的初期減少種群中個體的差異，提高種群的多樣性，在遺傳進化的后期通過增加個體的差異，保證最優(yōu)解的進一步搜索，并通過局部尋優(yōu)和保優(yōu)策略提高了算法的尋優(yōu)能力，避免了提前收斂。最后，通過算例，驗證了自適應(yīng)遺傳算法可最大限度滿足多車間混流裝配線的準(zhǔn)時化生產(chǎn)實際需求。

［1］Xiaobo Z，Ohno K.Algorithms for sequencing mixed models on an assembly line in a JIT production system［J］.Computers and Industry Engineering，1997，32（1）：47-56.

［2］宋春雷.混流裝配線平衡與投產(chǎn)排序研究［D］.大連：大連理工大學(xué)，2012.

［3］李同正，楊才君，孫林巖.混流裝配線平衡和排序問題研究綜述［J］.河南科學(xué)，2012，30（7）：900-909.

［4］邵新宇，饒運清.制造系統(tǒng)運行優(yōu)化理論與方法［M］.北京：科學(xué)出版社，2010.

［5］董義軍.多工廠協(xié)同生產(chǎn)計劃與調(diào)度方法研究［D］.上海：上海交通大學(xué)，2010.

［6］蘇生.多工廠生產(chǎn)計劃與調(diào)度優(yōu)化模型與求解算法［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2007.

［7］鄭敏，董明.考慮轉(zhuǎn)換約束的汽車混流裝配線投產(chǎn)排序研究［J］.工業(yè)工程與管理，2012（2）：85-89.

［8］黃剛.混流裝配生產(chǎn)的計劃排序及其執(zhí)行過程管理［D］.武漢：華中科技大學(xué)，2007.

［9］邢永慶.轎車涂裝線生產(chǎn)準(zhǔn)備過程分析及改進［D］.長春：吉林大學(xué)，2012.

［10］劉敬宇，朱朝艷.改進自適應(yīng)遺傳算法的結(jié)構(gòu)優(yōu)化設(shè)計［J］.遼寧工學(xué)院學(xué)報，2007，26（5）：308-311.

（編輯 李秀敏）

Research on Mixed-Model Assembly Line's Sorting of Multiple Workshop Based on JIT

XU Bing，TAO Li-hua，HU Yue-mei
（School of Mechanical and Electrical Engineering，Changchun University of Technology，Changchun 130012，China）

In order to agile and efficient operation of mixed-model assembly line's sorting of multiple workshop based on JIT，this essay research the supply and demand between the multiple workshop.Multi-objective was present：minimizing model switching times，key-module type switching，color switching times and violating optional frequency.Then the weighted average method was used to build the multi-objective mathematical model.The paper presents the adaptive genetic algorithm to solve mixed-model assembly line's Sorting of multiple workshops，which according to genetic algorithm easy to fall into local optimum and convergence problems in advance.Improving the searching capability of the algorithm which by means of adaptive crossover and mutation，local optimization and optimal policy.Finally use example to verify the efficiency of the algorithm.

multiple cooperating workshops；mixed-model assembly；sorting

TH162；TG65

A

1001-2265（2015）01-0153-04 DOI：10.13462/j.cnki.mmtamt.2015.01.043

2014-06-09；

2014-08-09

國家高技術(shù)研究發(fā)展計劃（863計劃）（2007AA04Z1A4）

徐兵（1965—），男，黑龍江延壽人，長春工業(yè)大學(xué)副教授，博士，碩士生導(dǎo)師，研究方向為柔性制造技術(shù)和制造業(yè)信息化，（E-mail）xubing1965@126.com。