基于遺傳算法的汽車零配件生產排程問題

潘怡穎 徐嘉杰 劉大河

華南農業大學數學與信息學院，廣東 廣州 510642

車間生產調度問題（JSSP）是企業生產作業調度中的重大課題，汽車零配件則是汽車工業的基礎，噴涂過程是汽車工業中必不可少的環節。在現有的研究車間調度的方法中，大多數是以生產周期為目標的優化問題，多為運用遺傳算法、蟻群算法與粒子群算法等，通過迭代方法實現柔性作業車間調度的方案。經過對相關文獻的探究，我們最終選擇基于遺傳算法建立的數學模型來完成多目標柔性車間排程問題。

1 問題描述

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

2 問題分析

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

3 基于遺傳算法的調度優化

3.1 約束規則

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

零件擺放規則：（門檻B），（門檻C），（門檻A、門檻D、后保A、門檻裝飾條A），3個括號對應三個項目，不同項目的任意兩個產品的滑橇不能安排在一起；門檻B、門檻C不能與所有類型的雷達支架安排在一起噴涂。

3.2 模型思路

遺傳算法（genetic algorithm, GA）是基于自然選擇和基因遺傳學原理的一種群體尋優的搜索算法，特別適用于處理傳統搜索方法難以解決的復雜和非線性問題，其中就包括生產調度問題，且能為調度解提供很好的魯棒性。

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

3.3 染色體編碼

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

表1 顏色編碼

表2 產品編號

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

3.4 種群初始化

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

（1）群體規模N=200。即在內層每次運行過程中，最多保留的種群為200組。

（2）內層迭代次數T1=303。因為一圈傳送帶中共有303個滑橇，于是每圈的迭代次數設定為303，迭代303次表示單圈完成。

（3）外層迭代次數T2=1000。即在1000個內層迭代出的可行解中，選擇最優的作為全局最優解。

（4）變異概率P=0.4。為增加零件多樣性，防止陷入局部最優解，設定變異概率為0.4，當產生變異時，顏色變異概率為Pc=0.3，零件種類變異概率為Pz=0.7。

3.5 目標函數

1）內層目標函數

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

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

2）外層目標函數

由于最終問題的要求是盡量滿足生產需求，在內層目標函數選擇后的多個可行解中，選擇最少的未滿足產品零件個數。

3.6 遺傳算子的設計

1）非變異交叉操作

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

如對A74A12進行復制，復制一次得到A74A12A12，復制兩次得到A74A12A12A12。

2）變異交叉操作

在遺傳算法的計算過程中，變異算子是遺傳算法生產新個體的主要操作方式，它能提高遺傳算法的全局搜索性，也能從局部得到更優的解。

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

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

于是我們在確定初步噴涂計劃后，減去當圈的換色次數C，即需要刪除計劃中最后C個滑橇的零件，再一次性插入換色的滑橇之間，形成完整的單圈噴涂計劃。

4 結語

根據實例仿真，最終得到平均每圈的換色次數為6.125，未滿足生產需求的零件個數為451，說明基于遺傳算法的車間調度解決方案能夠良好地解決車間生產調度相關問題。