一種新型混合算法在混流裝配調度中的應用

婁高翔，蔡宗琰，劉清濤

LOU Gaoxiang,CAI Zongyan,LIU Qingtao

長安大學 工程機械學院，西安 710064

School of Construction Machinery,Chang’an University,Xi’an 710064,China

1 引言

作為制造業中比較常見的一種生產方式，混流裝配生產可以在一條流水生產線上同時裝配出型號、數量均不同的產品，其具有靈活性高，實用性強的特點。自從1961年由Kilbridge和Wester提出混流裝配這個概念后，混流裝配線的生產調度問題已經成為該領域的研究熱點。李同正等[1]在2012年對一些特殊形式的混裝線進行了分析，指出了混裝線排序問題需要進一步研究的方向；呂聰穎[2]為解決混流裝配調度問題提出了新穎的蟻群算法，定義了信息素的表示方法，但是參數的取值具有一定的局限性；劉瓊等[3]針對混流裝配線上各工作站內設備閑置成本的不同，提出了一種基于線性混合比率的貓行為模式選擇方法，提高了算法前期的全局搜索能力和后期的局部尋優能力；周康渠等[4]針對混流裝配調度算法中存在的“早熟”現象，提出了一種混合離散粒子群算法，并通過實例驗證了該算法的有效性；魯建廈等[5]為解決面向云制造的混合車間調度問題，建立了多目標車間調度模型，設計了一種混合生物地理學優化算法，并得到良好驗證。

目前的混流裝配問題主要是針對多個工序對兩個目標進行優化：裝配線各工作站上的負荷平衡最優、待組裝的主要零部件和原材料的消耗速率最優[1]。近年來對其他因素如最大完工時間[6]、最小化工位[7]、最小化品種切換時間等[8]進行綜合考慮，很少有考慮緩沖空間存在儲存成本的情況，但是在實際問題中，有些緩沖空間的存儲成本需要考慮，且裝配生產的成本問題也是需著重考慮的一項重要因素。混流裝配調度問題是典型的NP-hard問題，目前解決NP-hard問題的方法主要分為分支定界法[9]、領域搜索算法[10]、遺傳算法（GA）[11]、蟻群算法[12]、粒子群優化算法[13]以及一些混合算法[14]等。這些算法都在相關的領域得到了應用驗證。且不同算法對連續數據和離散數據的優化效率不同[15-16]。混流裝配調度中加工工序和加工數量分別為離散變量和連續變量，為了更有效地處理這兩種變量需設計一種更高效的算法，目前對混流裝配調度的研究中尚未見能同時高效處理連續變量和離散變量的混合算法。

本文針對車間中存在緩沖區的實際問題，首次對加工工序和加工數量的連續性進行分類，并用新的混合算法解決了緩沖區數量和調度最優時間而形成的目標優化問題。本文將GA有效處理離散變量及DE有效處理連續變量的優點融合，以更好地處理同時具有離散變量和連續變量的情況。

2 問題描述

在連續的兩個混流裝配車間中，往往布置緩沖區來保證生產平順性，即通過預先安排好一部分制造資源，來緩解生產過程中不同環節之間生產節拍不一致帶來的瓶頸問題。各車間可通過緩沖區的排序功能來調整產品的順序。

本文要討論的緩沖區連接兩個上下游車間。緩沖區可暫時儲存即將進入下游車間生產裝配的零部件，某可以看成是一種特殊類型的在制品倉庫。考慮到不同車間生產節拍不同，生產中各型號產品會在緩沖區中維持一定的數量。由于所研究車間生產的特殊性，對零部件的生產需分階段進行，且在生產過程中，上下游車間共用一批操作工人。零部件的油污需要清洗后風干才能進入下一加工階段，上游車間為零部件的風干車間，下游車間為裝配加工車間，上游車間的加工完全可以在下游車間生產過程中同時無人進行，因此可忽略上游車間的加工時間以及加工停頓性，且零部件風干后輸入到緩沖區時下游車間需停止生產，該時間遠小于下游車間的加工時間，因此可以忽略。單純作為緩沖區而言，過大的緩沖區可以完全滿足車間零部件的緩沖儲存需求，但是也大大增加了儲存成本。而過小的緩沖區雖然可以降低儲存成本，卻不能起到真正平衡節拍的功能。因此，此類緩沖區會有一個最低的安全庫存值，也會有一個最高的庫存值。而下游車間的生產裝配工作量也可以根據緩沖區來調整，如果僅僅考慮生產時間最低則需要盡可能少量的生產數量，僅考慮緩沖區的儲存成本則需要盡可能多的生產數量。同時考慮二者則會形成一個衡量權重、相互矛盾的目標函數，因此需要綜合考慮多方面因素以尋找一個最優的解決方案。另外實踐表明，頻繁更換不同的產品比連續生產同一種產品具有更低的工作效率[17]。針對上述情況，本文提出了一種在最大化工作效率的前提下能夠使生產成本最低的方法，建立了相關的模型，并用新型的算法予以解決。

3 模型建立

為了更加方便地描述以上數學模型，特定義符號如下：

M為所有產品的集合，產品的種類數為為產品的生產序列，產品的總數量為為整個生產序列DT中第m種型號產品的集合，第m種型號產品的數量為，有：Dj為生產序列DT中第j個產品的型號，j=1,2,…,有Dj∈M；sj,m為生產序列DT中第j個位置是否生產第m種產品，其中m∈M，sj,m=0表示否，sj,m=1表示是，顯然有：

3.1 目標函數

此調度問題的目標函數是盡量減少生產成本，包括在整個調度范圍內生產所有產品的總時間成本和緩沖區的儲存成本。

產品的生產時間包括不同種類產品之間的等待時間以及所有產品的加工時間總和。

定義不同種類產品之間的等待時間：

ti,j為生產完i類型產品后j類型產品的準備時間，其中i=1,2,…,m，j=1,2,…,m。

假設ti,i=0，首個生產產品的準備時間定義為ti,i。由于ti,i=0，當計算總的等待時間時，可以將每個類型的產品假設成一個產品，此時原有的生產序列DT可以簡化為dt。

等待時間為：

另外，定義t′i為一個產品i的生產時間，其中i=1,2,…,m，生產線上所有產品i的生產總時間ti為：

其中，ni,line為生產線上產品i的數量。

所有產品的生產時間為：

產品總的生產時間為：

時間成本與生產時間呈正相關，因此生產成本為：

其中，kct表示成本C1與時間T之間的正相關系數。

每種類型的產品在緩沖區的數量為ni，其中i=1,2,…,m。

所有產品的數量為：

儲存成本與儲存數量也呈正相關，因此儲存成本為：

其中，kcn表示成本C2與數量N之間的正相關系數。

因此調度問題目標函數為：

其中，q1、q2分別表示生產成本和儲存成本的權重系數。

上述在緩沖區的產品數量均為生產線機器運行后的數量。

3.2 約束

（1）緩沖區庫存數量。每種型號的緩沖區庫存的數量ni需要滿足：

其中，ni,min是型號i在緩沖區的安全庫存；ni,max是型號i在緩沖區的最大庫存。

（2）生產線數量。對于可靠的生產，型號i在生產線上數量ni,line必須滿足：

其中，n0,i為生產線開機前型號i的初始數量。

3.3 混合算法框架

圖1為遺傳算法和差分進化的混合算法框架流程圖。該混合算法可以解決調度問題中同時存在的離散排序問題以及連續數量問題。以下是詳細的程序：

步驟1設置遺傳算法和差分進化算法的初始參數，包括初始種群數量、突變率、交叉率、約束條件和終止條件等。

步驟2設置初始種群。

步驟3根據適應度函數評價個體的適應度。

步驟4選出最優解并記錄。

步驟5如果滿足終止條件則轉到步驟9，如果不滿足終止條件則轉到步驟6。

步驟6對基因的排序采用遺傳算法的選擇、交叉、變異操作；同時基因的數量采用差分進化算法的變異、交叉、選擇操作。

步驟7根據適應度函數評價新個體的適應度。

步驟8新個體與原個體置換形成下一代個體，并轉到步驟4。

步驟9輸出最優解。

圖1 遺傳算法與差分進化算法混合算法流程圖

從以上流程圖中可以看出，遺傳算法解決了生產線上所有產品的排序問題，差分進化算法則解決了產品的生產數量問題。將兩種算法結合可以同時更好地解決排序及數量問題。

3.3.1 編碼

本文的遺傳算法使用字符串編碼方式，即每個染色體為一個字符串，一個字符串表示一個生產序列，染色體里面的每個基因代表一個待生產的產品型號。本研究的調度是基于產品的相似度，因此多個相同型號的產品可用一個基因表示。染色體片段如下：

其中A、B、C、D、…、O、P、Q、R等表示生產序列中的一個待生產的產品型號。示例中的加工順序為：型號A→型號B→型號C→型號D→…→型號O→型號P→型號Q→型號R。

對應于上述遺傳算法中每個染色體使用字符串，差分進化算法使用數字串編碼方式，數字串表示方式如下：

其中每個數字表示生產序列中待生產產品型號的數量。

3.3.2 適應度函數

本文混合框架中遺傳算法和差分進化算法均是通過適應度來衡量個體的優良程度，越接近最優解則適應度越高。較高適應度的個體有更大的概率遺傳到下一代，反之亦然。適應度函數為衡量每個個體適應度高低的函數。優化目標是使生產成本最低，為方便計算，適應度函數采用目標函數的變式，即：

其中，fp的含義參考式（10）。

3.3.3 進化策略

在遺傳算法中，進入下一代的個體必須是適應度相對理想的，適應度不理想的個體將被淘汰。進化方法一般有精英選擇和輪盤賭。精英選擇是直接選出適應度強的個體進入下一代。輪盤賭的方式則按照每個個體適應度所占總適應度的比例選擇進入下一代。本文選擇兩者結合的方式，先選出這一代中表現好的m個個體直接進入下一代，這一層選擇是精英選擇。然后從剩下的個體中采用輪盤賭的方式選擇個進入下一代。用Pr(di)表示個體di被選中的概率。

當i≤m時：

這種方式保留了最優個體，同時保證了種群的多樣性，更大程度地保證了下一代的質量。

差分進化算法中的進化策略采用的是貪婪算法。通過比較經過變異、交叉完畢的染色體和原有染色體的適應度函數值來選擇。其中變異和交叉算子在算子選擇部分進行詳細介紹。

3.3.4 算子的選擇

根據本研究的具體情況，對算子進行了一定的改進。

（1）遺傳算法

遺傳算法中的交叉算子是產生新個體的主要方法。本文采用順序交叉的方式，即在父代的一方d1中隨機選出一段染色體作為原始后代，再從父代的另一方d2中選出剩余的染色體按照順序補充到新的子代1染色體上。圖2為順序交叉示例。

圖2 遺傳算法順序交叉示例

同理在父代d2中隨機選出一段染色體作為原始后代，再從父代d1中補充剩余的片段可以形成新的子代2染色體。

遺傳算法的變異運算一般包括反轉、插入、移位、互換等，本文采用互換的方式，隨機選取基因的兩個位置進行互換。圖3為變異的示例。

圖3 遺傳算法變異運算示例

（2）差分進化算法

差分進化算法需先進行變異再進行交叉操作。此算法通過差分策略實現個體變異，可以應用于連續變量中。本研究在種群中隨機挑選不同的兩個個體，兩個個體進行向量差的同比例減小，再與待變異的個體進行合成，即：

其中，F為縮放因子；xi(g)表示第g代中的第i個個體。在變異進化過程中，需判斷新產生的中間體是否滿足邊界條件，如果超出了邊界，則要重新生成中間體。若每代種群數量記為N，則會生成N個變異中間體。然后對第g代種群及其變異的中間體進行個體間的交叉操作。

當rand(0,1)≤CR或者j=jrand時：

反之：

其中，CR為交叉概率；j為基因位置，jrand為[1,2,…,D]的隨機整數。圖4為6個基因位的染色體交叉運算示意圖。

圖4 差分進化交叉運算示例

3.3.5 終止條件

根據本研究的具體情況，如果算法滿足預先設定的迭代數，則迭代會被終止。

4 結果分析

為了驗證混合遺傳算法對存在緩沖區的混流裝配車間調度問題的有效性，采用了具體的生產數據進行驗證。

實例為需要生產A、B、C、D、E、F共6種型號的產品，初始狀態全部存放于緩沖區中。各種型號產品在緩沖區的初始數量及緩沖區的最高最低庫存量如表1所示。

生產不同型號的產品需要一定的轉換等待時間，每個型號的產品也需要一定的生產時間。生產不同型號產品的等待時間如表2所示。

表1 緩沖區中各種型號產品數量狀態表

表2 各產品之間等待時間

在表2中，先生產A再換型號A的等待時間為0，先生產A再換型號B的等待時間為80 s，先生產A再換型號C的等待時間為60 s，以此類推。需要注意的是先生產A再換型號B的等待時間與先生產B再換型號A的等待時間是不同的。各型號單個產品的生產時間如表3所示。

表3 各型號產品生產時間

按照本文提出的混合遺傳算法進行編程，設置初始種群大小為100，迭代次數為100，遺傳算法[18]和差分進化算法[19]的交叉概率均為0.9，遺傳算法的變異概率為0.02，差分進化算法的變異概率為0.5。鑒于車間的實際情況，根據專家經驗設置時間成本和庫存成本的系數分別為1、4.5；kcn和kct均取1。圖5為混合算法迭代曲線。從圖中可以看出，無論是最優目標值還是平均目標值都能夠快速地收斂。

圖5 混合算法迭代曲線

產品生產狀態穩定后各零部件在生產線上的順序及生產數量如圖6。

圖6 各產品生產數量和順序狀態

此時最優目標值為10281。各產品在車間2內的生產時間狀態如圖7。圖7中紅色區域代表等待時間，黑色區域代表生產時間。先生產E，然后再生產B的時候需要一定的等待轉換時間然后再生產B，以此類推。

圖7 各產品生產時間狀態

本文分別采用傳統遺傳算法和差分進化算法求解此實例，并將結果與混合遺傳算法對比，仿真結果如圖8所示。從圖8的對比曲線可以看出：遺傳算法的收斂速度最快，但在一個相對比較大的目標值處就趨于穩定；差分進化算法趨于穩定的目標值相對遺傳算法更低，但其收斂速度較慢；與遺傳算法及差分進化算法相比，混合遺傳算法的收斂速度相對較快，并能在更低的目標值處趨于穩定。由此可見，對于本文提出的調度問題，混合遺傳算法具有收斂速度快，優化能力強，算法可靠等優勢。

圖8 3種算法仿真結果對比曲線

5 結論

本文針對含有緩沖區混流裝配調度問題，建立了以最小時間成本和最小庫存成本為優化目標的混流裝配生產數學模型，該模型同時含有離散變量和連續變量。為求解該數學模型，本文提出了一種新的混合遺傳算法。此混合算法彌補了遺傳算法和差分進化算法的缺陷，同時融合了兩種傳統算法的優點。通過算例表明，與傳統算法相比，所設計的混合遺傳算法在求解混流裝配調度問題中收斂速度相對較快，并能在更低的目標值處趨于穩定，進一步驗證了該算法的有效性和優越性。