基于零部件均衡重要程度的混流裝配線排序

劉 暢，原丕業(yè)，劉佳楠，張 萌

(青島理工大學(xué) 管理工程學(xué)院，山東 青島 266520)

混流裝配線是指在同1條裝配線上以流水作業(yè)的方式混合連續(xù)地完成工藝接近的不同類(lèi)型、不同數(shù)量的產(chǎn)品。合理的產(chǎn)品投放順序有助于降低成本、提高效率，進(jìn)而提升企業(yè)的競(jìng)爭(zhēng)力。因此，眾多學(xué)者針對(duì)該問(wèn)題進(jìn)行了大量的研究。文獻(xiàn)[1-7]分別從不同的角度建立關(guān)于混流裝配線的排序模型，但并未考慮到生產(chǎn)過(guò)程中零部件消耗的均衡化。文獻(xiàn)[8-14]雖在建立的混流裝配線排序模型中考慮到零部件消耗均衡化的因素，但并未考慮到不同類(lèi)型零部件的消耗均衡情況對(duì)生產(chǎn)裝配系統(tǒng)重要程度的差異性。因此，在以零部件消耗均衡化為目標(biāo)的混流裝配線排序過(guò)程中考慮零部件均衡化的重要程度是十分必要的。

1 問(wèn)題描述

混流裝配線排序問(wèn)題是一個(gè)短期決策問(wèn)題，每日甚至每班都需要根據(jù)市場(chǎng)需求的變化安排合適的排產(chǎn)計(jì)劃。由于在混流裝配線中生產(chǎn)每種產(chǎn)品所需的零部件類(lèi)型以及數(shù)量各不相同，所以不同的投產(chǎn)排序?qū)Ω黝?lèi)零部件的消耗都是不同的。若零部件消耗不均衡，則會(huì)造成在一段時(shí)間內(nèi)某類(lèi)零件的需求量激增，而其他零件的需求量較少，為了應(yīng)對(duì)某零件的高峰需求，該零件需要維持在1個(gè)較高的安全庫(kù)存，從而造成不必要的浪費(fèi)。因此，在混流裝配線排序時(shí)需要對(duì)零部件消耗波動(dòng)進(jìn)行均衡。由于傳統(tǒng)的零部件消耗均衡是為了達(dá)到總體目標(biāo)的最優(yōu)，即全部零部件消耗波動(dòng)函數(shù)之和最小化，所以個(gè)別類(lèi)型的零部件消耗波動(dòng)均衡情況一定沒(méi)有或者是較小地進(jìn)行改善。若這類(lèi)零部件的均衡程度相對(duì)生產(chǎn)系統(tǒng)更為重要，則必須采用一定的方法保證這類(lèi)零部件最大程度地優(yōu)先進(jìn)行均衡。

2 數(shù)學(xué)建模

基于以上描述，為了確保重要零部件最大程度地優(yōu)先進(jìn)行均衡，本文根據(jù)各類(lèi)零部件均衡對(duì)生產(chǎn)裝配系統(tǒng)的重要性，分別賦予各類(lèi)零部件不同的權(quán)重，為了簡(jiǎn)化運(yùn)算，在1個(gè)最小生產(chǎn)循環(huán)內(nèi)構(gòu)建基于零部件均衡重要程度的混流裝配線排序模型

(1)

(2)

(3)

qms-qm,s-1≤1， ?s∈I,m∈M，

(4)

qms-qm,s-1≥0， ?s∈I,m∈M，

(5)

0≤qms≤dm， ?s∈I,m∈M，

(6)

0≤ωg≤1， ?g∈p.

(7)

式中：I為1個(gè)MPS中需要排序的產(chǎn)品數(shù)量；s為排產(chǎn)序列中第s個(gè)位置；p為零部件的種類(lèi)數(shù)量；M為產(chǎn)品的種類(lèi)數(shù)量；g為類(lèi)型g的零部件；m為類(lèi)型m的產(chǎn)品；dm為類(lèi)型m的產(chǎn)品數(shù)量；ngm為裝配產(chǎn)品m所消耗零部件g的數(shù)量；qms為前s個(gè)位置中產(chǎn)品m的數(shù)量；ωg為零部件g均衡化重要程度的權(quán)重；xsm為0～1變量，當(dāng)排產(chǎn)序列中第s個(gè)位置的產(chǎn)品是m，則為1，否則為0。

目標(biāo)函數(shù)表示考慮零部件均衡重要程度的零部件消耗均衡情況，其中，括號(hào)內(nèi)第一部分表示零部件的理想消耗量，第二部分表示零部件的實(shí)際消耗量；式(2)表示任意1個(gè)位置只能安排1個(gè)產(chǎn)品；式(3)表示排產(chǎn)序列中安排m產(chǎn)品的數(shù)量等于其需求量；式(4)、式(5)表示在任意1個(gè)s-1的位置到s位置，產(chǎn)品m的數(shù)量只能增加1或保持不變；式(6)表示排序中任意s位置前產(chǎn)品m的數(shù)量不能大于1個(gè)MPS中產(chǎn)品m的需求量；式(7)表示權(quán)重的取值范圍。

3 自適應(yīng)遺傳算法的設(shè)計(jì)

遺傳算法是由美國(guó)教授Holland在1975年提出的1種效仿達(dá)爾文生物進(jìn)化過(guò)程的優(yōu)化算法，即通過(guò)對(duì)染色體的評(píng)價(jià)、選擇、交叉以及變異等一系列操作，最終得到最優(yōu)的目標(biāo)值。但是，傳統(tǒng)的遺傳算法中的交叉算子和遺傳算子往往采用固定的數(shù)值，這種方式的弊端在于若種群中出現(xiàn)占據(jù)絕對(duì)優(yōu)勢(shì)的染色體，極易導(dǎo)致求解的結(jié)果陷入局部最優(yōu)。為了避免出現(xiàn)早熟現(xiàn)象，提高全局搜索最優(yōu)染色體的能力，文中設(shè)計(jì)新的自適應(yīng)遺傳算法用于解決混流裝配線的排序問(wèn)題。該算法在遺傳算法的基礎(chǔ)上通過(guò)借鑒文獻(xiàn)[15]的自適應(yīng)機(jī)制對(duì)交叉和變異算子進(jìn)行動(dòng)態(tài)地調(diào)整，可以使模型在求解過(guò)程中有效地避免出現(xiàn)早熟的現(xiàn)象。綜合以上的分析，可得到本文設(shè)計(jì)的自適應(yīng)遺傳算法的流程如圖1所示。

圖1 自適應(yīng)遺傳算法流程

3.1 編碼

針對(duì)投產(chǎn)排序問(wèn)題，由于模型的求解結(jié)果只與產(chǎn)品對(duì)應(yīng)編碼在染色體上的位置有關(guān)，與其大小無(wú)關(guān)，故本文采用符號(hào)編碼方式。不同類(lèi)型的產(chǎn)品用不同的數(shù)字表示，如A，B，C，D，E 5種產(chǎn)品分別用1，2，3，4，5進(jìn)行表示，則染色體11223345解碼后可表示為AABBCCDE這樣一個(gè)序列依次進(jìn)入裝配線。

3.2 初始化種群的產(chǎn)生

為了確保初始解的質(zhì)量以及多樣性，在初始化種群的過(guò)程中參考小生境技術(shù)先進(jìn)的思想。首先依據(jù)1個(gè)MPS中各產(chǎn)品的投產(chǎn)比例，分別確定染色體的長(zhǎng)度以及種群的規(guī)模，然后任意生成滿足種群規(guī)模大小條件的若干個(gè)種群，挑選出每個(gè)種群中適應(yīng)度值排名前10%的染色體，使其組成1個(gè)新的種群，最終形成初始種群。

3.3 選擇

為了能夠更好地選擇和保留優(yōu)秀的染色體，本文采用精英保留策略和輪盤(pán)賭相結(jié)合的方法。采用輪盤(pán)賭的方法雖然可以使適應(yīng)度值好的染色體有較大的概率被選中復(fù)制到下一代，但是無(wú)法保證一定被保留。同理，適應(yīng)度值較差的染色體無(wú)法保證被淘汰。并且由于后續(xù)交叉和變異的過(guò)程中具有隨機(jī)性，容易出現(xiàn)遺傳退化。因此，為防止出現(xiàn)遺傳退化解，確保淘汰最差個(gè)體，保留最優(yōu)染色體，故在輪盤(pán)賭的基礎(chǔ)上加入精英保留策略。即保存并記錄父代種群中的最佳染色體，若子代種群相比父代種群沒(méi)有出現(xiàn)更優(yōu)秀的染色體，則用保存的最佳染色體替換子代種群中適應(yīng)度值最低的染色體，否則，將更新當(dāng)前保存的最佳染色體。

3.4 自適應(yīng)交叉算子

交叉概率決定了種群中染色體被選中進(jìn)行交叉從而產(chǎn)生子代的概率，小的交叉概率能夠更好地對(duì)種群中出現(xiàn)的優(yōu)秀個(gè)體進(jìn)行保留，但是容易陷入局部最優(yōu)。大的交叉概率有利于跳出局部最優(yōu)從而尋求最優(yōu)解，但是會(huì)損害優(yōu)秀個(gè)體，造成算法退化，為了提高算法對(duì)局部最優(yōu)的突破能力以及全局最優(yōu)的保存能力，借鑒文獻(xiàn)[10]的方法，通過(guò)評(píng)價(jià)當(dāng)前種群染色體的離散程度對(duì)交叉概率進(jìn)行自適應(yīng)調(diào)整,具體計(jì)算如式(8)所示。從選擇復(fù)制產(chǎn)生的子代種群中按照自適應(yīng)交叉概率pc選取一定數(shù)量的交叉父本，兩兩父代個(gè)體之間進(jìn)行交叉操作。交叉過(guò)程如圖2所示：首先從父代1中任取一段基因直接遺傳到子代1相應(yīng)的位置；其次，從父代2中依次剔除所選取片段中含有的基因，并將殘留的基因依次遺傳到子代1剩余的位置中，從而產(chǎn)生新的子代個(gè)體。同理，交換父代的位置可產(chǎn)生子代2。將從原種群中選擇的交叉父本分別用新產(chǎn)生的子代個(gè)體進(jìn)行替換，進(jìn)而形成新的種群。

圖2 交叉過(guò)程

自適應(yīng)交叉概率pc的計(jì)算公式為

pc=

(8)

式中：pcmax為預(yù)設(shè)最大交叉概率；pcmin為預(yù)設(shè)最小交叉概率；fmax為當(dāng)前種群內(nèi)個(gè)體的最大適應(yīng)度值；favg為當(dāng)前種群內(nèi)各個(gè)體的平均適應(yīng)度值；ξ為fmax-favg的敏感性系數(shù)。

3.5 自適應(yīng)變異算子

變異概率決定了種群中染色體被選中進(jìn)行變異的概率，對(duì)種群多樣性的保持有著重要意義。本文通過(guò)借鑒文獻(xiàn)[10]的方法對(duì)變異概率進(jìn)行自適應(yīng)調(diào)整，具體計(jì)算如式(9)所示。變異過(guò)程具體如下：首先從種群中按照自適應(yīng)變異概率抽取一定數(shù)量的變異父本，其次如圖3所示對(duì)變異父本中的染色體隨機(jī)選取兩個(gè)需要突變的位置進(jìn)行交換以完成變異操作。

圖3 變異過(guò)程

自適應(yīng)變異概率pm計(jì)算公式為

pm=

(9)

式中：pmmax為預(yù)設(shè)的最大變異概率,pmmin為預(yù)設(shè)的最小變異概率。

根據(jù)式(8)和式(9)可知，fmax與favg的差值越大表示當(dāng)前種群個(gè)體越離散，種群多樣性越好，此時(shí)需要降低交叉概率pc和變異概率pm，從而加速收斂。fmax與favg的差值越小表示當(dāng)前種群個(gè)體越集中，多樣性越差，為防止出現(xiàn)局部收斂等問(wèn)題，需要增加交叉概率pc和變異概率pm。

4 案例分析

已知某公司混流裝配線上A，B，C，D，E 5種產(chǎn)品的日均訂單需求量分別為(60，20，40，30，20)，根據(jù)最小生產(chǎn)循環(huán)原理可得到A，B，C，D，E的產(chǎn)品比例為6:2:4:3:2，現(xiàn)階段公司按照AAAAAABBCCCCDDDEE的順序在最小生產(chǎn)循環(huán)內(nèi)依次對(duì)各類(lèi)產(chǎn)品進(jìn)行小批量生產(chǎn)，其中，每種產(chǎn)品消耗零部件的類(lèi)型和數(shù)量如表1所示。

表1 產(chǎn)品-零部件消耗矩陣

本文的算法通過(guò)MATLAB R2016a進(jìn)行編程，計(jì)算機(jī)處理器參數(shù)為Intel(R)Core(TM)i5-8250U CPU@1.6 GHz 1.80 GHz雙核處理器，RAM為8 GB，64位Windows10操作系統(tǒng)。經(jīng)過(guò)算法靈敏度計(jì)算實(shí)驗(yàn)，確定涉及的參數(shù)設(shè)置如下：種群大小為30，最大交叉概率與最小交叉概率分別為0.9和0.5，最大變異概率與最小變異概率分別為0.1和0.01，迭代代數(shù)為100，ξ為10，根據(jù)各零部件均衡化重要程度確定權(quán)重ωg=[0.4,0.4,0.4,0.4,1,1,0.4]。

4.1 算法對(duì)比

利用自適應(yīng)遺傳算法進(jìn)行求解，得到最終的混流裝配線排序方案為DABCAECADACACEBAD，目標(biāo)函數(shù)值為31.282 4。其中，自適應(yīng)遺傳算法收斂曲線如圖4所示。

圖4 自適應(yīng)遺傳算法收斂曲線

利用標(biāo)準(zhǔn)遺傳算法進(jìn)行求解，得到最終的混流裝配線排序方案為DABCAECAEDACDACAB，目標(biāo)函數(shù)值為39.411 8。其中，標(biāo)準(zhǔn)遺傳算法收斂曲線如圖5所示。

圖5 標(biāo)準(zhǔn)遺傳算法收斂曲線

通過(guò)對(duì)比分析兩種算法優(yōu)化性能以及對(duì)所構(gòu)建模型進(jìn)行求解的最終結(jié)果，可以發(fā)現(xiàn)，標(biāo)準(zhǔn)遺傳算法在迭代85次后收斂，目標(biāo)函數(shù)值為39.411 8。針對(duì)同樣問(wèn)題，自適應(yīng)遺傳算法達(dá)到穩(wěn)定狀態(tài)只需迭代44次，目標(biāo)函數(shù)值為31.282 4，結(jié)果表明自適應(yīng)遺傳算法的尋優(yōu)效果更好，效率更高。

4.2 結(jié)果分析

利用本文設(shè)計(jì)的自適應(yīng)遺傳算法對(duì)不考慮零部件均衡重要程度的零部件消耗均衡化模型進(jìn)行分析，即賦予每種零件相同的權(quán)重，可得到對(duì)應(yīng)最優(yōu)的混流裝配線排序方案為DABCAECDACEACABD。比較公司優(yōu)化前的排序方案以及有無(wú)考慮零部件均衡重要程度兩種情況優(yōu)化后的混流裝配線排序方案，可得到各零部件的消耗方差值，如表2所示。

由表2可見(jiàn)，相比公司現(xiàn)有的投產(chǎn)順序，無(wú)論采用哪種方式進(jìn)行優(yōu)化，都可大幅度降低各類(lèi)零部件的消耗方差值，可見(jiàn)，使用零部件消耗均衡化模型確定的投產(chǎn)順序和零部件消耗均衡情況相較于公司現(xiàn)有的投產(chǎn)順序都會(huì)有較大的提升。另外，相比不考慮零部件均衡重要程度的情況，在考慮零部件均衡重要程度的情況下，p5和p6的消耗方差值分別由8.941 2降至6.117 6、12.588 2降至10.764 7，均衡效果分別提升31.578 9%和14.486%，p5,p6二者消耗方差之和由21.529 4降至16.882 3，重要零部件的總體均衡效果提升了21.584 7%。由此可知，基于零部件均衡重要程度的零部件消耗均衡化模型能夠優(yōu)化混流裝配線的投產(chǎn)排序順序，并且可以對(duì)生產(chǎn)系統(tǒng)影響程度更為重要的零部件實(shí)現(xiàn)更好地均衡，從而優(yōu)化生產(chǎn)系統(tǒng)，在生產(chǎn)制造過(guò)程中實(shí)現(xiàn)企業(yè)精益生產(chǎn)的目的。

表2 不同排序方案下各零部件的消耗方差值

除此之外，為了最大限度地實(shí)現(xiàn)更為重要零件的均衡，造成各類(lèi)零部件的總體消耗方差之和有所增加，由47.117 6增加至52.882 4。根據(jù)制造業(yè)的實(shí)際生產(chǎn)要求，以犧牲較小的總體消耗波動(dòng)換取對(duì)生產(chǎn)系統(tǒng)影響更為重要的零部件最大限度地均衡是必要且可取的。

4.3 實(shí)驗(yàn)分析

為了明確重要零部件消耗均衡與總體波動(dòng)的關(guān)系，以確定對(duì)混流裝配線所需零部件總體的實(shí)質(zhì)影響，本文根據(jù)不同情境設(shè)置不同的權(quán)重配比方案進(jìn)行實(shí)驗(yàn)分析，如表3所示。

表3 不同的權(quán)重配比方案

方案1與方案5對(duì)應(yīng)不考慮零部件均衡重要程度和考慮零部件均衡重要程度兩種情境下的解上文已求得，故只需對(duì)方案2、方案3和方案4的混流裝配線排序進(jìn)行求解，得到對(duì)應(yīng)的排產(chǎn)順序分別為DABCAECADACBADEAC、DABCAECADACBAEDCA、DABCAECADBADACECA。根據(jù)方案1～5的排產(chǎn)順序可得到對(duì)應(yīng)的零部件總體消耗方差值分別為47.117 6、49.941 8、50.647 1、51.411 8、52.882 4，其中，重要零部件p5和p6的消耗方差之和分別為21.529 4、20.882 4、20.235 3、18.882 4、16.882 4。通過(guò)對(duì)方案1～5的總體零部件以及重要零部件消耗方差值進(jìn)行分析，可以得到不同權(quán)重配比方案下各因素的變化曲線，如圖6所示。從圖中可以看出，自方案1至方案5，隨著重要零部件相對(duì)重要程度的增強(qiáng)，重要零部件消耗方差和逐漸減少，而總體消耗方差和逐漸增加。由此可以說(shuō)明，重要零部件消耗均衡化與總體消耗均衡的目標(biāo)相沖突，更好地均衡重要零部件的消耗是以增加生產(chǎn)系統(tǒng)總體消耗波動(dòng)為代價(jià)的。因此，企業(yè)管理者在生產(chǎn)過(guò)程中應(yīng)權(quán)衡考慮重要零部件的均衡與總體波動(dòng)之間的關(guān)系，適時(shí)為企業(yè)管理提供合理決策。

圖6 不同權(quán)重配比方案下各因素的變化曲線

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

本文在傳統(tǒng)的零部件消耗均衡模型的基礎(chǔ)上進(jìn)行改進(jìn)，構(gòu)建了基于零部件均衡重要程度的混流裝配線排序模型。根據(jù)所建模型，設(shè)計(jì)了自適應(yīng)遺傳算法，并與標(biāo)準(zhǔn)遺傳算法進(jìn)行對(duì)比，結(jié)果證明自適應(yīng)遺傳算法的尋優(yōu)效果更好，效率更高。通過(guò)案例的對(duì)比分析，證明在各類(lèi)零部件的總體消耗波動(dòng)不會(huì)顯著增加的情況下，基于零部件均衡重要程度的混流裝配線排序能夠?qū)ιa(chǎn)系統(tǒng)影響更大的零部件均衡情況有較大程度地改善。除此之外，通過(guò)對(duì)重要零部件配比不同的權(quán)重方案，證實(shí)重要零部件消耗均衡與總體波動(dòng)之間的關(guān)系，對(duì)企業(yè)管理者合理決策具有借鑒意義。