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

杜利珍 王運發 王 震 余聯慶 李新宇

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

0 引言

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

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

1 問題描述和數學模型

1.1 問題描述

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

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

1.2 數學模型

在追求第二類裝配線平衡時，需要將所有工序分配到各工作站中，最終使生產節拍T達到最小，并保證整個生產線中的不同工作站的加權平均負荷能夠達到均衡，即不同工位的平均單件作業時間的標準方差最小。

依據上述分析，得到本次研究問題的目標函數。

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

minZ1=T

(1)

(2)為了平衡裝配線上各工作站的工作負荷，將負載標準差最小化設置為第二個優化目標，即有

(2)

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

因此，本文研究的第二類裝配線平衡問題的優化目標由生產節拍最小化和負載標準差最小化共同組成，W1、W2分別代表這兩個優化目標的權重，從而將多目標優化問題轉化為單目標問題。因此，建立總目標函數為

minZ=W1Z1+W2Z2

(3)

對上述問題進行研究時，作如下假設[8]：①作業i的加工時間都是穩定的；②所有的作業都被分配到工作站k中去；③一個作業只能夠分配到一個工作站；④裝配線不能夠實現并行處理。上述條件轉化成為的表達式為

(4)

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

(5)

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

(6)

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

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

2 算法設計

2.1 基本原理及步驟

果蠅算法[9]是根據果蠅群體依據空氣中的氣味分子實現覓食過程開發的，算法流程如下：

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

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

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

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

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

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

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

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

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

2.2 編碼與解碼

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

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

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

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

2.3 作業分配方案的生成

上述算法運行后能生成拓撲排序，但一個SP有很多個分配方案，因此在進行作業分配之前還需對方案進行分析、選擇，利用最佳方案對作業進行分配。本次設計中使用的是KIM等[11]研發的方法，通過該方法對作業進行分配，經過不斷的迭代，使所有的作業都能均勻地分配到工作站中，算法流程[12]如下：

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

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

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

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

3 標桿案例

3.1 雙產品裝配時間測定

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

3.2 雙產品優先關系圖

A、B產品作業優先關系如圖2所示。

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

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

圖2 某公司A、B產品裝配線作業優先關系圖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

因此可知，標桿案例中裝配線的生產節拍為327 s，根據生產線平衡率計算公式可計算出裝配線平衡率：

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

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

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

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

(3)編碼及模型求解。本文采用基于權重編碼方式，對A、B產品利用優先權重編碼的過程進行分析，隨機初始化作業單元的優先權重為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)。

根據果蠅算法的求解步驟，用MATLAB進行仿真求解，算法對相關參數設置如下：最大迭代次數130，種群規模100。求解得到的最優果蠅個體為(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

采用果蠅算法對工作站分配模型進行求解，其工作站作業內容如表3所示，目標函數值324 s，即優化后的生產節拍T=324 s，裝配線各工作站內作業元素如表3所示。由表3可以計算出優化后裝配線平衡率α為97.68%。

表3 果蠅算法優化后各工作站劃分情況

標桿案例采用自適應遺傳算法和本文采用果蠅算法求解的優化結果，如表4所示。

表4 GA與FOA求解結果對比表

由表4可知，本文采用果蠅算法的優化結果與標桿案例的優化結果相比，生產節拍縮短了3 s，裝配線平衡率提升了0.9%，負載標準差降低了2.32 s。利用果蠅算法求解的工站工時趨于平穩。

4 結語

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