彭運芳，梁玉珍，夏蓓鑫

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

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

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

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

1 模型建立

1.1 問題描述

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

圖1 工序優(yōu)先順序圖Fig.1 Precedence of tasks

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

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

1.2 數(shù)學模型

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

表1 參數(shù)設置Table 1 Parameter settings

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

2 改進型遺傳算法的設計

2.1 初始種群的產(chǎn)生

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

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

2.2 解碼操作

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

圖4 解碼過程Fig.4 Decoding procedure

2.3 適應度

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

2.4 選擇操作

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

2.5 交叉與變異操作

2.5.1 交叉操作

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

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

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

2.5.2 變異操作

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

圖6 變異操作Fig.6 Mutation operation

2.5.3 算子設計

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

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

2.6 終止條件

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

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

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

3 實例驗證

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

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

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

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

表3 產(chǎn)品各型號作業(yè)時間Table 3 Operating time of each model of the products s

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

4 結束語

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