杜 斌，郭帝江

(中國(guó)電子科技集團(tuán)公司第二研究所，山西 太原 030024)

1 緒言

隨著電鍍生產(chǎn)工藝流程越來(lái)越復(fù)雜，以及電鍍產(chǎn)品呈現(xiàn)出小批量多品種的態(tài)勢(shì)，這就需要電鍍企業(yè)在電鍍行車(chē)柔性調(diào)度方面達(dá)到更高層次的自動(dòng)化、智能化[1]。通過(guò)學(xué)習(xí)發(fā)現(xiàn)國(guó)內(nèi)外許多針對(duì)先進(jìn)電鍍產(chǎn)線(xiàn)制造系統(tǒng)[2-4]，鍍件在工位間的搬運(yùn)動(dòng)作基本都是由計(jì)算機(jī)控制的電鍍行車(chē)完成。目前，行車(chē)調(diào)度問(wèn)題主要依賴(lài)于混合整數(shù)規(guī)劃、分支定界以及繪畫(huà)行車(chē)運(yùn)行圖等精確算法[5,6]。但上述算法只適用于求解小規(guī)模調(diào)度問(wèn)題，在大規(guī)模復(fù)雜行車(chē)調(diào)度問(wèn)題上，只能依靠智能算法求解。因此，對(duì)具備柔性調(diào)度的電鍍行車(chē)而言能極大的提高整個(gè)生產(chǎn)線(xiàn)的生產(chǎn)效率，提升產(chǎn)品質(zhì)量有著非常重大的意義。

本文依據(jù)企業(yè)的實(shí)際生產(chǎn)需求，為具有柔性電鍍時(shí)間的電鍍行車(chē)調(diào)度問(wèn)題提出了一種改進(jìn)型遺傳算法(Improved Genetic Algorithm, IGA)。該算法中染色體編碼方式采用電鍍行車(chē)搬運(yùn)次序，依據(jù)不同行車(chē)調(diào)度特征算法產(chǎn)生了初生代種群，同時(shí)，該算法通過(guò)在交叉變異操作中運(yùn)用鄰域運(yùn)算，從而避免了迭代冗余，消除了傳統(tǒng)遺傳算法(Traditional Genetic Algorithm, TGA)中優(yōu)化種群難以保證的缺點(diǎn)，加快了收斂速度。實(shí)驗(yàn)最后通過(guò)對(duì)電鍍產(chǎn)線(xiàn)中的案例分別進(jìn)行了測(cè)試對(duì)比，驗(yàn)證了該算法的可行性和有效性。

2 調(diào)度問(wèn)題描述和模型建立

電鍍產(chǎn)線(xiàn)中調(diào)度單元基本是由一組工藝、功能槽位和電鍍行車(chē)組成。工位號(hào)為0、1、2…，N，N+1，其中0和N+1為上、下料工位。鍍件在某個(gè)工位上i的浸漬時(shí)間ti具有一定的柔性范圍，即ti的上下限值[ai，bi]。電鍍行車(chē)是負(fù)責(zé)鍍件在工位間進(jìn)行搬運(yùn)操作。行車(chē)將鍍件從工位i搬運(yùn)至i+1的動(dòng)作稱(chēng)為搬運(yùn)操作i，時(shí)間為dti(0≤i≤N)。電鍍行車(chē)在工位i到j(luò)的空載時(shí)間是Ci,j(0≤i,j≤N+1)。鍍件在工位上浸漬完成后須搬運(yùn)至下一工位，所有鍍件均已在上料區(qū)內(nèi)整備，且行車(chē)與工位有且只能處理一個(gè)鍍件。

◆ 示例模型

依據(jù)實(shí)際采用5個(gè)工位的行車(chē)調(diào)度產(chǎn)線(xiàn)，其中有效工位為3，si(0≤i≤3)表示行車(chē)搬運(yùn)i的起始時(shí)間。因此，行車(chē)的搬運(yùn)次序可看為(0,1,3,2)，在該周期起始時(shí)刻，行車(chē)會(huì)將鍍件由上料工位搬運(yùn)至工位1內(nèi)，等待完成s1后再搬運(yùn)至工位2，緊接著會(huì)空載行駛至工位3，并在s3取出在工位3內(nèi)的鍍件放置下料區(qū)，隨后空載行駛至工位2，在s2搬運(yùn)鍍件進(jìn)入工位3，行車(chē)?yán)^續(xù)空載行駛至上料區(qū)，在T繼續(xù)下個(gè)周期運(yùn)作。

為了便捷，將周期內(nèi)的搬運(yùn)次序定義為X=([0],[1],[2],…，[N])，si表示搬運(yùn)i的起始時(shí)刻(0≤i≤N)。因此，鍍件在工位i內(nèi)的浸漬時(shí)間ti就是

ti=si-(si-1+di-1)+yiT.

(1)

(1)式中，當(dāng)si>si-1時(shí)，yi=0表示搬運(yùn)動(dòng)作i-1和搬運(yùn)動(dòng)作i搬運(yùn)同一個(gè)鍍件；相反，si

可得出電鍍行車(chē)搬運(yùn)調(diào)度問(wèn)題的模型：minT。即：

s[i]≥0，0≤i≤N.

(2)

s[i]>s[i]-1時(shí)，yi=0；反之，yi=1.

(3)

s[N]+d[N]+c[N]+1,0≤T.

(4)

s[i]+d[i]+c[i]+1,[i+1]≤s[i+1].

(5)

a[i]≤s[i]-(s[i]-1+d[i]-1)+yiT≤b[i].

(6)

式(2)、(3)為鍍件搬運(yùn)過(guò)程中的約束條件；式(4)、(5)為電鍍行車(chē)搬運(yùn)約束條件,因此可將所研究的問(wèn)題轉(zhuǎn)化稱(chēng)為尋求一組電鍍行車(chē)搬運(yùn)周期次序X，使得該次序下周期T時(shí)間最小化。

3 改進(jìn)型遺傳算法結(jié)構(gòu)的設(shè)計(jì)

3.1 算法編碼

遺傳算法作為全局尋優(yōu)的智能方法，在解決大規(guī)模調(diào)度問(wèn)題中得到了廣泛應(yīng)用。本次算法采用行車(chē)搬運(yùn)次序的染色體編碼方式，將搬運(yùn)隊(duì)列作為其“基因序列”，即X=(x0,x1,…，xN)為一個(gè)基因組。在圖1示例中，對(duì)應(yīng)的染色體編碼為X=(0,1,3,2)。

圖1 五個(gè)工位的產(chǎn)線(xiàn)調(diào)度示意圖

3.2 初生代種群架構(gòu)

初始種群的質(zhì)量對(duì)算法后續(xù)優(yōu)化有重要的影響，通過(guò)對(duì)電鍍行車(chē)調(diào)度特征的研究，發(fā)現(xiàn)可行基因序列(可行搬運(yùn)作業(yè)順序)必須滿(mǎn)足以下性質(zhì)：

1) 在產(chǎn)線(xiàn)中每個(gè)周期內(nèi)，只準(zhǔn)許一個(gè)鍍件進(jìn)行和離開(kāi)，并且行車(chē)每個(gè)周期內(nèi)在每個(gè)工位上只能搬運(yùn)一次；

2) 當(dāng)鍍件進(jìn)入上料位后，若有K個(gè)工位被先前進(jìn)入的鍍件占用，則這K個(gè)被占用的工位上的搬運(yùn)一定優(yōu)先于近前工位上的搬運(yùn)動(dòng)作；

3) Chen等[14]對(duì)電鍍產(chǎn)線(xiàn)中最大鍍件數(shù)Kmax值的求解做了詳細(xì)敘述。只有當(dāng)k≤Kmax時(shí)，行車(chē)搬運(yùn)次序才具備可行性。

因此，新初始種群的具體思路為：首先需要計(jì)算Kmax的值，分別設(shè)k為1，2，3，…，Kmax，隨機(jī)產(chǎn)生k個(gè)鍍件在工位上的P種排列情況，然后產(chǎn)生出滿(mǎn)足以上三個(gè)性質(zhì)的初始基因種群。

3.3 算法適應(yīng)度函數(shù)

為了保證進(jìn)入下一代的個(gè)體更加優(yōu)良，算法中選擇了經(jīng)典的輪盤(pán)賭，即將上代中最優(yōu)的個(gè)體隨機(jī)替換掉下代中基因個(gè)體，從而保證該遺傳算法的尋最優(yōu)值繼續(xù)進(jìn)行。

因本文研究對(duì)象為行車(chē)調(diào)度問(wèn)題的目標(biāo)為最優(yōu)周期T，因此，適應(yīng)度函數(shù)為

F(X)=(Tmax-T)/Tmax.

(7)

其中:Tmax為種群中最大的周期，T為基因個(gè)體X對(duì)應(yīng)的周期。

3.4 驗(yàn)證算法有效可行性

為了檢驗(yàn)提出的算法是否具備有效性，該試驗(yàn)分別應(yīng)用IGA和TGA對(duì)六組行車(chē)調(diào)度問(wèn)題的基準(zhǔn)案例進(jìn)行測(cè)試比較。

假設(shè)電鍍生產(chǎn)線(xiàn)由13個(gè)含有各種化學(xué)液體的工藝槽和一個(gè)負(fù)責(zé)搬運(yùn)鍍件的行車(chē)構(gòu)成，鍍件被行車(chē)依次搬運(yùn)至工藝槽中接受除油、清洗、活化、電鍍、鈍化、烘干等電鍍工序，其中鍍件在每個(gè)處理槽中的浸漬時(shí)間被限定在一定時(shí)間范圍內(nèi)。六組行車(chē)調(diào)度問(wèn)題基準(zhǔn)案例的具體參數(shù)，如工位數(shù)N，浸漬時(shí)間范圍[ai,bi]，行車(chē)搬運(yùn)過(guò)程時(shí)間di和空載時(shí)間cij等都按照各自需要進(jìn)行設(shè)置。同時(shí)，為了確保IGA和TGA兩個(gè)算法的具備可比性，人為的將TGA和IGA的種群規(guī)模設(shè)置成相同，交叉概率Pc=0.6，變異概率Pm=0.9，算法的最大迭代次數(shù)為800。

表1中第1、2行數(shù)據(jù)分別表示為IGA和TGA產(chǎn)生初代種群中可行染色體比例，第3行為算法種群規(guī)模。由表1中數(shù)據(jù)可以看出，在每個(gè)試驗(yàn)組內(nèi)IGA初始種群可行染色體比例明顯均優(yōu)于TGA的初始種群可行染色體比例。

表1 IGA和TGA初始種群

從表2中數(shù)據(jù)可以得出，IGA和TGA兩個(gè)算法都可以在較短的時(shí)間內(nèi)求到最優(yōu)解。但在滿(mǎn)意解方面，IGA的滿(mǎn)意解優(yōu)化更勝于TGA。

表2 IGA和TGA運(yùn)行結(jié)果

圖2中所示IGA和TGA這兩個(gè)算法在示例中求解后的收斂曲線(xiàn)圖。由圖可得出IGA算法更加能夠接近最優(yōu)解，同時(shí)，由于算法過(guò)程中加入了相鄰局部搜索方法，繼而保證后續(xù)運(yùn)算中IGA算法不斷向最優(yōu)解方向快速收斂。因此，可以得出本文所涉及到的IGA更為有效。

圖2 IGA和TGA案例收斂曲線(xiàn)

4 結(jié)論

本文針對(duì)從電鍍行業(yè)生產(chǎn)特點(diǎn)出發(fā)，為具有柔性電鍍時(shí)間的電鍍行車(chē)調(diào)度問(wèn)題提出了一種改進(jìn)型遺傳算法IGA。該算法中染色體編碼方式采用電鍍行車(chē)搬運(yùn)次序，依據(jù)不同行車(chē)調(diào)度特征算法產(chǎn)生了初生代種群，同時(shí)，該算法通過(guò)在交叉變異操作中運(yùn)用鄰域運(yùn)算，從而避免了迭代冗余，消除了TGA中優(yōu)化種群難以保證的缺點(diǎn)，加快了收斂速度。試驗(yàn)案例的實(shí)驗(yàn)結(jié)果表明，該算法在求解電鍍產(chǎn)線(xiàn)中柔性電鍍時(shí)間行車(chē)調(diào)度問(wèn)題上具備了更高的可行性和有效性。同時(shí)，該算法已逐步應(yīng)用于當(dāng)前電鍍產(chǎn)線(xiàn)控制系統(tǒng)中，表現(xiàn)良好，運(yùn)行穩(wěn)定。