某汽車座椅混流裝配線多目標排產優化

姜興宇，李世磊，田志強，鄧健超，韓清冰，劉偉軍

(沈陽工業大學 機械工程學院，沈陽 110870)

汽車座椅作為典型的面向訂單的多品種大批量產品，其裝配線常常處于多型號、多狀態、多批次同時在線的混流狀態，不同裝配工藝頻繁切換、不同座椅生產節拍差異大，導致裝配周期長、資源利用率低.因此，如何在規定時間內滿足不同客戶訂單需求，提高裝配線資源利用率，縮短產品裝配時間，提高裝配線產能已經成為汽車座椅混流裝配線排產優化的核心問題.完工時間與等待時間是研究混流裝配線排產問題的經典指標，其長短已成為混流裝配線能否保質保量地完成主機廠訂單的關鍵，實際生產過程中考慮產品裝配完工與等待時間，既能提高混流裝配效率，及時滿足客戶多樣化訂單的需求，又能平衡工作站的負載，合理安排生產計劃，使其更加符合企業的生產實際.因此，面向訂單的汽車座椅排產優化問題的研究具有重要的應用經濟價值.

混流裝配線排產問題是通過調整產品投產序列以協調生產、提高混裝線生產效率的復雜多目標組合優化問題，一直是生產運作和組合優化領域的熱點[1-2].1963年，Wester等[3]首次提出混流裝配線的排產問題，隨后的幾十年中，該問題已被證明是組合優化問題中非確定多項式困難問題(non-deterministic polynomial hard problem，NP-hard)，具有計算復雜性高、求解難度大等特點.該算法是求解混流裝配線排產問題的重要組成部分.提升算法的求解效率，優化算法求解機制，設計適用于此類問題的高效優化方法，是研究混流裝配線排產問題的重要內容.

Ishigaki等[12]構建了以最小化總未完成工作時間為目標的排產優化模型，并提出了適用于該模型求解的改進模擬退火算法；Tahriri等[13]構建了以最小化完工時間和最小化裝配數量為優化目標的混流裝配線排產模型，并提出了一種改進的遺傳算法——模糊自適應遺傳算法進行求解；蒙秋男等[14]研究了按工作日歷組批、零部件配套約束下的混流裝配線排產方案，以最小化完工時間、總提前拖期、總加班時間為目標構建排產優化模型，并設計了空間蟻群算法求解，通過實例驗證了排產方法的有效性；韓忠華等[15]構建了以產品完工時間、等待時間、空閑時間等為優化目標的排產模型，設計了一種改進緊致遺傳算法求解該問題；李燚等[16]構建了以瓶頸工位負載平衡、最小化工位加工滯后次數為目標的優化模型，提出一種改進蟻群算法進行求解，有效提高了求解過程中解的收斂速度及精度；張煒等[17]以訂單緊急度、匹配度和負荷均衡為上層目標，以工位空閑及產品等待時間為下層目標，構建了多目標主從關聯優化模型，設計一種結合Pareto前沿解的雙層交互式遺傳算法求解該模型，結果驗證了所提模型及算法的有效性.

綜上，學者們已經從排產模型構建、提高算法求解性能等方面對混流裝配線排產問題進行了系列研究，取得了一定成效，但還尚不完善，仍存在以下問題：

1)汽車座椅混流裝配線裝配產品種類多、批量大、不同工藝頻繁切換，導致排產模型的建立及資源約束更為復雜，實現統籌考慮產品完工時間和等待時間的優化目標極為困難.而現有大批量混流排產問題的研究較少考慮產品完工時間與等待時間的協同優化沖突，導致裝配線生產資源浪費.

2)在求解工藝復雜的多目標排產優化模型時，對求解算法的尋優能力、種群多樣性要求較高，傳統優化算法如遺傳算法等由于進化策略簡單、靈活性較差，會出現搜索速度慢且容易陷入局部最優的問題，從而很難獲得理想的排產優化方案.針對多目標優化問題，評價方法的科學性、客觀性也決定著最終的優化效果.因此，如何提高算法的求解性能并結合科學、客觀的評價手段以獲取全局最優解是多目標排產優化問題的重點.

基于此，本文針對汽車座椅多批次、大批量混流裝配、工藝及節拍差異大導致裝配線資源利用率低、交貨期長、難以滿足主機廠需求等問題，以汽車座椅混流裝配最小等待時間和完工時間為目標，設計了一種改進快速非支配排序遺傳算法(non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ)對排產模型進行求解，應用改進的灰色關聯分析(grey relational analysis，GRA)與理想點接近法(technique for order preference by similarity to an ideal solution，TOPSIS)混合評價方法，對所得Pareto最優解集進行評價，得到最優的排產方案.通過實例分析，驗證本文所提模型及算法的有效性和實用性.

1 多目標混流裝配排產問題

1.1 問題描述

混流裝配線的排產問題主要是根據客戶對不同類型產品的需求量，確定產品間的排產順序，從而滿足客戶需求的問題.本文研究假設混流裝配線已完成平衡設計及改善，優化目標的選取僅考慮排產問題.在靜態環境下，混流裝配線排產問題可以描述為：在計劃完工時間T內生產M種批量為im的不同類型產品i(i=1，2，…，M)，產品i需要按設定的排產順序依次經過m個工位k(k=1，2，…，m)，通過N道裝配工序Uj{j=1，2，…，N}的加工，消耗裝配時間tirj{i=1，2，…，M，j=1，2，…，N}完成各道工序的裝配，各類型產品可以以任意投產順序依次裝配，而不同類型產品的裝配流程及各工位的裝配時間均不同，同時可以組成多種排產方案.最后從全局角度研究，將M種產品按固定的比例設定排產順序，合理安排產品的裝配，為企業確定最優的投產順序，使得排產方案滿足一個或多個生產指標要求.

為了解決混流裝配線排產問題，需要滿足如下的假設條件：1)不同產品的相同任務分配到同一個工作站；2)假設產品裝配工序需要的物料都可以連續供應，不存在因物料不足而等待的現象；3)裝配線上的產品裝配按照先進先出原則進行；4)每一個裝配工藝的操作時間是確定的.

為能夠在規定時間內滿足客戶多樣化訂單，優化混流裝配線上產品的投產順序，并減少在制品在線上的庫存成本和人工閑置浪費的成本，同時減少總裝配時間，本文排產優化模型的目標定為完工時間和產品等待時間最小.

1.2 優化目標

1.2.1 相關參數及含義

模型中涉及的相關參數及含義如表1所示.

表1 模型中相關參數及含義

1.2.2 目標函數

目標函數設為最小生產單元里所有產品完成裝配時的完工時間和產品等待時間最小，即

f=min(T完工，T等待)

(1)

1)完工時間目標

完工時間反映了混流裝配線的生產能力，其長短成為混流裝配線能否及時滿足客戶多樣化訂單需求的關鍵，其表達式為

T完工=max ETirjk

(2)

2)等待時間目標

當上一個產品在工位進行裝配時，下一個產品已經進入該工位，需要等待上一個產品完成作業后才能進行裝配，這段時間就是產品的等待時間，其表達式為

(3)

1.2.3 約束條件

目標函數的相關約束條件為

ETijk=BTijk+imtirjk(r=1，2，…，im；j=1，2，…，N)

(4)

(5)

BTirjk=max(ETir(j-1)k，ETi(r-1)jk) (r=2，3，…，im；j=2，3，…，N)

(6)

(7)

(8)

式(4)表示第i個產品在第j個工作站上結束裝配時消耗的總時間等于裝配消耗時間與第i個產品在第j個工作站上開始裝配時消耗的總時間之和；式(5)表示各個工作站的總裝配時間小于理論生產節拍；式(6)表示投產中第i個產品在第j個工作站上開始裝配時消耗的總時間等于第i個產品在第j-1個工作站上結束裝配的時間和第i-1個產品在第j個工作站上結束裝配的時間中的較大值；式(7)表示一個工位同一時間只能裝配一個產品；式(8)表示任意一個工位的裝配時間等于該工序裝配M種產品的裝配時間的加權平均值.

2 算法設計

具有多品種大批量復雜工藝特征的混流裝配線排產問題是典型的NP-hard問題，相對于傳統流水裝配線排產問題，具有裝配工藝復雜、目標約束多、求解難度高等特點.在求解此類問題時，智能優化算法是目前求解混流裝配線排產問題的一種主要方法，與整數規劃、分支定界等精確方法相比，無論在求解速度還是解集質量方面均表現出了更好的特性.但傳統的優化算法如遺傳算法、模擬退火算法等由于尋優能力不足、進化策略簡單，難以獲得理想的優化方案[18].NSGA-Ⅱ是Deb等[19]提出的一種元啟發式算法，由于其在求解低維問題時具有良好表現，并且求解速度相對較快、容易實現，因此被眾多學者應用于求解多目標裝配線排產問題.然而，傳統NSGA-Ⅱ算法由于采用模擬二進制編碼方式，計算擁擠度時未考慮某個淘汰解對鄰域解擁擠距離的影響，導致其在求解更加復雜的多品種大批量復雜工藝特征的混流裝配線排產問題時速度慢，Pareto解集質量差.因此，本文針對混流裝配線排產的實際問題，設計一種改進NSGA-Ⅱ算法用于模型求解.根據不同型號汽車座椅需求量在一個最小循環周期內的投產比例，提出了一種基于最小投產比例的實數編碼方法，提高了算法的解碼效率；采用一種基于產品的OC(order crossover)交叉策略及多點變異策略，在保證算法種群多樣性的同時提高了算法搜索效率；應用一種循環擁擠排序的精英選擇策略，避免淘汰解對鄰域解擁擠距離的影響，提高算法的收斂速度和魯棒性，并保證了非劣解的均勻分布.改進NSGA-Ⅱ算法流程如圖1所示.

圖1 改進NSGA-Ⅱ算法流程

2.1 編碼操作及種群初始化

采用基于產品最小投產比例的實數編碼方式對染色體進行編碼，其長度由最小循環周期內的所有待裝產品總數決定，一個基因代表一個產品，目前A、B、C、D、E、F六種座椅需求量為40、40、160、160、120、120，則A、B、C、D、E、F六種座椅在一個最小循環周期內的投產比例為1∶1∶4∶4∶3∶3，編碼方式為ACCCDDCBEEDDFFEF，滿足編碼條件的個體隨機分配組成初始種群.

2.2 交叉與變異

基于產品最小投產比例的實數編碼后基因與產品一一對應，而且基因由實數表示，故有較大概率在不同基因位置出現相同產品，因此交叉操作選擇應用基于產品的OC交叉策略，提高種群的多樣性.在初始種群中隨機選擇兩個染色體，作為父代染色體1、2，并將其等分為頭部和尾部兩部分，在父代1中按照基因排列順序挑選出與父代2尾部相同的基因，構成子代的頭部，子代的尾部為父代2的頭部基因，隨即產生子代染色體，如圖2所示.

圖2 交叉操作

在進行變異操作時，采用多點變異策略.在父代基因中任意選取不小于2個基因，保留剩余基因，在相同位置將選中的基因按照先后順序進行倒序，由此組成變異后的子代，如圖3所示.

圖3 變異操作

2.3 精英選擇策略

整合新生成的子代與父代個體Pareto解，并將其看做一個新的種群，計算新種群中每一個個體擁擠距離；刪除新種群中擁擠距離最短個體并重新計算剩余個體擁擠距離；判斷剩余個體數是否滿足需求，循環刪除，直到滿足個體數量要求結束算法并輸出最優個體集[20].

2.4 基于改進GRA與TOPSIS方法的最優解選取

Pareto最優解集法是一種公認的多目標優化問題的有效求解方法[21].在通過改進NSGA-Ⅱ算法的混流裝配線排產優化得到一組Pareto解集后，決策者還面臨如何從這組Pareto解集尋求出最滿意方案的問題.常見的多目標決策方法有：加權和方法、字典序法、層次分析法、熵值法、數據包絡方法(data envelopment analysis，DEA)、多維偏好分析的線性規劃方法(linear programming techniques for multidimensional analysis of preference，LINMAP)、TOPSIS法、GRA等.TOPSIS法是通過檢測評價對象與最優解、最劣解的距離來進行排序，其結果能精確地反映各評價方案之間的差距，但忽略了各方案的變化趨勢，而GRA是運用各個影響因素的樣本數據來計算灰色關聯度，能夠準確分析因素之間的關系，在分析變化趨勢和發展態勢時有著較強的性能.因此，本文采用一種GRA與TOPSIS的混合評價方法，將靜態距離和動態趨勢結合起來，對所得Pareto最優解集中排產方案進行評價，具體實施步驟[22]如下：

1)構造向量歸一標準化矩陣.對于具有n個評價指標的q個對象，其初始矩陣為

(9)

在此基礎上，構造加權規范矩陣，標準化矩陣為

(10)

2)建立最優解與最劣解集合.最優解集合w+、最劣解集合w-由各列中最大元素值、最小元素值所組成，即

(11)

(12)

3)計算各評價對象與最優方案、最劣方案的接近程度，其表達式為

(13)

(14)

4)計算各評價對象與最優方案間的灰色關聯系數，其表達式為

(15)

式中，ρ為灰色關聯系數，通常取0.5.

5)計算各評價對象與最優、最劣方案間的灰色關聯度，其表達式為

(16)

6)整合歐氏距離和灰色關聯度，其表達式為

(17)

(18)

7)計算各評價對象與最優方案的貼近程度，其表達式為

(19)

式中，Ei值越趨近于1，說明評價對象越優.

3 案例分析

3.1 企業現狀

某汽車座椅裝配企業座椅車間主要產品類型包括五座車型的前后排座椅和七座車型的前排、中排及后排座椅，由于汽車消費市場的需求波動導致公司客戶的產能調整，原有汽車座椅裝配線生產能力過剩，導致生產成本中的直接人工成本比例升高，現將原有整車總裝線調整為多種產品型號混流生產.然而，裝配線調整后帶來的產品需求變化，進而影響生產計劃改變，混流裝配線需要在一個生產計劃周期內裝配不同型號的產品，由于不同型號產品存在工序和裝配時間的差異，在進行排產裝配過程中，出現產品等待時間過長、工人負荷過大的現象，降低了企業實際的裝配效率，加大工人工作負荷.針對此類問題，可以通過對產品排產順序的調整，充分利用工作時間，在裝配過程中進行座椅型號的切換，這時就會產生產品投產的排序問題.因此，只有在混流裝配過程中合理配置座椅類型、投產順序、裝配數量和裝配時間等，才能充分利用混流裝配線的裝配資源，最大化裝配線的裝配效率及產能.在實際生產過程中，合理有效的排產方案可以提高裝配效率，減少工人工作負荷，以滿足客戶對訂單的需求.

該企業混流裝配線共有19道工序，加工6種類型汽車座椅產品，汽車座椅裝配車間如圖4所示，前、中排座椅混流裝配線布局如圖5所示.上下兩部分對稱分別生產左側與右側座椅，左右側座椅生產節拍完全一致，生產時兩條線同時進行裝配達到同步化生產.其中裝配線的左半部分完成靠背和坐墊的裝配，右半部分的流水線完成座墊和靠背的結合以及后續裝配和整裝下線，汽車座椅混流裝配時間及綜合作業先序圖如圖6所示.

圖4 座椅裝配車間

圖5 汽車座椅裝配線布局

圖6 產品裝配綜合作業先序圖

3.2 優化結果

根據企業實際數據，目前車間日計劃產量如表2所示，A表示258XT前排，日計劃產量40臺，B表示258XT中排，日計劃產量40臺，C表示258GT前排，日計劃產量160臺，D表示258GT中排，日計劃產量160臺，E表示JBUB，日計劃產量120臺，F表示D2SB，日計劃產量120臺，一個批次加工工件數量為640件，在一個最小循環周期內，A、B、C、D、E、F六種座椅類型投產比為1∶1∶4∶4∶3∶3.

表2 各型號座椅需求

基于MATLAB編程，以汽車座椅混流裝配線完工時間、等待時間最小為目標，運用本文提出的改進NSGA-Ⅱ算法對上述案例進行求解，測試環境為：在Windows環境下運用MATLAB對改進NSGA-Ⅱ算法進行編碼，CPU為Intel(R)Core 1.70 Hz；內存環境為4 GB.初始種群大小設置為300，迭代次數為200，交叉概率為0.80，變異概率為0.20，得到基于改進NSGA-Ⅱ算法的Pareto最優解集如圖7所示.在此基礎上，基于改進GRA與TOPSIS混合評價方法對所得Pareto最優解集中各排產方案進行評價，得到最優排產方案如表3所示.

圖7 基于改進NSGA-Ⅱ算法所得Pareto最優解集

改進NSGA-Ⅱ算法的運行結果為汽車座椅混流裝配線排產提供了眾多可行的優化解，汽車座椅裝配完工時間和等待時間存在協同優化沖突，對具有多品種大批量特征的汽車座椅混流裝配線產品進行排產，在確定座椅批量的基礎上，隨著汽車座椅完工時間的增加，等待時間呈明顯下降趨勢，并逐漸達到最優.表3中，編號5的排產方案BCDDECCDDCEFFFEA，當裝配一個批量的汽車座椅完工時間為899.08 s、空閑時間為683.28 s時，Ei達到最大值，為0.591 648，更貼近1，故此方案為最優排產方案.

表3 基于改進GRA與TOPSIS方法的最優排產方案選擇

3.3 算法有效性分析

為驗證本文算法的有效性，分別運用基礎NSGA-Ⅱ算法與本文算法對排產方案進行優化，得到算法改進前后帕累托前沿點對比如圖8所示.由圖8可以看出，兩種算法均表現出非支配排序遺傳算法固有的收斂速度快的特性，但改進后的NSGA-Ⅱ算法無論收斂速度還是解集質量均要優于基礎NSGA-Ⅱ算法.表4為算法改進前后最優解對比.由表4可以看出，在算法改進前后最優的十組解中，經多目標評價決策后的兩種算法的評價指標，改進NSGA-Ⅱ算法的各評價對象與最優方案的貼近程度Ei值均大于改進前算法各評價對象與最優方案的貼近程度，多目標整體優化質量提高了1.6%；改進后的NSGA-Ⅱ算法既繼承了NSGA-Ⅱ算法收斂速度快的優點，在算法求解過程中，又可以通過循環擁擠排序機制的自適應調節，提高了解的多樣性.

圖8 算法改進前后帕累托前沿點對比

選擇改進前后兩種算法最優的前五組解進行比較，對比結果如表4所示.算法改進前后方案目標函數值對比如表5所示.

表4 算法改進前后最優解對比

表5 改進前后排產方案對比

優化后的排產方案為BCDDECCDDCEFFFEA，汽車座椅裝配總時間由9.5 h降至7.5 h，減少了21.05%，總等待時間由11.35 h降至9.98 h，減少了12.07%，充分利用了裝配線的裝配能力，降低了座椅裝配的總等待時間，優化效果顯著.

通過表4～5、圖8可以看出，改進NSGA-Ⅱ算法前沿點均優于基礎NSGA-Ⅱ算法前沿點，最優解均勻分布在不連續前沿的各個線段上.改進后的NSGA-Ⅱ算法求解性能有了較大的提升，有效縮短了裝配線的等待時間，提高了生產節拍，對于混流裝配線排產問題有著更好的適用性，本文所提改進策略提高了算法的求解質量，增強了算法求解性能.

4 仿真驗證

在混流裝配線排產方案設計階段，需在裝配線投產前對排產方案進行驗證，以便檢驗給定的排產方案是否符合實際生產情況，若在裝配線投產后再驗證排產方案是否合理，可能會造成企業資源浪費，不能準時完成客戶生產訂單，因此預先對混流裝配線排產方案進行仿真驗證尤為重要.運用Plant Simulation仿真軟件對給定的排產方案進行仿真分析，動態模擬混流裝配線的實際運行狀況，完善混流裝配線的排產設計.

4.1 仿真建模

根據表3中的排產方案，建立汽車座椅混流裝配線Plant Simulation仿真模型，如圖9所示.結合裝配線作業完工時間和等待時間，設置傳送帶長度為3 m，傳送速度為0.3 m/s，根據客戶訂單需求，設置訂單源生產節拍為44 s，訂單數量為640套.裝配路線通過實際工藝路線對各工位進行連接，若不同型號座椅在各自工位分別加工，則通過Simtalk仿真語言進行控制.

圖9 汽車座椅混流裝配線仿真模型

4.2 仿真結果分析

以目前車間日計劃產量640套座椅為例，對算法優化前后的排產方案進行仿真，原批量排產方案如圖10所示，部分混流排產方案如圖11所示，通過比較排產方案優化前后混流裝配線完工時間、設備利用率、生產作業工時等指標，驗證所提模型及算法的有效性.

圖10 原批量排產方案

圖11 部分混流排產方案

4.2.1 完工時間對比

原批量排產方案生產640套座椅完工時間為9.55 h，如圖12所示.混流排產方案生產640套座椅完工時間為7.6 h，如圖13所示.

圖12 原批量排產方案完工時間

圖13 混流排產方案完工時間

對比圖12～13可知，在裝配相同訂單的前提下，混流裝配線排產優化后裝配時間由9.55 h下降至7.6 h，減少了20.42%，同時裝配線的運輸效率得到顯著改善，極大地提升了裝配線的裝配效率，充分利用了人力、物力等資源，降低了工人工作負荷.

4.2.2 設備利用率對比

原批量排產方案各設備利用率如圖14所示，平均設備利用率為33.48%.混流排產方案各設備利用率如圖15所示，平均設備利用率為51.54%.

圖14 原批量排產方案各設備利用率

圖15 混流排產方案各設備利用率

對比圖14～15可知，混流裝配線排產優化后，工作站的平均利用率提高了18.06%，等待率平均下降了21.27%，堵塞率平均下降了99.26%，顯著改善了產品在工作站內的堵塞與等待現象，表明排產優化后的混流裝配線可提高工作站利用率，減少堵塞與等待現象.

4.2.3 生產作業工時對比

原批量排產方案各工位平均等待時間如圖16所示，其裝配線綜合等待時間為11.38 h.混流排產方案各工位平均等待時間如圖17所示，其裝配線綜合等待時間為9.95 h.

圖16 原批量排產方案各工位平均等待時間

圖17 混流排產方案各工位平均等待時間

對比圖16～17可知，汽車座椅在混流裝配線上的平均等待時間較排產優化前下降了12.56%，累計加工數量得到極大提升，表明混流排產方案可顯著減少產品裝配時的等待時間，提高裝配效率，對改善前原批量排產方案而言，有著明顯的效率優勢.

運用Plant Simulation物流仿真軟件對車間的裝配線進行仿真模擬，通過代入現實設備與場地參數，分別對比優化前后的完工時間、設備利用率、等待時間.對比結果顯示：混流排產方案明顯優于原批量排產方案，完工時間由9.55 h降低到7.6 h，平均設備利用率由33.48%上升到51.54%，設備利用率上升18.06%，等待時間由11.38 h降低到9.95 h.仿真結果表明，本文所提模型及算法能有效縮短裝配周期，提高裝配線資源利用率.

5 結 論

本文通過分析得出以下結論：

1)本文針對混流裝配線客戶訂單多樣化、不同裝配工藝頻繁切換、不同類型產品裝配時間難以統一，導致裝配周期長、難以滿足客戶需求的問題，綜合考慮產品最小完工時間、最小裝配等待時間目標，構建了面向客戶訂單的多品種大批量混流裝配線排產優化模型.

2)提出一種改進非支配排序遺傳算法對上述模型進行了求解，應用循環擁擠排序精英選擇策略，解決了NSGA-Ⅱ算法收斂性和解的多樣性差的問題，應用改進GRA與TOPSIS的多目標評價方法對排產方案進行綜合評價，使得兩個目標達到Pareto最優.

3)為進一步驗證提出的模型與方法的實用性，應用Plant Simulation對優化前后的排產方案進行仿真驗證.結果表明：本文所提模型及算法能有效提高混流裝配線的生產效率、降低工人工作負荷、縮短產品裝配與等待時間.