婁高翔，蔡宗琰，劉清濤

LOU Gaoxiang,CAI Zongyan,LIU Qingtao

長(zhǎng)安大學(xué) 工程機(jī)械學(xué)院，西安 710064

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

1 引言

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

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

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

2 問(wèn)題描述

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

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

3 模型建立

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

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

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

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

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

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

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

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

等待時(shí)間為：

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

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

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

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

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

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

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

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

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

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

因此調(diào)度問(wèn)題目標(biāo)函數(shù)為：

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

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

3.2 約束

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

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

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

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

3.3 混合算法框架

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

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

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

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

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

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

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

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

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

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

圖1 遺傳算法與差分進(jìn)化算法混合算法流程圖

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

3.3.1 編碼

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

其中A、B、C、D、…、O、P、Q、R等表示生產(chǎn)序列中的一個(gè)待生產(chǎn)的產(chǎn)品型號(hào)。示例中的加工順序?yàn)椋盒吞?hào)A→型號(hào)B→型號(hào)C→型號(hào)D→…→型號(hào)O→型號(hào)P→型號(hào)Q→型號(hào)R。

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

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

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

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

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

3.3.3 進(jìn)化策略

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

當(dāng)i≤m時(shí)：

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

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

3.3.4 算子的選擇

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

（1）遺傳算法

遺傳算法中的交叉算子是產(chǎn)生新個(gè)體的主要方法。本文采用順序交叉的方式，即在父代的一方d1中隨機(jī)選出一段染色體作為原始后代，再?gòu)母复牧硪环絛2中選出剩余的染色體按照順序補(bǔ)充到新的子代1染色體上。圖2為順序交叉示例。

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

同理在父代d2中隨機(jī)選出一段染色體作為原始后代，再?gòu)母复鷇1中補(bǔ)充剩余的片段可以形成新的子代2染色體。

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

圖3 遺傳算法變異運(yùn)算示例

（2）差分進(jìn)化算法

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

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

當(dāng)rand(0,1)≤CR或者j=jrand時(shí)：

反之：

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

圖4 差分進(jìn)化交叉運(yùn)算示例

3.3.5 終止條件

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

4 結(jié)果分析

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

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

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

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

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

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

表3 各型號(hào)產(chǎn)品生產(chǎn)時(shí)間

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

圖5 混合算法迭代曲線

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

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

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

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

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

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

5 結(jié)論

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