王 壯，張新敏

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

0 引言

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

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

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

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

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

1.1 參數定義

1.2 問題描述

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

1.3 模型建立

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

(1)

(2)

(3)

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

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

序列中第1個產品m1在工作站1開始和結束的時間：

Z11=0；

E11=Z11+Tm1,1

序列中第1個產品m1在工作站j的開始和結束時間：

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

E1j=Z1j+Tm1，j

序列中第s個產品ms在工作站1開始和結束的時間：

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

Es1=Zs1+Tms，1

序列中第s個產品在第j個工作站中的開始和結束時間：

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

Esj=Zsj+Tms，j

實際負載是最后一個產品在某個工作站結束的時間，減去第一個產品在這個工作站開始的時間：ALj=ESj-Z1j。

目標函數：

(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)為目標函數，求最小的實際負載偏差和和最小的閑置時間；式(6)、式(7)是實際負載偏差和閑置時間的計算公式；式(8)保證一個任務只能分配到一個工作站；式(9)保證一個位置上只能安排一個產品；式(10)保證一個序列產品的總數目等于一個MPS中產品的總數目；式(11)保證各操作任務滿足優(yōu)先關系；式(12)保證產品只有在本工位加工完成后才能在下一個工位進行加工；式(13)保證在本工作站內只有加工完當前產品，才能進行下一個產品的加工。

2 內共生進化算法

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

2.1 算法的設計

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

圖1 內共生算法進化圖

2.2 算法的流程

內共生進化算法的流程如下：

步驟1：種群初始化

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

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

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

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

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

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

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

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

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

步驟4：內部競爭

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

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

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

2.3 算法進化操作

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

圖2 組合個體表達方式

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

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

3.1 算例描述

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

圖3 Thomopoulos問題三種產品優(yōu)先關系

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

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

3.2 參數設置

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

3.3 結果對比

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

圖4 EAA求解結果

圖5 EA求解結果

圖6 GA求解結果

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

表1 三種算法求解結果

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

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

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

圖7 三種算法收斂圖

4 結束語

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

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