基于內(nèi)共生算法的混裝線平衡和排序協(xié)同優(yōu)化*

王 壯，張新敏

(沈陽工業(yè)大學(xué)機械工程學(xué)院，沈陽 110870)

0 引言

隨著柔性更高的混流裝配線在市場中得到更加廣泛的應(yīng)用，如何進行混流裝配線的優(yōu)化，成為急需解決的問題。平衡和排序是影響混流裝配線的兩個關(guān)鍵因素。這兩個互相獨立又緊密聯(lián)系的因素共同決定了混流裝配線的優(yōu)劣，國內(nèi)外學(xué)者也針對這兩個問題進行了大量的研究。

大多數(shù)學(xué)者在對混流裝配線進行優(yōu)化時，單獨的進行平衡或排序研究。針對平衡的研究主要分為兩類：第一類是混流裝配線初次平衡的靜態(tài)研究[1-3]；第二類是混流裝配線再平衡的動態(tài)研究[4-5]。針對排序的研究主要分為三類：第一類是負(fù)載均衡問題的研究[6-7]；第二類是生產(chǎn)平準(zhǔn)化問題的研究[8-9]；第三類是產(chǎn)品相似性問題的研究[10-11]。以上研究在優(yōu)化過程中沒有考慮到平衡和排序之間的相互影響，單獨的考慮平衡和排序難以達到整體最優(yōu)。

因此一些學(xué)者開始同時考慮平衡和排序，以求得混流裝配線的整體最優(yōu)。文獻[12-13]以平衡方向的負(fù)載均衡等指標(biāo)進行整體方案的評價，求得使整體最優(yōu)的組合解。文獻[14-15]以排序方向超載工作等指標(biāo)，利用協(xié)同進化算法求得平衡和排序的最優(yōu)組合方案。這些研究同時考慮平衡和排序兩個因素，但評價指標(biāo)偏向平衡或排序單個方面，不是對組合方案的整體評價，難以求得整體最優(yōu)的問題沒有得到很好解決。

本文在混流裝配線優(yōu)化的過程中，同時考慮平衡和排序兩個因素，設(shè)計出平衡和排序組合方案的整體評價指標(biāo)。以實際負(fù)載均衡和實際閑置時間最小為目標(biāo)，構(gòu)建混流裝配線平衡和排序協(xié)同優(yōu)化模型。對協(xié)同進化算法進行改進，設(shè)計出內(nèi)共生進化算法進行模型的求解，求得的組合方案能使混流裝配系統(tǒng)達到整體的最優(yōu)。

1 混流裝配線協(xié)同優(yōu)化模型

1.1 參數(shù)定義

1.2 問題描述

混流裝配線是在一條裝配線上同時生產(chǎn)M個品種的產(chǎn)品，M個產(chǎn)品的總需求量為D，每種產(chǎn)品的需求量為Dm，各操作任務(wù)的時間和優(yōu)先關(guān)系已知?；炝餮b配線平衡問題的研究是通過綜合優(yōu)先關(guān)系，將多產(chǎn)品轉(zhuǎn)換成單產(chǎn)品進行研究?；炝餮b配線排序問題的研究是采用循環(huán)排序法，只對一個MPS中的產(chǎn)品排序，通過重復(fù)一定次數(shù)的排序循環(huán)，實現(xiàn)對所有產(chǎn)品的排序?；炝餮b配線平衡和排序協(xié)同優(yōu)化是在一定的資源限制下，對混流裝配線系統(tǒng)的整體進行優(yōu)化，在求解過程中利用平衡和排序之間的相互影響，同時進行平衡和排序問題的研究，求解出使混流裝配線整體最優(yōu)的平衡和排序的組合方案。

1.3 模型建立

混流裝配線協(xié)同優(yōu)化的關(guān)鍵的因素是組合方案評價指標(biāo)的設(shè)計，優(yōu)秀的評價指標(biāo)能夠快速地求出質(zhì)量更高的解。傳統(tǒng)的評價指標(biāo)準(zhǔn)主要是針對平衡或排序單方面進行設(shè)計，以應(yīng)用最多的ADW(絕對負(fù)載偏差)為例，表達式如下：

(1)

(2)

(3)

由表達式可知，ADW在衡量負(fù)載偏差時以分配到各工作站操作任務(wù)的時間為基礎(chǔ)進行計算，這個時間是理論上各工位的工作時間。在單獨進行平衡研究時，可以將理論時間作為此工位的工作負(fù)載進行均衡優(yōu)化。在實際中不同的排序方案會使各工位內(nèi)產(chǎn)生不同的閑置時間，閑置時間雖然不是負(fù)載，但它會影響產(chǎn)品在工作站的停留時間，此時各工位內(nèi)的實際工作時間和理論工作時間之間會存在偏差。在這種計算方式下各工位間的負(fù)載雖然均衡，但產(chǎn)品在各工作站的停留時間并不均衡，在實際生產(chǎn)中會造成各工位忙閑不均，長時間運行會產(chǎn)生在制品堆積等問題。

本文在進行組合方案評價指標(biāo)的設(shè)計時，綜合考慮平衡和排序之間的相互影響，以一個MPS內(nèi)的各工作站內(nèi)的工作時間和閑置時間之和為實際負(fù)載進行均衡優(yōu)化。同時對閑置時間進行限制，避免閑置時間過多造成生產(chǎn)浪費。實際負(fù)載求解過程如下。

序列中第1個產(chǎn)品m1在工作站1開始和結(jié)束的時間：

Z11=0；

E11=Z11+Tm1,1

序列中第1個產(chǎn)品m1在工作站j的開始和結(jié)束時間：

Z1j=Z1，j-1+Tm1，j-1

E1j=Z1j+Tm1，j

序列中第s個產(chǎn)品ms在工作站1開始和結(jié)束的時間：

Zs1=Zs-1，1+Tms-1，1

Es1=Zs1+Tms，1

序列中第s個產(chǎn)品在第j個工作站中的開始和結(jié)束時間：

Zsj=max{Es,j-1,Es-1,j}

Esj=Zsj+Tms，j

實際負(fù)載是最后一個產(chǎn)品在某個工作站結(jié)束的時間，減去第一個產(chǎn)品在這個工作站開始的時間：ALj=ESj-Z1j。

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

(4)

f2=min(idtsj)

(5)

約束條件：

ALy=Esj-Z1j

(6)

(7)

(8)

(9)

(10)

(11)

Es,j+1-Tms,j+1≥Esj

(12)

Es-1,j-Tms-1,j≥Esj

(13)

式(4)、式(5)為目標(biāo)函數(shù)，求最小的實際負(fù)載偏差和和最小的閑置時間；式(6)、式(7)是實際負(fù)載偏差和閑置時間的計算公式；式(8)保證一個任務(wù)只能分配到一個工作站；式(9)保證一個位置上只能安排一個產(chǎn)品；式(10)保證一個序列產(chǎn)品的總數(shù)目等于一個MPS中產(chǎn)品的總數(shù)目；式(11)保證各操作任務(wù)滿足優(yōu)先關(guān)系；式(12)保證產(chǎn)品只有在本工位加工完成后才能在下一個工位進行加工；式(13)保證在本工作站內(nèi)只有加工完當(dāng)前產(chǎn)品，才能進行下一個產(chǎn)品的加工。

2 內(nèi)共生進化算法

內(nèi)共生進化算法來自文獻[16]提出的共生理論，是在協(xié)同進化算法的基礎(chǔ)上進行改進。在內(nèi)共生進化算法中存在兩個或兩個以上的種群，每個種群中的個體代表整體問題的部分解，不同種群中個體的相互組合，代表整個問題的完整解。該算法的顯著特點是它保持了個體及其共生伙伴的結(jié)合。內(nèi)共生的存在可以加速個體向好的解決方案收斂的速度。

2.1 算法的設(shè)計

在內(nèi)共生進化算法中構(gòu)建了3個種群：平衡種群(Pop-B)、排序種群(Pop-S)和組合種群(Pop-BS)。其中平衡和排序種群中的個體代表著任務(wù)分配方案和產(chǎn)品的排序方案，是問題的部分解。組合種群中的每個體是平衡和排序個體的組合體代表問題的完整解。在算法中存在兩種進化機制：協(xié)同進化和內(nèi)部競爭。種群Pop-B中的個體和種群Pop-S中的個體協(xié)同進化，并相互結(jié)合成新的組合種群Pop-BS’。新組合種群Pop-BS’和舊組合種群Pop-BS通過互換優(yōu)秀的個體來淘汰種群內(nèi)部低劣的個體，原組合種群中優(yōu)秀的個體保持不變，算法示意如圖1所示。

圖1 內(nèi)共生算法進化圖

2.2 算法的流程

內(nèi)共生進化算法的流程如下：

步驟1：種群初始化

①生成平衡和排序的初始種群Pop_B0和Pop_S0；

②由Pop_B0和Pop_S0結(jié)合生成組合種群的初始種群Pop_BS0。

步驟2：計算種群Pop-BS0的適應(yīng)度，并保存適應(yīng)度最大的個體Pop-BSbest0和最大適應(yīng)度值fbest0(Pop_BS0);

步驟3：協(xié)同進化

①對平衡種群進行選擇、交叉、變異操作生成新平衡種群Pop_B1；

②平衡種群Pop_B1中的所有個體和最佳組合個體Pop-BSbest0的排序部分進行組合生成新的組合種群Pop_BS1；

③計算新的組合種群Pop_BS1的適應(yīng)度，求出適應(yīng)度最大的個體Pop-BSbest1和最大適應(yīng)度值fbest1(Pop_BS1)；

④若fbest1(Pop_BS1)>fbest0(Pop_BS0),則更新最佳組合個體和最大適應(yīng)度值；進行步驟⑤

⑤同理對排序種群進行①～④操作；

步驟4：內(nèi)部競爭

①對組合種群Pop_BS0進行選擇、交叉、變異操作生成新的組合種群Pop_BS3；

②交換組合種群Pop_BS3和步驟3中得到的組合種群Pop_BS1、Pop_BS2中優(yōu)秀的個體以淘汰種群內(nèi)部低劣的個體，原種群中用于交換的優(yōu)秀的個體保持不變；

步驟5：若滿足終止條件程序終止，否則轉(zhuǎn)至步驟③。

2.3 算法進化操作

對于平衡和排序問題的遺傳和進化操作的研究已經(jīng)相當(dāng)成熟，本文在前人的基礎(chǔ)上重點研究組合個體的遺傳表達和進化操作。以數(shù)字序列[1,5,3,4,2,6]代表平衡序列，字母序列[ABBACC]代表排序序列，組合序列的編碼如圖2所示。頭部代表平衡序列尾部代表排序方案。

圖2 組合個體表達方式

在染色體進化產(chǎn)生新的個體時，分兩步進行：①先分別對頭部和尾部進行交叉操作，生成新的個體；②分別對頭部和尾部進行變異操作產(chǎn)生新的個體。這里針對頭部和尾部進行的交叉和變異操作采用平衡和排序單個體一樣的交叉和變異操作。

3 模型的求解與算法的驗證

3.1 算例描述

為驗證混流裝配線平衡和排序協(xié)同優(yōu)化模型和內(nèi)共生進化算法的有效性，本文通過對Thomopoulos[17]問題的求解進行驗證。在Thomopoulos問題中一個MPS中三種產(chǎn)品的比例為[3 2 1]；三種產(chǎn)品的綜合操作時間為[100 144 28 48 44 24 102 50 74 8 66 50 16 44 204 6 90 78 66]；三種產(chǎn)品的綜合優(yōu)先關(guān)系如圖3所示。

圖3 Thomopoulos問題三種產(chǎn)品優(yōu)先關(guān)系

以實際負(fù)載偏差和閑置時間最小為目標(biāo)建立數(shù)學(xué)模型，分別采用遺傳算法(GA)、協(xié)同進化算法(EA)和內(nèi)共生進化算法(EAA)進行求解。

遺傳算法采用傳統(tǒng)串行的求解方式，先對混流裝配線平衡問題進行求解，在已得平衡方案的基礎(chǔ)上進行排序問題的求解，求得使整體最優(yōu)的平衡和排序組合方案；協(xié)同進化算法采用并行求解方式，將整體解分成平衡和排序兩個部分，求解時兩個部分相互組合協(xié)同進化，求得使整體最優(yōu)的組合解；內(nèi)共生進化算法在協(xié)同進化算法中加入內(nèi)共生體(平衡和排序組合個體)，內(nèi)共生種群和協(xié)同進化種群互換較好的個體，以淘汰中群內(nèi)低劣的個體。

3.2 參數(shù)設(shè)置

平衡種群、排序種群和組合種群的初始規(guī)模都為100，變異率為0.8，交叉率為0.2，兩個種群最優(yōu)基因交換的數(shù)目為5，工作站數(shù)為3，迭代次數(shù)為500次。

3.3 結(jié)果對比

分別使用三種算法對Thomopoulos問題進行求解，三種算法求得的最佳組合方案如圖4～圖6所示。

圖4 EAA求解結(jié)果

圖5 EA求解結(jié)果

圖6 GA求解結(jié)果

三種算法求解的目標(biāo)函數(shù)值如表1所示。表中是每個算法運行10次目標(biāo)函數(shù)的平均值，其中提升率是協(xié)同進化算法和內(nèi)共生進化算法相對于遺傳算法目標(biāo)函數(shù)函數(shù)的提升，計算公式為：{(EEA-GA)/GA}×100%。

表1 三種算法求解結(jié)果

由結(jié)果可知：傳統(tǒng)以串行的方式進行平衡和排序問題的求解結(jié)果最差，傳統(tǒng)的串行求解思路只能求得平衡或排序的部分最優(yōu)，無法求得平衡和排序的組合最優(yōu)，并且傳統(tǒng)算法在求解集成問題時，解的搜索效率和搜索能力較差。

在并行求解思路中內(nèi)共生進化算法的求解結(jié)果最好，這說明與協(xié)同進化算法相比，內(nèi)共生進化算法在求解過程中，通過不同種群間優(yōu)秀內(nèi)共生體的交換不僅能夠加種群的多樣性，避免算法早熟，而且還能夠提升解的質(zhì)量和求解效率。

如圖7所示展示了目標(biāo)函數(shù)隨著迭代次數(shù)的收斂曲線，由收斂曲線可知內(nèi)共生和協(xié)同進化算法相比于遺傳算法，在尋優(yōu)能力和收斂性方面的得到很大的提升。在三種算法中內(nèi)共生進化算法的收斂速度最快，求解結(jié)果最好，在求解集成問題時具有更大的優(yōu)勢。

圖7 三種算法收斂圖

4 結(jié)束語

(1)對混流裝配系統(tǒng)進行分析發(fā)現(xiàn)，傳統(tǒng)串行求解方式和偏向性評價指標(biāo)，無法綜合考慮平衡和排序之間的聯(lián)系，難以求得系統(tǒng)的整體最優(yōu)方案；

(2)并行求解方式和綜合性評價指標(biāo)相結(jié)合的模型，能夠彌補傳統(tǒng)串行求解方式難以達到整體最優(yōu)的缺陷；(3)通過算例驗證了模型的可行性，并且內(nèi)共生進化算法與另外兩種算法相比，具有更佳的尋優(yōu)能力和收斂性。