基于遺傳算法的汽車零配件生產(chǎn)排程問題

潘怡穎 徐嘉杰 劉大河

華南農(nóng)業(yè)大學(xué)數(shù)學(xué)與信息學(xué)院，廣東 廣州 510642

車間生產(chǎn)調(diào)度問題（JSSP）是企業(yè)生產(chǎn)作業(yè)調(diào)度中的重大課題，汽車零配件則是汽車工業(yè)的基礎(chǔ)，噴涂過程是汽車工業(yè)中必不可少的環(huán)節(jié)。在現(xiàn)有的研究車間調(diào)度的方法中，大多數(shù)是以生產(chǎn)周期為目標(biāo)的優(yōu)化問題，多為運(yùn)用遺傳算法、蟻群算法與粒子群算法等，通過迭代方法實(shí)現(xiàn)柔性作業(yè)車間調(diào)度的方案。經(jīng)過對相關(guān)文獻(xiàn)的探究，我們最終選擇基于遺傳算法建立的數(shù)學(xué)模型來完成多目標(biāo)柔性車間排程問題。

1 問題描述

噴涂過程在傳送帶上完成，每個(gè)零件需要放在特定的支架上進(jìn)行順序噴涂。一圈共有303個(gè)滑橇，一個(gè)滑橇有兩面，可同時(shí)噴涂，一個(gè)滑橇可看作6個(gè)相同支架，則每個(gè)滑橇放置同種零件。若前后相鄰兩個(gè)滑橇上的零件需要噴涂不同的面漆色，則出現(xiàn)了“換色”，意味著對應(yīng)的噴槍需要更換涂料顏色。現(xiàn)需要根據(jù)指導(dǎo)生產(chǎn)量制定出未來八圈的詳細(xì)噴涂排序計(jì)劃，要求盡量減少換色的次數(shù)，并盡可能滿足指導(dǎo)生產(chǎn)量的需求。統(tǒng)計(jì)出每一圈的平均換色次數(shù)及未滿足生產(chǎn)需求的零件個(gè)數(shù)，作為判斷指標(biāo)。

2 問題分析

對于本題，首先要明確約束條件，并將其用數(shù)學(xué)語言進(jìn)行表述，建立以顏色與零件種類為編碼的遺傳算法模型，然后再對模型進(jìn)行優(yōu)化分析，得到最優(yōu)解。該問題的特點(diǎn)在于充分考慮生產(chǎn)的實(shí)際情況，用一定數(shù)量的運(yùn)算解決多項(xiàng)式一定時(shí)間內(nèi)的問題。而問題的難點(diǎn)在于對約束條件進(jìn)行模型化處理。

3 基于遺傳算法的調(diào)度優(yōu)化

3.1 約束規(guī)則

換色順序規(guī)則：任意紅色和任意藍(lán)色后面不能接任何白色；極地白后不能安排任意黑色；鉆石白前必須是極地白。

零件擺放規(guī)則：（門檻B(tài)），（門檻C），（門檻A、門檻D、后保A、門檻裝飾條A），3個(gè)括號(hào)對應(yīng)三個(gè)項(xiàng)目，不同項(xiàng)目的任意兩個(gè)產(chǎn)品的滑橇不能安排在一起；門檻B(tài)、門檻C不能與所有類型的雷達(dá)支架安排在一起噴涂。

3.2 模型思路

遺傳算法（genetic algorithm, GA）是基于自然選擇和基因遺傳學(xué)原理的一種群體尋優(yōu)的搜索算法，特別適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題，其中就包括生產(chǎn)調(diào)度問題，且能為調(diào)度解提供很好的魯棒性。

我們基于遺傳算法框架，根據(jù)問題描述，進(jìn)行了模型優(yōu)化：把目標(biāo)函數(shù)劃分為兩層，即外層目標(biāo)函數(shù)代表未滿足零件的最優(yōu)解，內(nèi)層目標(biāo)函數(shù)代表顏色更換的最優(yōu)解，使模型能夠完成多目標(biāo)問題最優(yōu)解的尋找。

3.3 染色體編碼

本文采用坐標(biāo)編碼的方法，編碼的X用來表述零件種類，編碼的Y則表述顏色的種類，即可做到將83種具體的零件與坐標(biāo)一一對應(yīng)。顏色編碼、產(chǎn)品編碼分別如表1、表2所示。

表1 顏色編碼

表2 產(chǎn)品編號(hào)

如光耀藍(lán)門檻A則表示為（20,2）。由于X∈[0,30]，Y∈[0,9]，共有31*10=310種坐標(biāo)組合，但零件個(gè)數(shù)僅為83種，即有227種坐標(biāo)組合并不存在對應(yīng)零件。于是我們設(shè)計(jì)生存矩陣，將不存在的零件數(shù)設(shè)為“0”，存在的零件數(shù)設(shè)為“1”，每生成一個(gè)坐標(biāo)組合，則需通過生存矩陣判斷其是否存在。若不存在，則重新生成，直至其判斷為是存在的零件種類。有此編碼后，問題的約束規(guī)則也可以得到解決，即當(dāng)出現(xiàn)違反問題約束的零件擺放時(shí)，重新隨機(jī)或空一個(gè)滑橇來保證滿足約束條件。

3.4 種群初始化

進(jìn)行合適的種群化選擇可以避開有效基因的損失，設(shè)置合適的遺傳算法計(jì)算參數(shù)將推進(jìn)算法的進(jìn)程，參數(shù)設(shè)置如下。

（1）群體規(guī)模N=200。即在內(nèi)層每次運(yùn)行過程中，最多保留的種群為200組。

（2）內(nèi)層迭代次數(shù)T1=303。因?yàn)橐蝗魉蛶е泄灿?03個(gè)滑橇，于是每圈的迭代次數(shù)設(shè)定為303，迭代303次表示單圈完成。

（3）外層迭代次數(shù)T2=1000。即在1000個(gè)內(nèi)層迭代出的可行解中，選擇最優(yōu)的作為全局最優(yōu)解。

（4）變異概率P=0.4。為增加零件多樣性，防止陷入局部最優(yōu)解，設(shè)定變異概率為0.4，當(dāng)產(chǎn)生變異時(shí)，顏色變異概率為Pc=0.3，零件種類變異概率為Pz=0.7。

3.5 目標(biāo)函數(shù)

1）內(nèi)層目標(biāo)函數(shù)

為了降低生產(chǎn)成本，我們需要盡量減少換色次數(shù)。函數(shù)表達(dá)式為：由于支架數(shù)量具有上限，即在每圈的噴涂過程中相應(yīng)的零件數(shù)同樣具有上限，為在有限的零件數(shù)內(nèi)有效利用支架數(shù)，需增加零件的多樣性，故更換零件次數(shù)需要達(dá)到最大值：

權(quán)系數(shù)的產(chǎn)生，我們通過層次分析法得到，利用換色次數(shù)與零件更換次數(shù)兩個(gè)指標(biāo)建立判斷矩陣進(jìn)行相對重要度計(jì)算。采用求根法來計(jì)算特征值的近似值，最終得到權(quán)重為W1=W2=0.5。則最終的目標(biāo)函數(shù)為：

2）外層目標(biāo)函數(shù)

由于最終問題的要求是盡量滿足生產(chǎn)需求，在內(nèi)層目標(biāo)函數(shù)選擇后的多個(gè)可行解中，選擇最少的未滿足產(chǎn)品零件個(gè)數(shù)。

3.6 遺傳算子的設(shè)計(jì)

1）非變異交叉操作

由編碼規(guī)則可知，一個(gè)算子由產(chǎn)品種類X和顏色Y組成。假設(shè)一個(gè)初始選擇的算子編碼為（n,m），則記這個(gè)初始算子為A(n,n)，簡記為Anm。在非變異交叉操作中，子代沒有發(fā)生改變，即復(fù)制行為占整個(gè)分裂行為的0.6。

如對A74A12進(jìn)行復(fù)制，復(fù)制一次得到A74A12A12，復(fù)制兩次得到A74A12A12A12。

2）變異交叉操作

在遺傳算法的計(jì)算過程中，變異算子是遺傳算法生產(chǎn)新個(gè)體的主要操作方式，它能提高遺傳算法的全局搜索性，也能從局部得到更優(yōu)的解。

在復(fù)制操作中，我們假設(shè)了一個(gè)初始算子為Anm，繼續(xù)沿用在變異操作中。在整個(gè)遺傳算子的分裂中，變異占據(jù)了剩下的0.4，由于一個(gè)算子由產(chǎn)品種類X和顏色Y組成，變異時(shí)只會(huì)在X和Y中選擇任意一個(gè)。要使得換色次數(shù)盡量少并且合理安排產(chǎn)品排序，則Y變化要盡量少。基于問題中隱含的產(chǎn)品種類多樣性和產(chǎn)品顏色穩(wěn)定性的要求，設(shè)定算子變異X的概率在變異事件中為0.7，算子變異Y的概率在變異事件中為0.3。

最后，將約束規(guī)則進(jìn)行模型化處理，采用輪盤賭選擇方法來達(dá)到篩選的目的，通過目標(biāo)函數(shù)值之間的比較，選擇函數(shù)值最小的組合，作為本圈的初步噴涂計(jì)劃。由于在換色過程中要求在兩個(gè)滑橇之間插入一個(gè)滑橇的底漆件作為過渡，即意味著換色過程中將會(huì)“損失”一個(gè)滑橇。

于是我們在確定初步噴涂計(jì)劃后，減去當(dāng)圈的換色次數(shù)C，即需要?jiǎng)h除計(jì)劃中最后C個(gè)滑橇的零件，再一次性插入換色的滑橇之間，形成完整的單圈噴涂計(jì)劃。

4 結(jié)語

根據(jù)實(shí)例仿真，最終得到平均每圈的換色次數(shù)為6.125，未滿足生產(chǎn)需求的零件個(gè)數(shù)為451，說明基于遺傳算法的車間調(diào)度解決方案能夠良好地解決車間生產(chǎn)調(diào)度相關(guān)問題。