考慮工時不確定性的混流U 型裝配線平衡的分布魯棒優化方法

周劍揚， 張凌波

（華東理工大學信息科學與工程學院, 上海 200237）

多品種、小批量的產品需求模式使得混流U 型裝配線為越來越多的制造型企業所采用。相較于直線單模裝配線，混流U 型裝配線具有可以同時生產多種類型的產品和工序分配更靈活等優點。因此，混流U 型裝配線平衡問題（Mixed-Model U-Shaped Assembly Line Balancing Problem，MMUALBP）成為近幾年的研究熱點。目前已有許多研究人員針對理想情況下的MMUALBP 進行了研究[1-3]，但在真實的生產環境中，受工人熟練度等因素影響，裝配時間并非固定值，為了抵消不確定工時帶來的影響，提高裝配線的魯棒性就極其重要。

解決工時不確定裝配線平衡問題的方法有隨機優化（Stochastic Optimization，SO）、魯棒優化（Robust Optimization，RO）和模糊規劃等[4-10]。在工時的概率分布信息已知的基礎上，SO 通過機會約束理論構建模型。文獻[4]假設工時服從某個已知的正態分布，設定完工概率為α，建立了混合整數規劃模型；文獻[5]采用機會約束規劃建立工時不確定情況下的Ⅱ類裝配線平衡模型；唐秋華等[6]針對隨機工時的裝配線平衡問題，考慮物流運輸約束條件，建立機會約束規劃模型并轉換為混合整數規劃模型。RO 適用于工時部分已知的情況，通過集合的形式描述工時的不確定性。Hazir 等[7]針對時間的不確定性，建立基數不確定集合，構建了兩種魯棒優化模型，并提出一種基于分解的算法求解；Zhang 等[8]建立了時間不確定的Ⅱ類混流裝配線平衡魯棒優化模型，根據對偶原理將其轉換為對等模型。模糊規劃適用于存在模糊參數的最優化問題，其關鍵在于選擇合適的隸屬度函數。Mirzaei 等[9]采用梯形模糊數描述工時的不確定性，提出一種基于信念度的模糊模型；Babazadeh等[10]采用三角模糊數描述工時的不確定性并構建直型和U 型裝配線模糊模型。

在上述文獻中，SO 和RO 是兩種常用的解決工時不確定條件下裝配線平衡問題的方法，但卻存在一定的不足。SO 需要知道完整的工時概率分布信息，在實際情況中很難實現；RO 不需要完整概率分布信息，在最壞情況下求解，結果通常較為保守。分布魯棒優化[11-13]（Distributionally Robust Optimization，DRO）綜合了SO 和RO 的優點，又在一定程度上解決了兩者的不足，無需知道不確定參數確切的概率分布信息，同時又不忽略樣本數據，通過構建不確定參數的模糊集，尋找極端概率分布下的最優決策。

本文考慮工時的不確定性，基于Wasserstein 距離[14-15]，建立工時不確定性模糊集，進一步建立MMUALBP DRO 模型，并根據對偶理論對原模型進行轉化。針對提出的模型，設計了一種改進遺傳算法（Improved Genetic Algorithm，IGA），提出一種基于區間數的解碼方案，并引入自適應概率。最后通過數值仿真實驗驗證了所建立的DRO 模型可以更好地平衡效率和保守性，并進一步驗證了IGA 在求解本文DRO 模型具有更好的精度。

1 基于Wasserstein 模糊集的分布魯棒優化方法

1.1 分布魯棒優化

DRO 最早由Scarf[16]在1958 年提出，其目標函數可以表示為：

1.2 基于Wasserstein 距離的模糊集

建盡可能小且包含真實分布的模糊集。本文采用Wasserstein 距離衡量經驗分布和真實分布之間的差異，相較于其他度量，Wasserstein距離有著更好的性質[17]，定義如下：

1.3 數據驅動支撐集

2 工時不確定的混流U 型裝配線平衡問題的分布魯棒優化模型

2.1 問題描述

考慮工時不確定的第二類MMUALBP（MMUAL BP-Ⅱ）是在裝配線工作站數量已知的情況下，最小化生產節拍。其每種產品每道工序的裝配時間都是一個不確定的數值，工序時間的概率分布信息不可知，N個工序時間的歷史樣本數據已知。相較于普通的直線型單模裝配線，混流U 型裝配線的復雜性在于混流處理和工序分配。直型線的工序分配只能單向進行，而U 型線可以從前向后和從后向前雙向進行。對于混流的處理，一般采取的方式是根據最小生產循環（Minimal Production Set，MPS）原理構建綜合工序優先級圖[21]，將“混流”問題轉換為“單?！眴栴}，如圖1 所示，已知MPS 為1∶1∶1。

圖1 綜合優先級圖Fig.1 Comprehensive priority chart

針對工時不確定的MMUALBP，提出幾點假設：(1)工序的時間都是不確定的，但都服從輕尾分布；(2)所有模型的優先級圖都可以構成綜合優先級圖；(3)不同的產品具有相似的工序，相同工序必須分配到同一個工作站；(4)所有模型相同工序的優先級關系相同。

2.2 混流U 型裝配線平衡問題的分布魯棒優化模型

針對工時不確定的MMUALBP-Ⅱ，優化目標定義為最小化生產節拍，DRO 模型可以表示為：

滿足約束：

其中，E表示情景集，ztkCε為1 表示在情景ε中工作站k的總裝配時間超過節拍時間tC，否則為0。參考上述方式，本文針對樣本集提出一種魯棒性指標RL：

3 改進的遺傳算法

式(16)為產品的總需求；式(17)為綜合優先級圖中各工序根據MPS 計算得出的加權時間；式(18)表示每道工序都被分配至一個工作站；式(19)表示工作站的總時間不得超過節拍時間；式(20)和式(21)分別表示向前和向后的工序分配需要滿足優先級約束。其中：M為模型數量，m=1.2,···,M；dm為MPS 中模型m的需求；D為所有模型需求總量；K為工作站數量，k=1,2,···K；J為工序數量，j=1,2,···J；t?jm為模型m的工序j裝配時間；T?j為工序j的加權時間；tC為節拍時間；當分配順序從前向后、工序j分配給工作站k時，xjk為1，反之為0；當分配順序從后向前，工序j分配給工作站k時，yjk為 1，反之為 0；Pr為工序優先級矩陣。

2.3 分布魯棒模型的對偶轉化

根據強對偶原理，將DRO 模型中求極端分布期望問題轉化為易于計算的形式：

2.4 魯棒性指標

魯棒性指標用于衡量分配方案的魯棒性，一般通過工作站的過載情況衡量方案的魯棒性[22-24]。文獻[24]中通過方案正常運行的比例作為衡量魯棒性的指標Rrob，并將其作為模型約束，具體可以表示為：

裝配線平衡問題是典型的非確定性多項式難問題（NP 問題），當問題規模較小時，可以采用精確算法快速求解，當問題規模較大時，精確算法的求解效果較差，甚至無法求解，因此，越來越多的研究人員采用智能優化算法進行求解。遺傳算法[25](Genetic algorithm，GA) 是基于達爾文進化論的智能優化算法，因為其簡單、求解速率快等優點被廣泛應用于各領域問題的求解。本文提出一種用于求解上述模型的IGA。

3.1 編碼和解碼

針對MMUALBP-Ⅱ，IGA 采用優先級權重的編碼方式，初始對每道工序賦予[0,1]之間的隨機數，作為該工序的權重系數，以Jackson 問題為例，其優先級權重編碼如圖2 所示。

圖2 Jackson 優先級權重編碼Fig.2 Jackson priority weight coding

根據URBAN[26]提出的影子約束關系（圖3），同時從前后兩個方向進行工序分配，具體步驟如下：

圖3 影子約束關系圖Fig.3 Shadow constraint diagram

步驟6：如果k=K-1，將剩余工序分配至工作站K，輸出分配結果，否則k=k+1，轉至步驟2。

3.2 適應度函數

適應度代表個體在種群中生存的優劣程度，IGA 的適應度函數可以表示為：

3.3 選擇操作

IGA 采用輪盤賭選擇法進行個體選擇，其思想是個體被選擇的概率與適應度大小成正比，可以描述為：

其中，P(xi)為個體xi被選中的概率。

3.4 交叉操作

IGA 采用實數編碼，因此交叉操作采用模擬二進制交叉。首先需要生成[0,1] 內的均勻分布隨機數u，然后根據u計算傳播因子βa：

其中：p1和p2均為親代個體，c1和c2均為交叉后產生的子代個體。

3.5 變異操作

變異操作中隨機選擇染色體中某個基因，用[0,1]區間中的隨機數替換，過程如圖4 所示。

圖4 變異過程Fig.4 Variation process

3.6 自適應交叉和變異概率

為改善GA 易于陷入局部最優的問題，IGA 引入了自適應交叉概率Rc和變異概率Rm，根據種群的權重編碼排序結果調整變異和交叉的概率，使得種群在聚集程度高的時候提高變異概率，降低交叉概率，而在聚集程度低的時候提高交叉概率，降低變異概率。

其中，Diff_Num 表示權重大小排序后不相同的個體數，Size 表示種群總數。

4 標準算例測試與分析

4.1 實驗設計和環境參數

為了驗證所提模型和算法的性能，采用https://assembly-line-balancing.de/中的混流數據集作為標準數據，如表1 所示。與確定性優化（Deterministic optimization，DO）、SO 和RO 方法比較，SO 模型參考文獻[4]，置信水平取95%，RO 模型參考文獻[8]，區間擾動系數ψ取0.1，DRO 中置信水平β和η均取95%。實驗中假定所有工序的裝配時間tjm不固定，且滿足輕尾分布的假設。為了模擬真實環境，以標準時間為期望，以0.1 倍的期望作為方差，生成200個樣本數據。模型的求解采用IGA 和GA，種群大小設置為30，精英保留數為2，迭代次數為500，IGA 初始的變異和交叉因子分別設置為0.2 和0.5，GA 恒定為0.1 和0.8，測試指標為節拍時間，為避免隨機性，對每個算例獨立運行10 次。測試軟件為Matlab2021b，測試環境為11th Gen Intel(R) Core(TM) i7-11800H @2.30 GHz，16 GB RAM。

表1 測試算例Table 1 Test examples

4.2 測試結果與分析

表2 給出了問題Kim1～6 的測試結果，從最優生產節拍指標最優值（Best）看，SO 所求得的節拍時間最小，DRO 次之，RO 最大。對于上述結果，因SO 已知工時的概率分布信息，可以求得最小的節拍時間，而RO 考慮最壞情況最差值（Worst），故所得的節拍時間最大，DRO 則是利用了歷史數據信息，通過求取極端分布的情況下期望上界，因此所獲得的節拍時間介于SO 和RO 兩者之間。根據不同樣本個數對比結果可以看出（表3），隨著樣本數量的增加，DRO得到的節拍時間會減少。這是因為隨著樣本數量N的增加，Wasserstein 球的半徑會逐漸降低，使得模型的保守程度降低。從表2中DRO+IGA 和DRO+GA的對比結果來看，IGA 相較于GA，在Kim1～6 問題的求解上都得到了更小的生產節拍，均值（Mean）和標準差（Std）的值也表明IGA 的穩定性更好，僅在Kim4 中IGA 的Std 值差于GA，這說明在求解本文模型上，IGA 的性能要優于GA。

表2 對比測試結果Table 2 Results of comparison test

表3 不同樣本個數對比結果Table 3 Comparison results of different sample numbers

為進一步驗證模型解的魯棒性，采用相同的方式生成10 000 條樣本數據，分別計算三種模型解的魯棒性指標值，結果如表4 所示。SO 模型雖然已知裝配時間的概率分布信息，但在生產環境中可能和實際運行中的數據存在偏差，不能應對所有可能的場景，因此所得解的魯棒性較低；RO 模型因為考慮最壞情況，因此能完全應對時間不確定性所帶來的擾動，所得解的魯棒性最高，其RL值均達到1；DRO模型因為考慮樣本數據和極端分布的情況，所得解的魯棒性介于SO 和RO 之間，但RL值基本接近1 的程度，說明DRO 模型具有較好的魯棒性。圖5 給出了更加直觀的結果，其中f代表頻率。

表5 給出了SO、RO 和DRO 3 種模型的魯棒代價（POR）。參考文獻[27]，魯棒代價可以通過下式計算：

表4 魯棒性指標對比結果Table 4 Comparison results of robustness metric

表5 3 種模型的魯棒代價Table 5 Price of robustness for three models

圖5 不同模型目標值和實際生產節拍對比Fig.5 Comparison of object value and actual cycle time of different models

其中，xDO表示確定性優化的最優決策，xmodel表示工時不確定條件下模型做出的最優決策，f(·)表示決策所對應的節拍時間。如表5 所示，在Kim1～6 中表現出的魯棒性代價關系為SO 最小，RO 最大，DRO 介于SO 和RO 兩者之間，說明為了應對工時的不確定性，SO 模型所做出的決策付出的代價最小，RO 付出的代價最大，而DRO 介于SO 和RO 之間。結果表明，SO 的 保 守 性 最 低，RO 最 高，DRO 介 于SO 和RO 之間。

5 斷路器生產實例分析

某公司斷路器抽架裝配線為包含14 個工作站的混流U 型裝配線，可以生產A、B、C、D 四種型號的產品。抽架裝配過程包含機構裝配等56 道工序，具體的工序時間和工序優先級關系如表6 和圖6 所示。表6 中所示的裝配時間（t）為測得的標準時間，由于裝配時間受到工人熟練度、環境等影響存在波動，在進行裝配線平衡時需要考慮這種不確定性。

表6 斷路器抽架工序信息Table 6 Chassis process information of circult breaker

圖6 斷路器抽架工序優先級關系圖Fig.6 Circuit breaker chassis process priority diagram

真實的生產環境中各工序的裝配時間通常圍繞標準時間上下隨機波動，因此可以采用高斯分布生成數據模擬真實數據，具體的生成方式和相關參數設置與本文第4 節相同。當MPS 為1∶1∶1∶1 時，測試指標為最優生產節拍，采用IGA+DRO 的方式，優化前節拍時間為149 s，優化后為92.7 s，隨機樣本測試的魯棒性指標值為0.960 7，優化前后的工序分配見表7。相較于原方案，在工時不確定的情況下，采用DRO+IGA 優化后的裝配線具有更小的節拍時間，說明該裝配線得到了很好的優化，各工作站的負載更為均衡，同時所設定的節拍時間和工序分配方案可以很好地抵抗工時不確定性帶來的擾動，使得裝配線具備較好的魯棒性。

表7 工序分配Table 7 Distributing of process

6 結 論

本文采用一種基于Wasserstein 距離的分布魯棒優化框架對工時不確定的MMUALBP-Ⅱ進行建模；以樣本推導的經驗分布為中心，以Wasserstein 距離為度量，構建模糊集并建立了DRO 模型，通過對偶轉換，將原模型轉化為易于求解的形式；設計了一種基于工作站過載情況的魯棒性指標，并將其作為模型約束，增強解的魯棒性；同時提出一種改進的遺傳算法用于上述模型的求解，采用自適應交叉和變異因子，并設計了一種基于區間數的解碼方案；通過標準的測試用例，驗證了IGA 相較于GA，在求解上述模型上的性能更好，同時驗證了所建立的DRO 模型相較于一般的SO 和RO 模型，在保證解具有較高魯棒性的同時，節拍時間有所降低，并且隨著樣本數量的增加，節拍時間還會進一步降低；最后通過斷路器抽架案例，進一步驗證了所提模型的有效性，為解決該類工程問題提供了參考方案。