一種新型混合算法在混流裝配調(diào)度中的應(yīng)用

婁高翔，蔡宗琰，劉清濤

LOU Gaoxiang,CAI Zongyan,LIU Qingtao

長安大學(xué) 工程機械學(xué)院，西安 710064

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

1 引言

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

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

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

2 問題描述

在連續(xù)的兩個混流裝配車間中，往往布置緩沖區(qū)來保證生產(chǎn)平順性，即通過預(yù)先安排好一部分制造資源，來緩解生產(chǎn)過程中不同環(huán)節(jié)之間生產(chǎn)節(jié)拍不一致帶來的瓶頸問題。各車間可通過緩沖區(qū)的排序功能來調(diào)整產(chǎn)品的順序。

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

3 模型建立

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

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

3.1 目標函數(shù)

此調(diào)度問題的目標函數(shù)是盡量減少生產(chǎn)成本，包括在整個調(diào)度范圍內(nèi)生產(chǎn)所有產(chǎn)品的總時間成本和緩沖區(qū)的儲存成本。

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

定義不同種類產(chǎn)品之間的等待時間：

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

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

等待時間為：

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

其中，ni,line為生產(chǎn)線上產(chǎn)品i的數(shù)量。

所有產(chǎn)品的生產(chǎn)時間為：

產(chǎn)品總的生產(chǎn)時間為：

時間成本與生產(chǎn)時間呈正相關(guān)，因此生產(chǎn)成本為：

其中，kct表示成本C1與時間T之間的正相關(guān)系數(shù)。

每種類型的產(chǎn)品在緩沖區(qū)的數(shù)量為ni，其中i=1,2,…,m。

所有產(chǎn)品的數(shù)量為：

儲存成本與儲存數(shù)量也呈正相關(guān)，因此儲存成本為：

其中，kcn表示成本C2與數(shù)量N之間的正相關(guān)系數(shù)。

因此調(diào)度問題目標函數(shù)為：

其中，q1、q2分別表示生產(chǎn)成本和儲存成本的權(quán)重系數(shù)。

上述在緩沖區(qū)的產(chǎn)品數(shù)量均為生產(chǎn)線機器運行后的數(shù)量。

3.2 約束

（1）緩沖區(qū)庫存數(shù)量。每種型號的緩沖區(qū)庫存的數(shù)量ni需要滿足：

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

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

其中，n0,i為生產(chǎn)線開機前型號i的初始數(shù)量。

3.3 混合算法框架

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

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

步驟2設(shè)置初始種群。

步驟3根據(jù)適應(yīng)度函數(shù)評價個體的適應(yīng)度。

步驟4選出最優(yōu)解并記錄。

步驟5如果滿足終止條件則轉(zhuǎn)到步驟9，如果不滿足終止條件則轉(zhuǎn)到步驟6。

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

步驟7根據(jù)適應(yīng)度函數(shù)評價新個體的適應(yīng)度。

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

步驟9輸出最優(yōu)解。

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

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

3.3.1 編碼

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

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

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

其中每個數(shù)字表示生產(chǎn)序列中待生產(chǎn)產(chǎn)品型號的數(shù)量。

3.3.2 適應(yīng)度函數(shù)

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

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

3.3.3 進化策略

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

當i≤m時：

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

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

3.3.4 算子的選擇

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

（1）遺傳算法

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

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

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

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

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

（2）差分進化算法

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

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

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

反之：

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

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

3.3.5 終止條件

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

4 結(jié)果分析

為了驗證混合遺傳算法對存在緩沖區(qū)的混流裝配車間調(diào)度問題的有效性，采用了具體的生產(chǎn)數(shù)據(jù)進行驗證。

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

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

表1 緩沖區(qū)中各種型號產(chǎn)品數(shù)量狀態(tài)表

表2 各產(chǎn)品之間等待時間

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

表3 各型號產(chǎn)品生產(chǎn)時間

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

圖5 混合算法迭代曲線

產(chǎn)品生產(chǎn)狀態(tài)穩(wěn)定后各零部件在生產(chǎn)線上的順序及生產(chǎn)數(shù)量如圖6。

圖6 各產(chǎn)品生產(chǎn)數(shù)量和順序狀態(tài)

此時最優(yōu)目標值為10281。各產(chǎn)品在車間2內(nèi)的生產(chǎn)時間狀態(tài)如圖7。圖7中紅色區(qū)域代表等待時間，黑色區(qū)域代表生產(chǎn)時間。先生產(chǎn)E，然后再生產(chǎn)B的時候需要一定的等待轉(zhuǎn)換時間然后再生產(chǎn)B，以此類推。

圖7 各產(chǎn)品生產(chǎn)時間狀態(tài)

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

圖8 3種算法仿真結(jié)果對比曲線

5 結(jié)論

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