基于改進型遺傳算法的混流U 型裝配線第二類平衡問題

彭運芳，梁玉珍，夏蓓鑫

(上海大學管理學院，上海 200444)

近年來，裝配線平衡問題(assembly line balance problem，ALBP)已成為制約先進工業生產的因素，關系著產品能否按時交貨、生產節拍與工作站以及作業工序分配. 隨著全球化經濟的發展，客戶的需求愈發多元化. 多品種、小批量的客戶需求逐漸被廣大制造商所重視，傳統的單一品種裝配線已經無法滿足實際需求，混流裝配線應運而生. 混流U 型裝配線的設計布局不僅使作業工序有了更多結合的可能性，而且也大大增加了裝配線設計的柔性. 一般可以將裝配線平衡問題分為兩類: 第一類是已知生產節拍，求最小工作站數; 第二類是已知工作站數，求最小生產節拍.

第一類平衡問題通常在需求易于預測的新裝配線設計中予以考慮[1]. 不同線型的第一類裝配線平衡問題已得到了廣泛而深入的研究[2-4]. 第二類平衡問題被廣泛應用在已投產裝配線的再配置過程中，其應用范圍較之第一類問題更廣，但相應的研究卻明顯單薄. 尤其是第二類U 型裝配線平衡問題是許多準時化生產企業面臨的一個難點[5]. 針對單一品種的直線型裝配線，Roshani等[6]在求解第二類裝配線平衡問題時提出了基于模擬退火算法的兩種元啟發式算法. Moreira等[7]考慮了工人的差異性將工人進行適當的分配，使用啟發式算法解決了第二類平衡問題. 而針對單一品種的U 型裝配線，Oksuz等[8]在求解第二類平衡問題時，建立了非線性數學模型并線性化處理，使用CPLEX 軟件求解了中小規模問題，使用元啟發式算法解決了大規模問題. Ogan等[9]建立了混合整數規劃模型，使用分支定界法求解了中小規模下的第二類平衡問題. 在混流裝配線平衡處理方法上，Han等[10]通過矩陣圖將多品種作業順序圖等效生成一張綜合作業圖，從而把多品種裝配線平衡問題轉化為單一品種裝配線平衡問題. 目前對裝配線平衡問題的研究主要集中在單一品種直線型以及第一類U 型裝配線，而對第二類U 型混流裝配線平衡問題的研究較少. 之所以出現這種現象，是因為裝配線平衡本身是一個NP 難問題，而產品混流與U 型裝配線的工序分配方式進一步增加了問題的難度，第二類裝配線平衡問題相比第一類問題更難解決[5].

本工作針對第二類混流U 型裝配線平衡問題，在自適應遺傳算法的基礎上，結合混流U 型裝配線中工序分配到工作站的3 種方式，在解碼過程中使用3 種搜索方式把工序分配到工作站，并參照期望生產節拍值篩選結果. 同時，根據裝配線的平衡效果判定是否自動更新期望生產節拍值. 如果當前搜索不到結果，就在可接受的范圍內，按照工序作業時間精度值更新期望生產節拍值. 最后用標準測試數據來檢驗本算法設計的有效性. 通過比較CPLEX、標準測試及改進型遺傳算法的3 種運行結果，證明了本改進型遺傳算法設計的有效性.

1 模型建立

1.1 問題描述

圖1 為某產品的作業工序優先順序圖，其中圓圈內的數字表示工序，箭頭表示兩個工序之間的作業先后關系. 常見的U 型裝配線布局如圖2 所示. 以圖1 的7 個工序分配到4 個工作站為例進行說明: 矩形框內表示一個工作站，同一工作站的兩端可以有一個或者兩個小作業站甚至更多，產品依次進入裝配線中進行加工. 混流U 型裝配線是在同一個裝配線上生產M種類型的產品，每種類型產品的工藝要求不盡相同，使得不同產品的作業元素存在一定的差異. 在研究M種產品的混流裝配線平衡時，由各種類型產品對應的工序時間和作業優先順序圖，以及各產品的需求比率生成一張綜合作業優先順序圖.

圖1 工序優先順序圖Fig.1 Precedence of tasks

圖2 U 型裝配線布局Fig.2 Layout of the U-shaped assembly line

在工作站數一定的條件下，最小化混流U 型裝配線的生產節拍是本工作要解決的主要問題. 為了規范問題的求解過程，需進行以下假設: ①每個工序必須分配到具體工作站; ②所有的作業工序都必須被分配; ③生產節拍不小于任意工作站時間; ④一個工作站分配一位操作工; ⑤每種模型產品的工序作業時間已知; ⑥作業工序優先順序已知; ⑦產品順時針進入U型裝配線.

1.2 數學模型

根據問題描述部分以及裝配線平衡需要滿足的約束條件設定相關參數和決策變量，如表1 所示.

表1 參數設置Table 1 Parameter settings

不同型號產品的工序作業時間可能不同，根據各種型號產品的需求比率生成綜合作業圖[1]. 約束條件(1)表示目標函數，最小化生產節拍; 約束(2)表示所有的工序都要被分配;式(3)限定了工作站總作業時間不大于生產節拍; 式(4)表示具有緊前后關系的工序按照從前向后的方式進行工序分配時，要滿足優先順序關系; 式(5)表示按照從后向前的方式進行工序分配時，也要滿足優先順序關系; 約束條件(6)表示綜合作業圖中工序i的作業時間是根據產品的需求比例得來; 式(7)與(8)表示了變量xij，yij的取值范圍.

2 改進型遺傳算法的設計

2.1 初始種群的產生

本工作采用實數編碼方式，參照文獻[11]中初始染色體的生成方法，將所有具有緊前后關系的工序生成滿足工序優先順序的染色體序列. 染色體上的基因位代表著作業工序，圖3 為圖1 中某產品的工序優先順序圖對應的一種染色體序列.

圖3 基因編碼順序圖Fig.3 Encoding procedure

2.2 解碼操作

解碼是將工序分配到工作站的重要操作，也是本遺傳算法規則設計的創新之處. 每次以期望值Cycletime 為上界值，比較3 種搜索分配方式的優劣并篩選出最優工序分配結果. 具體操作如下: 首先將工作站平均生產節拍賦值給Cycletime 進行第一次搜索，如果尋找到的目標函數值Ct≤Cycletime 則終止尋找，否則更新期望值，也即以工序作業時間精度值依次累加到Cycletime 繼續尋找. 在滿足工作站時間小于等于Cycletime 的情況下，對未分配的工序采用以下3 種分配方式(以圖3 為例): ①按照從前向后的搜索方式將工序分配到工作站(從工序1 開始，依次將工序分配到工作站中); ②按照從后向前的搜索方式將工序分配到工作站(從工序7 開始，依次將工序分配到工作站中); ③按照從前向后與從后向前的搜索方式同時進行分配(從前向后從工序1 開始，從后向前從工序7 開始，依次將工序分配到工作站中; 否則，在從前向后分配的工序中按照工序優先序列關系依次加入下一工序，并重復上述搜索方式). 解碼流程如圖4 所示.

圖4 解碼過程Fig.4 Decoding procedure

2.3 適應度

適應度是通過對染色體的優劣進行衡量，以此來判斷求解結果是否達到要求. 本工作是在工作站數量已知的情況下將最小化生產節拍作為目標函數，并將目標函數(9)作為適應度，即

2.4 選擇操作

輪盤賭選擇又稱為比例選擇算子，其基本思想是各個體被選中的概率與其適應度函數值大小成正比. 設群體大小為N，個體xi的適應度為f(xi)，則個體xi被選中的概率為P(xi)，即

2.5 交叉與變異操作

2.5.1 交叉操作

在交叉過程中要滿足作業工序的順序優先級關系. 采用兩點交叉操作法，首先在染色體的基因位上隨機選擇兩點，被選中進行交叉的父代一染色體與父代二染色體根據對方在兩點之間的相對位置進行交叉產生子代一和子代二，具體的操作過程如圖5 所示.

圖5 兩點交叉法Fig.5 Two point crossover method

由圖5 可見，在兩點交叉操作過程中，首先在染色體片段上隨機選擇兩點(如箭頭所示)，父代一在兩點間的片段2，5，4 要根據父代二中的相對位置進行重新排序. 可以看出，父代一兩點間的基因片段在父代二中的相對位置順序為2，4，5，所以產生的子代一在該兩點間的基因序列為2，4，5，兩點之外的序列不變. 子代二的產生同理.

2.5.2 變異操作

變異操作也要滿足作業工序的順序優先級關系，操作過程如圖6 所示. 可見，在變異操作中，隨機選擇染色體中的某一基因(工序)，根據作業工序順序優先關系圖分別找出該工序的緊前序與緊后序所在位置，然后隨機插入該工序.

圖6 變異操作Fig.6 Mutation operation

2.5.3 算子設計

交叉率(pc)與變異率(pm)的大小直接影響求解結果的質量. 為了避免搜索陷入局部較優解，本工作采用了自適應遺傳算法，根據適應度大小來自動調節交叉變異率: 適應度高的個體結構以較小的概率發生改變，適應度低的個體結構則以較大的概率發生變化.

式中:fmax為種群中最大的適應度值;favg為平均適應度值;f′為要交叉的兩條染色體中較大的適應度值. 因為本工作中的目標函數是最小化形式，所以要根據約束條件(13)進一步轉化. 當favg逐漸趨向于fmax時，pc與pm變為0，優良的個體被保留，其中k1=k2= 1，k3=k4=0.5，使得低于或等于平均適應度值的個體都要被淘汰，利用種群中低于平均適應度值的個體進一步搜索全局最優解.

2.6 終止條件

遺傳算法的終止條件為目標函數值Ct滿足約束條件(14)，或者迭代次數達到最大限制，即

綜上所述，本改進算法的思想如圖7 所示，其中重點改進在于運用了本工作提出的解碼操作計算染色體的適應度.

圖7 改進遺傳算法流程圖Fig.7 Flow chart of the improved genetic algorithm procedures

3 實例驗證

用Visual Studio 2015 運行上述算法程序，采用網址https://assembly-line-balancing.de/中的直線型標準數據進行測試與比較. 表2 為不同規模下采用CPLEX、標準數據及本工作提出的改進型遺傳算法3 種方法求得的最優解，其中n表示工序數;k表示工作站數;Ct表示求得的生產節拍值;TW表示工作站總空閑時間;η表示裝配線平衡效率.

表2 求解結果對比Table 2 Comparisons of the solution results

由表2 可見: 本工作提出的改進型遺傳算法得到的解相比標準數據質量更優，驗證了U 型裝配線比直線型裝配線的平衡效果好; 同時絕大多數改進型遺傳算法求解得到的生產節拍值與CPLEX 精確求解得到的最優值相等，驗證了改進型遺傳算法在規則設計時的有效性; 從裝配線的平衡效率來看，CPLEX 在能求出解的情況下，求解效率均達到最大值; 改進型遺傳算法得出的U 型裝配線平衡效率大多高于直線型裝配線; 從運行時間上看，隨著規模的增大，改進型遺傳算法比CPLEX 所需運行時間明顯減少. 同時也發現，當規模變大時，比如58 個工序分配到19 個工作站時，CPLEX 已經無法在一定的時間內運行出結果.

通過比較標準測試數據，驗證了本改進型遺傳算法的有效性. 將本算法應用到汽車裝配線[11]中，以驗證其實用性. 由于文獻[11]與本工作考慮的因素不同，故在原數據的基礎上進行了修改，考慮了兩種不同型號的產品. 表3 為產品型號1 的作業時間(operating time of type-1，OT-1)與型號2 的作業時間(operating time of type-2，OT-2)的對比. 同時，還采用兩種方法解決了該裝配線的平衡問題: 方法一，在CPLEX 軟件中建立混合整數規劃進行精確求解; 方法二，使用本改進型遺傳算法進行求解，結果如表4 所示. 可見兩種方法求得的工序分配結果雖有所不同，但都找到了相同的目標值34.05.

表3 產品各型號作業時間Table 3 Operating time of each model of the products s

表4 裝配線平衡結果Table 4 Results of the assembly line balance

4 結束語

混流U 型裝配線平衡對多品種生產制造企業尤為重要，合適的工序分配能夠大大提高企業生產效率. 本工作基于U 型裝配線工序分配的特點，在遺傳算法規則設計方面進行創新，采用3 種搜索方式分配工序，并參照期望生產節拍值大小篩選出最優的分配方案. 同時，根據算法尋優情況是否達到要求來判斷是否更新期望生產節拍值，并通過大量的實驗驗證了該算法規則設計的有效性和可行性，為第二類U 型裝配線的平衡提供了一種高效可行的算法規則設計建議.