基于果蠅算法的第二類裝配線平衡問題

杜利珍 王運發(fā) 王 震 余聯(lián)慶 李新宇

1.武漢紡織大學(xué)機械工程與自動化學(xué)院,武漢,430073 2.華中科技大學(xué)機械科學(xué)與工程學(xué)院，武漢，430074

0 引言

裝配線平衡問題研究主要集中在三個方面：①給定生產(chǎn)節(jié)拍，優(yōu)化最小工作站數(shù)；②給定最小工作站數(shù)，最小化生產(chǎn)節(jié)拍；③工作站數(shù)和生產(chǎn)節(jié)拍已定，平衡工作負(fù)荷[1]。近20年來，許多學(xué)者圍繞智能算法進行了深入研究，將它們運用到裝配線平衡問題的求解，取得了比較好的效果，其中，代表性的算法有遺傳算法[2]、蟻群算法[3]、粒子群算法[4]等。遺傳算法容易早熟，更新規(guī)則較復(fù)雜，涉及大量個體的計算，穩(wěn)定性較差；蟻群算法收斂速度慢，易陷入局部最優(yōu)；粒子群算法容易早熟收斂，局部尋優(yōu)能力較差。綜上所述，本文采用一種新的智能算法——果蠅算法來解決第二類裝配線平衡問題。

在經(jīng)典的果蠅算法中，種群中的果蠅基于氣味搜索和視覺搜索,能夠在一定的時間段中優(yōu)化搜索空間[5]。近年來，果蠅算法較多地被運用在網(wǎng)絡(luò)拍賣、物流服務(wù)、多維背包問題等問題優(yōu)化中。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

本文研究第二類裝配線平衡問題，即生產(chǎn)線的工作站數(shù)量已定，同時設(shè)定了幾個生產(chǎn)約束條件。在此基礎(chǔ)上，將有限的工序按照一種特定模式在各個不同的工作站內(nèi)進行分配，最終目的是使生產(chǎn)節(jié)拍最小[6]，且工作負(fù)荷達到平衡。

整個生產(chǎn)過程中，生產(chǎn)節(jié)拍受到生產(chǎn)工藝、場地以及各種工具的限制，因此需要考慮不同工序的優(yōu)先順序等問題[7]。在滿足生產(chǎn)約束條件之后，需要在整條裝配線上對工作站進行生產(chǎn)工序的分配，使各工作站保持一個比較均衡的作業(yè)負(fù)荷，從而實現(xiàn)生產(chǎn)節(jié)拍的最小化。

1.2 數(shù)學(xué)模型

在追求第二類裝配線平衡時，需要將所有工序分配到各工作站中，最終使生產(chǎn)節(jié)拍T達到最小，并保證整個生產(chǎn)線中的不同工作站的加權(quán)平均負(fù)荷能夠達到均衡，即不同工位的平均單件作業(yè)時間的標(biāo)準(zhǔn)方差最小。

依據(jù)上述分析，得到本次研究問題的目標(biāo)函數(shù)。

(1)裝配線的最小節(jié)拍：

minZ1=T

(1)

(2)為了平衡裝配線上各工作站的工作負(fù)荷，將負(fù)載標(biāo)準(zhǔn)差最小化設(shè)置為第二個優(yōu)化目標(biāo)，即有

(2)

式中，Tk為第k個工作站中所有作業(yè)的時間總和。

因此，本文研究的第二類裝配線平衡問題的優(yōu)化目標(biāo)由生產(chǎn)節(jié)拍最小化和負(fù)載標(biāo)準(zhǔn)差最小化共同組成，W1、W2分別代表這兩個優(yōu)化目標(biāo)的權(quán)重，從而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)問題。因此，建立總目標(biāo)函數(shù)為

minZ=W1Z1+W2Z2

(3)

對上述問題進行研究時，作如下假設(shè)[8]：①作業(yè)i的加工時間都是穩(wěn)定的；②所有的作業(yè)都被分配到工作站k中去；③一個作業(yè)只能夠分配到一個工作站；④裝配線不能夠?qū)崿F(xiàn)并行處理。上述條件轉(zhuǎn)化成為的表達式為

(4)

Sx∩Sy=?x≠y;x,y=1,2,…,N

(5)

?i∈Sx,j∈Sy,若Pij=1，則x≤y

(6)

其中，Sk為在第k個工作站中所有作業(yè)元素的集合；i、j表示作業(yè)元素，所有作業(yè)元素集合為M，即i，j∈M；Pij表示作業(yè)之間的順序關(guān)系。

式(4)表示所有的作業(yè)都被分配到工站；式(5)表示每一個作業(yè)只能夠被分配到一個工作站；式(6)表述在工作站劃分過程中，遵循作業(yè)優(yōu)先順序。

2 算法設(shè)計

2.1 基本原理及步驟

果蠅算法[9]是根據(jù)果蠅群體依據(jù)空氣中的氣味分子實現(xiàn)覓食過程開發(fā)的，算法流程如下：

(1)采用迭代方法對種群的大小進行初始化。

(2)開始時，果蠅個體的位置是隨機的，然后向不同的方位搜索。

(3)計算果蠅個體之間的距離d，將果蠅個體的味道濃度判定值Fi設(shè)置為間距的倒數(shù)。

(4)把Fi代入適應(yīng)度函數(shù)，計算得到果蠅個體的味道濃度。

(5)尋找種群中味道濃度最大的果蠅個體。

(6)將最佳味道濃度值sbest在XY坐標(biāo)系中的坐標(biāo)進行記錄、保存。

(7)對種群進行迭代，重復(fù)步驟(2)～步驟(5)。迭代后，比較迭代前后的味道濃度，查看是否得到了優(yōu)化，然后將目前的迭代值與最大值進行比較，若迭代值較小，則執(zhí)行步驟(6)，否則，結(jié)束該算法。

果蠅算法的算法流程如圖1所示。

圖1 果蠅算法流程圖Fig.1 Algorithm flow chart of fruit fly algorithm

2.2 編碼與解碼

編程設(shè)計時，首先對可行解的序列進行編碼，將其轉(zhuǎn)換成為浮點型向量。本次設(shè)計中，使用優(yōu)先權(quán)重[10]的方法對程序進行編碼、解碼，在對果蠅個體的位置進行編碼時，首先依據(jù)作業(yè)的優(yōu)先關(guān)系圖將浮點型向量轉(zhuǎn)化成為可行序列。浮點型向量中的每一個元素為0、1中的隨機數(shù)，其中，第j個元素表示的是該作業(yè)的優(yōu)先權(quán)重，值越大，作業(yè)元素排序越靠前，解碼算法流程如下：

(1)依據(jù)作業(yè)優(yōu)先圖，尋找出入度為0的作業(yè)，并將其組合成為集合V。

(2)通過V來尋找其中權(quán)重值最大的向量元素j。

(3)把尋找到的j放置到作業(yè)序列SP，并在作業(yè)順序圖中刪除作業(yè)j，然后判斷作業(yè)序列中作業(yè)個數(shù)是否為n，若作業(yè)個數(shù)達到n，則編碼結(jié)束，否則，執(zhí)行步驟(1)。

2.3 作業(yè)分配方案的生成

上述算法運行后能生成拓?fù)渑判颍粋€SP有很多個分配方案，因此在進行作業(yè)分配之前還需對方案進行分析、選擇，利用最佳方案對作業(yè)進行分配。本次設(shè)計中使用的是KIM等[11]研發(fā)的方法，通過該方法對作業(yè)進行分配，經(jīng)過不斷的迭代，使所有的作業(yè)都能均勻地分配到工作站中，算法流程[12]如下：

(1)計算最小節(jié)拍Tbest=max(Tsum/N,maxTk)，其中，Tsum為所有作業(yè)時間的總和。

(2)得到生產(chǎn)節(jié)拍理論值Tbest后，在滿足最小節(jié)拍的同時，將作業(yè)內(nèi)容盡可能地分配到前N-1個工作站中，將沒有分配的作業(yè)分配到最后的工作站。

(3)計算每一個工作站內(nèi)各作業(yè)時間的總和。

(4)取Tw=max(T1，T2，…，TN)，若Tw>Tbest，則回到步驟(2)重新計算；若Tw

3 標(biāo)桿案例

3.1 雙產(chǎn)品裝配時間測定

以某實驗教學(xué)儀器裝配線為例[13]，A、B產(chǎn)品按照2∶1的比例進行混合生產(chǎn)，對每道工序的作業(yè)時間進行了8次測量，取8次測量時間的平均值為產(chǎn)品每道工序的穩(wěn)定作業(yè)時間，得到各工序的加工時間，如表1所示。

3.2 雙產(chǎn)品優(yōu)先關(guān)系圖

A、B產(chǎn)品作業(yè)優(yōu)先關(guān)系如圖2所示。

參考文獻[13]的自適應(yīng)遺傳算法求解得到的工作站劃分，如表2所示。

表1 混合裝配線各工序加工時間ti

圖2 某公司A、B產(chǎn)品裝配線作業(yè)優(yōu)先關(guān)系圖Fig.2 A、B product assembly line job priority diagram for a company

工作站N工序i時間(s)11、2、3、27324228、29、30、35、3632234、5、6、3130649、10、14、15、3331657、22、23312611、16、24、32、34、37、3832778、17、18、19、20、39310812、13、21、25、26315

因此可知，標(biāo)桿案例中裝配線的生產(chǎn)節(jié)拍為327 s，根據(jù)生產(chǎn)線平衡率計算公式可計算出裝配線平衡率：

3.3 利用果蠅算法求解并仿真

(1)生產(chǎn)節(jié)拍的確定。該廠生產(chǎn)A、B產(chǎn)品的計劃月產(chǎn)量分別為3 740、1 870(每月工作天數(shù)以22計)，每天有效工作時間為8 h。A、B兩型產(chǎn)品以2∶1的比例混合裝配，則理論生產(chǎn)節(jié)拍TT應(yīng)為

(2)理論最小工作站數(shù)的確定。在滿足作業(yè)元素先后關(guān)系和生產(chǎn)節(jié)拍的前提下，將所有生產(chǎn)作業(yè)元素分配到裝配線的各工作站，并使所分配的工作站數(shù)為最小。理論最小工作站數(shù)可以直觀評價所求優(yōu)化方案是否達最優(yōu)，其值為

N=(859×2+814)/339=7.5≈8

(3)編碼及模型求解。本文采用基于權(quán)重編碼方式，對A、B產(chǎn)品利用優(yōu)先權(quán)重編碼的過程進行分析，隨機初始化作業(yè)單元的優(yōu)先權(quán)重為X=(0.63，0.45，0.51，0.37，0.42，0.46，0.53，0.48，0.59，0.49，0.53，0.54，0.66，0.54，0.59，0.70，0.12，0.85，0.65，0.23，0.54，0.26，0.87，0.58，0.16，0.34，0.67，0.52，0.69，0.46，0.19，0.55，0.75，0.42，0.63，0.52，0.41，0.85，0.62)。

根據(jù)果蠅算法的求解步驟，用MATLAB進行仿真求解，算法對相關(guān)參數(shù)設(shè)置如下：最大迭代次數(shù)130，種群規(guī)模100。求解得到的最優(yōu)果蠅個體為(14, 22, 27, 36, 15, 23, 35, 28, 29, 30, 32, 1, 9, 2, 33, 24, 16, 17, 20, 19, 10, 11, 3, 4, 6, 5, 18, 21, 25, 26, 7, 8, 12, 13, 37, 31, 34, 38, 39)，收斂曲線如圖3所示。

圖3 收斂曲線圖Fig.3 Convergent curve of objective function

采用果蠅算法對工作站分配模型進行求解，其工作站作業(yè)內(nèi)容如表3所示，目標(biāo)函數(shù)值324 s，即優(yōu)化后的生產(chǎn)節(jié)拍T=324 s，裝配線各工作站內(nèi)作業(yè)元素如表3所示。由表3可以計算出優(yōu)化后裝配線平衡率α為97.68%。

表3 果蠅算法優(yōu)化后各工作站劃分情況

標(biāo)桿案例采用自適應(yīng)遺傳算法和本文采用果蠅算法求解的優(yōu)化結(jié)果，如表4所示。

表4 GA與FOA求解結(jié)果對比表

由表4可知，本文采用果蠅算法的優(yōu)化結(jié)果與標(biāo)桿案例的優(yōu)化結(jié)果相比，生產(chǎn)節(jié)拍縮短了3 s，裝配線平衡率提升了0.9%，負(fù)載標(biāo)準(zhǔn)差降低了2.32 s。利用果蠅算法求解的工站工時趨于平穩(wěn)。

4 結(jié)語

本論文針對第二類裝配線平衡問題，綜合考慮生產(chǎn)節(jié)拍和各工作站平均負(fù)荷，建立雙目標(biāo)優(yōu)化模型，并采用果蠅優(yōu)化算法求解，通過對標(biāo)桿案例進行分析驗證，果蠅算法在獲取全局最優(yōu)解的能力上非常強，有效解決了在計算過程中陷入局部最優(yōu)、更新規(guī)則復(fù)雜、計算量大等問題，驗證表明本文提出的優(yōu)化模型和果蠅算法對于解決第二類裝配線平衡問題具有有效性和可行性。