隨機型裝配線平衡與緩沖區配置集成優化

劉雪梅， 劉 濤， 顧佳巍， 李愛平

(同濟大學 機械與能源工程學院，上海 201804)

線平衡和緩沖區配置是裝配線設計的兩個核心環節，通常先進行裝配線平衡，再進行緩沖區配置.對于操作時間不確定的裝配線平衡問題，一般通過操作時間概率分布或模糊時間的方法進行求解.在裝配線平衡方案確定后，各工位工作節拍不可能完全相同，且裝配線運行過程中會受到操作時間波動的影響，需要在工位間設置合適容量的緩沖區，以避免生產停機.由于工位時間的變化對緩沖區配置以及整線生產率產生較大影響，先平衡再緩沖區配置的串行優化模式，難以得到全局最優的結果[1]，因此，隨機裝配線平衡問題應與緩沖區配置問題集成考慮.

緩沖區配置問題BAP(buffer allocation problem)是要確定緩沖區的合理容量和適當位置，主要目的是使串行布置的各工位運行更為獨立，以減少缺料和堵料導致的空閑時間，從而提高生產率.但是緩沖區會占用生產空間，增加生產成本.BAP常見問題有：給定緩沖區總容量最大化生產率，或滿足生產率要求的前提下最少化緩沖區容量.在BAP問題中，通常各工位的生產率或操作時間已知，即生產線平衡方案已確定.工位操作時間和緩沖區配置存在復雜的交互影響，Hillier[11]針對無緩沖區裝配線提出一種倒碗式的最優工位操作分配方式，認為這種方式可以有效提高裝配線產能.與之對應，Harris[12]提出了一種倒碗式的緩沖區優化模型，在緩沖區總數一定的情況下，緩沖區最優配置的圖案也呈倒碗的形狀，但并沒有相關研究評估這兩種方式的交互作用.Boysen[13]認為工位時間的細微調整就可能引起緩沖區配置的巨變，平衡方案確定后的緩沖區優化忽略了這種影響.因此，生產線平衡和緩沖區配置順序求解方法難以得到最優生產線方案.

本文針對隨機型裝配線設計問題，集成考慮裝配線平衡和緩沖區配置優化，同時利用復雜性測度衡量工位操作時間隨機性的影響，以生產率最大，工位復雜度均衡指數、標準操作時間均衡指數和緩沖區總數量最小為優化目標，改進遺傳算法獲取集成優化方案.

1 隨機型裝配線平衡與緩沖區配置集成優化模型

1.1 問題描述

本文針對的是工位間配置有限容量緩沖區的隨機型裝配線.優化問題可描述為給定一系列作業元素，作業元素之間的優先關系已知，作業元素的操作時間不確定，各工位緩沖區容量上限已知，在節拍和作業元素優先關系約束下將作業元素分配至給定工位，并合理分配緩沖容量，實現各工位負荷均衡、生產率最大和緩沖區總容量最小.

問題相關建模參數定義如下：

K為裝配線上工位總數；k為裝配線上第k個工位，k=1,2,3,…,K；C為生產節拍；N為作業元素數；i和j為作業元素編號；O為作業元素集合，O={1,2,…,N}；ti為第i個作業元素的操作時間，i∈O；Tk為第k個工位的標準操作時間；Bk為第k個工位的緩沖區容量大小；Sk為第k個工位的作業元素集合；Y為作業元素優先關系矩陣.

1.2 基于信息熵的工位復雜性測度

大多數隨機型裝配線平衡問題主要考慮各工位標準操作時間平衡，由于操作時間隨機波動，容易導致平衡結果產生偏差，為了有效處理隨機裝配線的時間擾動，本文對工位復雜性進行測度，量化分析操作時間動態波動對裝配線平衡的影響，結合靜態時間優化目標，實現對裝配線靜、動態平衡綜合優化，保證平衡方案的有效性.目前，信息熵是研究制造系統復雜性最為重要的手段之一，本節將基于信息熵理論提出一種裝配線工位復雜性測度方法.

若存在離散隨機變量X，則X的熵定義為

(1)

式中，pi≥0.如果X表示某系統，(x1,x2,…,xn) 和(p1,p2,…,pn)分別表示該系統n個可能出現的狀態及其對應的概率，則E(X)為系統X的信息熵，是描述系統X時所需要的信息量，表征系統不確定性的大小.

裝配線中工位操作時間的偏差可達20%[6]，潘國強[14]在電機裝配線工位作業時間的統計中發現，人工工位作業時間呈近似正態分布，半自動工位作業時間呈近似三角分布，工位作業時間的最高偏差達23.3%.本文以作業元素實際操作時間的分布情況作為計算工位復雜度的狀態，通過對操作時間波動性的研究，能夠定量描述工位操作時間的不確定性，其大小取決于工位上作業元素操作時間可能出現的各個狀態及相應概率.工位熵值越大，工位狀態的不確定性和不可預測性越大，工位情況越復雜.

作業元素i的標準操作時間為ti0，經統計得到若干實際操作時間樣本，將其與標準操作時間進行對比，分作以下m個區間(s1,s2,…,sm)，分別表示m種狀態：操作時間為ti1～ti2,ti2～ti3,…,tim～tim+1；時間分段間隔為ε，間隔大小即劃分粗細程度.根據具體實例，ti0與ti最小值之差為Δia，若ti0前分為m1個區間，則

(2)

ti最大值與ti0之差為Δib，ti0后分為m2個區間，則

m2=maxΔ1bε,…,Δibε,…,Δnbε

(3)

作業元素i操作時間所分成的m個區間分別為：ti0-m1ε～ti0-(m1-1)ε,…,ti0-ε～ti0,ti0～ti0+ε,ti0-(m2-1)ε～ti0-m2ε.

統計得到作業元素i的操作時間出現在這m個區間的概率分別為(pi1,pi2,…,pim)，第k工位作業元素數為nk，作業元素i的操作時間所處狀態為ji，作業元素i出現ji狀態的概率為piji.該工位上的操作依次進行，工位出現某一種狀態的概率為p1j1p2j2…pnkjnk，所有狀態出現的概率之和為1，即

(4)

根據信息熵理論，該工位所含平均信息量，即工位復雜度為

(5)

式中:Hk為第k工位復雜度.

1.3 優化模型的建立

1.3.1目標函數

工位復雜度為工位操作時間的不確定性給出了量化指標，如前所述，工位復雜度越高，則工位操作時間可能出現的狀態越多，隨機性越大.如果工位間復雜性差異過大，則會造成有些工位時常出現空閑和超載嚴重，甚至引起阻塞.同時，操作時間超過節拍要求，工人更容易出現操作失誤，對生產進一步造成延誤.因此，平衡規劃階段需要考慮工位復雜性，減少各工位間復雜性的差異，使各工位操作時間不確定性趨于均衡，以提高平衡的有效性.工位復雜性差異度目標函數為

(6)

式中：G為工位復雜度均衡指數；Hmax為各工位復雜度的最大值.

除了新引入的工位復雜性差異度這一動態平衡目標外，區別于傳統基于工位標準操作時間均衡進行作業元素平衡分配的方法，本文考慮工位操作時間與緩沖區容量配置的交互影響，利用軟件仿真獲取裝配線生產率，將生產率R、工位標準操作時間均衡指數M和緩沖區總容量B作為目標函數，以保證裝配線性能.

其中工位標準操作時間均衡指數M定義如下：

(7)

式中:Tmax為工位標準操作時間的最大值.

緩沖區總容量B定義如下：

(8)

1.3.2整線生產率獲取方法

生產率R作為優化目標之一，針對每一次生成的平衡分配與緩沖區配置方案，均需要準確評價，通過Matlab調用Plant Simulation軟件仿真來得到準確的生產率，仿真流程如圖1所示.

圖1 調用Plant Simulation軟件仿真過程

Plant Simulation是一款離散事件系統仿真軟件，利用其面向對象建模的編程方法可以快速地實現系統建模，但是軟件內無法實現多個生產線方案的自動建模比較.本文利用Plant Simulation軟件的COM組件接口，在MATLAB中生成COM服務器并且訪問COM組件，將作業元素分配和緩沖區配置的集成方案輸入到Plant Simulation中，調用軟件中的method建立仿真模型，之后執行仿真，在仿真結束時傳回方案的相關數據，為生產線方案提供準確的生產率R的數值.

通過COM組件，MATLAB可以自動執行規劃方案的仿真，而不需要人為搭建模型，執行仿真操作，同時可以和優化算法相集成，利用仿真精度高的優勢來綜合評估線平衡與緩沖區配置對裝配線帶來的交互影響從而支持優化算法的尋優過程.

1.3.3優化模型

綜合上述內容，將作業元素集O={1,2,…,N}分配到K個工位上{Sk/k=1,2,…,K}, 并設置各個工位后緩沖區容量大小，集成優化的優化目標如下：

(9)

約束條件為

(10)

Sk1∩Sk2=?(k1≠k2;k1,k2=1,2,…,K)

(11)

Tk

(12)

Bk

(13)

Y=(yij)N×N(i,j=1,2,…,N)

(14)

約束(10)表示每個作業元素都要被分配至工位；約束(11)表示每個作業元素只能被分配一次；約束(12)表示工位的操作時間必須小于裝配線預設工作節拍；約束(13)表示工位的緩沖區大小必須小于裝配線預設緩沖區容量上限，且最后一個工位不設置緩沖區；約束(14)表示N個作業元素的N×N優先矩陣,其中矩陣元素yij取決于作業元素i與作業元素j的先后關系.如果作業元素i是作業元素j的優先作業元素，則yij=1,否則yij=0.

2 算法設計

裝配線平衡和緩沖區配置集成優化是典型的組合優化問題，隨著問題規模的增加，搜索空間急劇擴大.遺傳算法是最常用的解決組合優化問題的一種啟發式算法，可以有效求解線平衡[15]和緩沖配置[16]等問題，但是遺傳算法無法“記憶”較優的解，易導致求解速度慢或者出現早熟現象，本文針對所提出的集成優化模型，設計了一種改進的遺傳算法來進行求解.

2.1 染色體編碼方式

染色體編碼采用結構體編碼的直接編碼方式，編碼包括作業元素排序和緩沖區配置方案兩個部分.其中，作業元素排序對所有需要分配的作業元素根據作業元素優先關系矩陣進行實數編碼排序，緩沖區配置方案對應緩沖容量大小，編碼長度為需要設置緩沖區的工位個數.編碼結構如圖2所示.

圖2 染色體結構

2.2 染色體解碼方式

為了得到包含作業元素排序與工位分配、緩沖區配置的完整設計方案，按順序對染色體編碼進行解碼.首先解碼得到作業元素排序，根據單個工位節拍上限按順序將作業元素分配到各工位.然后結合裝配線工位總數，解碼緩沖區配置容量，得到緩沖區配置方案，從而得到裝配線配置方案.

2.3 改進的遺傳算法流程

針對所提出的集成優化模型，為避免最優方案丟失和出現早熟現象，設計了一種改進的遺傳算法來進行求解，采用精英保留策略對最優解進行復制保留和變異處理，保證算法收斂性.求解分為3個階段：

(1)根據工位數和節拍上限，生成作業元素分配方案，同時配置各緩沖區容量；

(2)通過仿真得到整線生產率，同時計算得到工位標準操作時間均衡指數和整線工位復雜度均衡指數；

(3)計算適應度值，通過圖3所示改進的遺傳算法流程循環保留最優方案.

改進的遺傳算法流程如下：

(1)根據個體適應度值對種群中存在的個體進行排序；

(2)保留最優解并對其進行復制，保留解染色體不變，復制解對染色體緩沖區配置部分進行鄰值變異；

(3)非保留解進行交叉變異.

(4)對新生成的染色體種群進行作業元素分配，判斷新生成的方案是否滿足工位數約束，若滿足，則通過仿真計算得到適應度值；若不滿足，進行懲罰使適應度值為0；

(5)當前種群個體按照適應度值排序；

(6)終止條件為限定的遺傳進化代數或末位50代適應度值標準差低于設定值，判斷是否滿足算法收斂條件，若滿足，根據個體適應度選擇最優方案；若不滿足，重復步驟(2)～步驟(6).

圖3 改進的遺傳算法過程

2.4 算法實現

2.4.1設定工位節拍上限

根據作業元素總的操作時間、工位數量等基本信息，估算出工位節拍時間上限，作為初始種群作業元素分配的工位操作時間約束.

2.4.2產生初始種群

根據作業元素優先關系矩陣挑選最前序作業元素生成優先級最高的作業元素集，并隨機選擇一個元素放入染色體，刪掉已分配元素；然后，剩余元素中生成優先級最高的作業元素集，隨機選擇一個元素按序置入染色體，如此反復直至所有元素分配完成即生成一條染色體作業元素排序部分；緩沖區配置部分依次在緩沖區容量的上限值內進行隨機取值；重復種群生成操作循環生成種群規模為z的初始種群.

2.4.3交叉變異算子

(1)交叉算子

選取兩條染色體父代1、父代2，對作業元素排序部分進行交叉操作.交叉算子采用兩點交叉法，設交叉概率為Pc，隨機產生兩個交叉點，得到父代1兩交叉點間的基因段，如圖4所示.在父代2中搜索該基因段的排列方式，將父代1基因段替換成新的排序方式獲得子代1，同樣的交叉過程獲得子代2，如圖5所示.由于交叉算子不破壞作業元素之間的先后順序約束，所以生成的兩個新作業序列是可行的.

對于緩沖區容量而言，由于不同工位間的緩沖區容量設置差異較大，不符合緩沖區容量變化的基本邏輯，因此對緩沖區配置編碼不進行交叉操作.

圖4 兩點交叉算子隨機選點

圖5 交叉后子代編碼順序

(2)變異算子

設變異概率為Pm，選擇一條染色體為父代，隨機產生變異點，根據優先關系矩陣，對變異點后面的作業排序基因段進行重新排列，獲得新的子代染色體，如圖6所示.

圖6 單點變異算子隨機選點

對于緩沖區容量而言，單個緩沖區容量的最優結果往往在個位數的變化范圍內產生，因此對緩沖區配置編碼進行鄰值變異操作，對每一個緩沖區的容量配置進行上下小區間的鄰值變異操作.

2.4.4適應度評價

本文隨機型裝配線平衡與緩沖區配置集成優化的目標是：最大化裝配線生產率，最小化工位復雜度均衡指數、標準操作時間均衡指數和工位間緩沖區配置總量.其中生產率和緩沖區容量設置直接影響到裝配線生產效益和成本，工位復雜度均衡指數和工位標準操作時間均衡指數則直接反應工位負荷情況.

裝配線的經濟性評價指標P與單位時間裝配線的產值和單位時間緩沖區總成本等有關，其中單位時間裝配線的產值由生產率R與單個產品產值p求得；單位時間緩沖區總成本則通過單位容量緩沖區單位時間成本c與緩沖容量總數B求得

P=pR-cB

(15)

化簡可得有效生產率P*，即

(16)

式中，生產率R通過軟件仿真得到，cp-1即單個產品緩沖成本率，根據裝配線實例可得其具體數值，記為c*.從工位生產負荷出發，工位負荷的大小和均衡與否會影響到裝配線的實際生產過程，進而影響整線的經濟性指標.

綜上，適應度函數f(R,B,G,M)設計為

(17)

在染色體解碼過程中，合理分配意味著不出現最后一個工位上沒有作業或作業分配不完的情況.如果出現不合格的染色體，對其將進行懲罰，令適應度值為0.

2.4.5保留復制策略

為了盡可能將優秀個體保留到下一代種群中，本文采用精英保留復制策略，精英選擇概率為PS，即選取這一代中a(a=zPS)個最優的個體直接進入下一代.同時對這a個最優個體進行染色體的復制，并對其進行緩沖區的鄰值變異后進入下一代.

3 實例驗證

以某汽車企業變速箱裝配線分裝線為例對本文算法進行應用驗證.該變速箱分裝線共有38個作業元素，遵循的優先關系如圖7所示.作業元素用數字進行標識，每一個連接線前后分別為緊前作業元素和緊后作業元素.

該變速箱分裝線共計8個串行工位，單個工位能夠配置的最大緩沖區容量為5，生產線節拍上限C估算為65 s，各作業元素的標準操作時間和波動時間數據均已知.所有作業元素只存在前后順序約束，并行作業元素無前后限制，單個產品緩沖成本率c*為0.043.

將作業元素i操作時間低于標準操作時間的部分分成3個區間，由于序號為24的作業元素標準操作時間與操作時間最小值之差最大為3 s.則作業元素i被分為4種狀態：ti0-3 s～ti0-2 s,ti0-2 s～ti0-1 s,ti0-1 s～ti0,ti0～ti0+1 s，對應的概率分別為 (pi1,pi2,pi3,pi4)，經過區間劃分，各作業元素標準時間和出現在4個區間的概率如表1所示.

圖7 作業元素優先關系

表1 作業元素標準操作時間及其區間概率

Tab. 1 Standard operation time and its interval probability

iti0pi1pi2pi3pi4iti0pi1pi2pi3pi4iti0pi1pi2pi3pi411400.230.730.04141600.230.730.04271500.230.730.0421100.200.780.02151400.080.860.06281600.200.780.023230.070.100.600.0316900.100.880.0229900.100.840.06411000.980.02171300.200.780.02301200.200.780.0251300.080.860.06181200.080.860.063110000.940.0661100.200.780.02191100.10.880.0232220.070.400.500.0379000.940.0620310.250.400.320.03331300.200.780.028900.230.730.04211400.230.730.0434700.100.840.0691400.200.780.0222900.10.840.06351100.100.840.061011000.940.0623800.100.90036800.230.730.04111000.200.780.0224290.250.300.420.0337900.200.780.02121000.200.780.02251100.100.840.06381500.200.780.0213800.10.880.02261000.080.860.06

3.1 求解作業元素分配和緩沖區配置方案

在MATLAB2010b中編制求解程序，遺傳算法參數設定為：種群規模z=200，精英選擇概率Ps=0.2，交叉率Pc=0.3，變異率Pm=0.5，遺傳迭代次數N=300，算法迭代收斂過程如圖8所示，得到最優作業元素分配和緩沖區配置方案1如表2所示.優化后節拍C1=63 s，利用仿真和式(6)～式(8)得到裝配線分裝線生產率為R1=46.964 3 h-1，復雜度均衡指數G1=2.224 9，工位標準操作時間均衡指數M1=6.782 3，緩沖區總容量為20.

圖8 算法迭代收斂曲線

表2 作業元素分配與緩沖區容量配置方案1

Tab. 2 Operation assignment & buffer configuration 1

工位工位作業元素標準操作時間復雜度緩沖區容量1[1,3,2,4]594.911 012[10,5,6,11,14]615.374 153[7,13,8,9,16,18]615.223 014[12,15,17,19,21]625.269 135[20,22,23,25]593.629 656[24,26,27,29]634.846 537[28,35,30,32]614.921 028[33,31,34,36,38,37]625.522 3/

3.2 考慮工位復雜度均衡與否的方案對比分析

對于隨機型裝配線平衡問題，常用的解決辦法是假設操作時間服從正態分布，在裝配線工位滿足一定完工率的條件下，使平衡率最高、工位平均操作時間均衡[5].為了說明本文方法的有效性，利用隨機數發生器產生的隨機操作時間，對所得方案1進行仿真，仿真得到裝配線完工率為0.94.將實例中的作業元素操作時間擬合成正態分布，利用文獻[5]中的方法，以平衡率最高、工位平均操作時間均衡為目標，對模型進行求解，得到最優作業元素分配與緩沖區配置方案2.計算方案2的工位標準操作時間和復雜度，如表3所示.

該方案中，節拍C2=63 s，整線生產率R2=45.285 4 h-1，復雜度均衡指數g2=2.991 9，工位標準操作時間均衡指數m2=7.348 5，緩沖區總容量為24.方案1和方案2各工位標準操作時間分布對比如圖9所示，各工位復雜度分布對比如圖10所示.方案2與方案1相比，工位2、3、4的標準操作時間差異較大，與之對應，工位2、3、4的復雜度也不如方案1平穩，即整個分裝線的2、3、4工位的操作時間不確定性更高，波動程度更大.考慮工位復雜度進行裝配線平衡，各工位復雜性均衡程度明顯提升，所得方案1比方案2提高25.64%.工位復雜度均衡表明各工位操作時間不確定性較為均衡，超載和空閑時間相差不大，減少不確定因素對裝配線的影響，使裝配過程更加平穩.與此同時，裝配線生產率保持R1=46.964 3 h-1，工位標準操作時間均衡程度同樣達到了較高水平，比方案2進一步改善了7.70%.同時，緩沖區配置的總量從24下降到20，優化率達到16.67%，因此，方案1在工位復雜度均衡、緩沖區總數量等方面均有較大優勢.

表3 作業元素分配與緩沖區容量配置方案2

圖9 各工位標準操作時間分布對比

圖10 各工位復雜度分布對比

由此可見，兩種優化方法得到的平衡方案整線生產率水平接近，標準操作時間均衡程度相差相對較小，整線工位復雜性均衡程度明顯提升，相比方案2，方案1的優化效果如表4所示.

表4 方案1優化效果

3.3 集成優化與串行優化對比分析

為了驗證集成優化方法的有效性，將集成優化與串行優化方法進行對比.在串行優化中，線平衡問題和緩沖區配置問題被拆分成兩個問題，傳統的線平衡問題首先以平衡率為目標進行線平衡優化，然后在線平衡的最優結果上再進行緩沖區的配置優化.使用所提的改進遺傳算法，參數設置與集成優化相同，對目標函數進行適當修改，取消緩沖區配置部分，優化結果如表5所示，平衡率結果為96.83%.

表5 串行優化作業元素分配方案

在線平衡的最優方案基礎上，再進行緩沖區配置的優化，以生產率最大為優化目標，仍采用之前提到的改進的遺傳算法，用仿真方法得到方案的生產率值，算法參數設置與線平衡時相同，緩沖區容量優化結果為3-2-3-5-5-5-2，緩沖區總容量為25，生產率最大為46.639 1 h-1.集成優化和串行優化方案的對比如表6所示.

表6 集成優化和串行優化方案對比

由表6可知，相比串行優化，集成優化不僅可以達到同樣的平衡率效果，且在進行線平衡優化的同時就考慮了整線工位復雜性和工位標準操作時間均衡等影響，最終的方案在保持較高的生產率水平的同時，在緩沖區配置的總數量方面有著較大的優勢.集成優化可以一次同時得到包括工位操作分配和緩沖區配置的完整設計方案，且避免了串行優化可能因為早熟現象而得不到全局最優解的問題，因此集成優化比串行優化在計算效率和優化結果上均占有較大優勢.

4 結語

針對隨機裝配線規劃過程中線平衡和緩沖區配置優化問題，引入裝配線工位復雜度均衡目標，并結合工位時間平衡、整線緩沖區總量最小和生產率最大化目標，構建了線平衡和緩沖區配置集成優化模型.通過軟件仿真得到設計方案的準確生產率，采用改進的遺傳算法進行優化方案求解.實例表明該方法可以在一次優化過程中得到線平衡和緩沖區配置的整體方案，在保持較高的平衡率、生產率的同時，工位復雜性更均衡，緩沖區總容量更小.

在進一步的研究工作中，將考慮裝配線專機性能對裝配作業元素可分配性的影響，增加操作分配時對專機屬性的考慮，另外也將考慮設備布局和物流等的影響，從而擴大算法的適用性，獲取更符合實際的優化方案.