基于遺傳算法的服裝大規模定制生產線平衡優化

陳 莎，修 毅，李雪飛

(北京服裝學院 信息中心，北京 100029)

在服裝制造業中，互聯網技術的應用有效促進了產銷端信息平衡，催生出以需求驅動生產的大規模定制生產模式。與傳統服裝企業相比，服裝大規模定制企業的生產訂單具有單量小、款式多變、下單時間不確定等新特點，這就要求生產線要更具生產柔性[1]。若企業仍按標準生產線進行生產，勢必會引起工位忙閑不均、生產設備利用率低等問題。另外，某些定制項復雜的訂單根本無法在標準生產線上完成生產，因此大規模定制生產線平衡問題亟待解決。

在生產車間調度平衡優化的相關研究中，遺傳算法(genetic algorithm, GA)及其改進算法的應用已相對成熟。基于GA的車間調度平衡研究主要分為2類：一是對車間調度數學模型不斷改進使算法優化結果更切合實際生產需求。當生產方式由標準化大批量生產向多品種小批量生產轉變，數學模型也相應轉變為多品種混合生產車間調度問題模型。比如：考慮工件序列約束、以最小化最大完工時間為目標，構建動態流水車間制造單元調度問題模型[2]；考慮加工質量、最大完工時間和加權成本等優化目標，構建多目標柔性作業車間調度問題模型[3]；考慮工件到達時間、加工時間、排隊規則出錯等影響因素，構建不確定因素擾動的柔性作業車間魯棒調度問題模型等[4]，以上模型呈現出動態性、多目標性、不確定性及約束性等復雜的特性。二是對算法本身的改進以保證尋優效率和結果準確性。雖然GA有隱性并行性和全局解空間搜索能力，善于解決諸如車間調度這種規模大且復雜的非線性問題，但在實際應用時也會出現早熟收斂或收斂緩慢等不足，因此學者們會在基因編碼、算法設計以及遺傳操作等方面對標準GA進行改進，增加收斂速度。比如，在基因編碼方面，采用自然數編碼、三元組編碼等多種編碼方式，擴大了GA的使用領域[5-6]；在算法設計方面，將模擬退火、拓撲方法、差異度閾值策略等理論思想嵌入GA框架中，有效提高了可行解的搜索能力[7-9]；在遺傳操作方面，對交叉、變異及適應度函數等進行自適應改善探究，使其可隨迭代次數進行動態調整，避免迭代過程中的早熟收斂[6，10]等。

在服裝領域，關于GA在大規模定制混合生產線平衡優化方面的應用探究還較少。目前大都是探討單品種、工序數少的服裝在標準生產線上的平衡優化，且以褲裝、襯衫等工藝較為簡單的服裝品類為例進行算法驗證[11-12]，對于總工序數較多、包含多組子生產線、工藝更為復雜的西服品類混合車間調度平衡相關問題無法解決。本文基于GA相關理論，綜合考慮工序約束、多優化目標、多子生產線以及混合投產等更為復雜的生產特點，對服裝混合車間調度平衡問題進行探究，完成混合生產線平衡優化模型構建及滿足約束的多目標優化算法設計，采用MatLab軟件技術，結合實例進行可行性驗證，有效提高服裝大規模定制生產車間的工序編制效率，使智能優化算法在服裝制造領域得到進一步的推廣和使用。

1 生產線平衡模型構建

多品種服裝共線定制生產的前提是，同一生產線上生產的通常都是結構、工藝相似，僅規格、部分部件不同的同品類服裝。在該服裝定制生產線中，個別定制工序存在的差別較大，其公共工序的工藝、工時是完全相同或僅略有差別，因此服裝定制生產適合于構建混流生產平衡模型，其模型構建如下。

1)確定混合生產線。在某特定生產計劃期內，根據單批次訂單內服裝產品的工序約束關系將各訂單的服裝工藝生產線整合為混合生產線。

以圖1為例，假設有A、B、C 3個服裝產品訂單共線生產，工序約束關系及工時數據分別如圖1(a)、(b)、(c)所示，依據公共工序合并，定制工序均保留的原則對所有種類服裝工序進行整合，合并為圖1(d)所示符合工序約束關系的混合產線。

注：圈內數字為工序編號；圈外數字為工序對應的工時，單位為min。

2)確定綜合工時。假設訂單A、B、C的生產量分別為5、3、2，工時數據如圖1(a)、(b)、(c)所示，根據式(1)可求出整合后混合生產線的各工序綜合工時，最終形成如圖1(d)所示的綜合工序圖。

(1)

式中：i為產品工序編號；Ti為工序i的綜合工時；m為該生產單元內第m個服裝定制訂單(m=1,2,…,M)；M為該生產單元內服裝定制訂單總數；qm為該生產單元內第m個服裝定制訂單的生產量；Q為該生產計劃期內每個生產單元的投產量；tmi為第m個定制訂單內服裝產品的第i個生產工序的工時(當訂單m內定制服裝產品的第i個工序為空時，tmi為0 min)。

其中，生產單元內訂單數M和訂單內服裝生產量qm的不同狀態可衍生出各種生產模式。比如：當該生產單元包含訂單數M=Q，qm均為1，即為個性化定制；M

3)確定優化方案。根據圖1(d)所確定的生產線滿足共線服裝的工序約束及工藝要求，符合混合生產基本條件。

基于GA相關理論進行編碼、解碼及算法設計，完成工序編制方案的尋優操作。并根據式(2)，求出該計劃期內服裝工序編制效率，對尋優結果進行驗證，判斷是否符合生產線編制效率一般大于85%的生產要求[13]。

(2)

2 編碼與解碼設計

2.1 編碼設計

由于GA通常不直接作用于問題解空間，所以需要通過編碼設計將生產線平衡問題的可行解空間與GA的碼空間相對應，合理的編碼機制對算法質量和尋優效率有很大影響。本文主要以矩陣形式對工序、工時、綜合約束關系3個部分進行編碼設計：工序部分采用自然數編碼如式(3)。每行代表1種符合約束關系的工序編制順序，即1個可行解，s代表第s個可行解(s=1,2,…,S)；S為工序編碼矩陣中可行解總數；xsr代表第s個可行解的第r個生產順序的工序號；工時部分采用實數編碼，見式(4)每行數值代表1種服裝的工時數據，tmi代表訂單m內服裝產品的第i個工序的具體工時；綜合約束關系部分采用二進制編碼，見式(5)。根據式(6)將所有工序按緊前約束關系生成N階方陣A，aij代表工序i對工序j的約束關系。

(3)

(4)

(5)

(6)

式中：i為該生產期內服裝產品的工序編號(i=1,2,…,N)；緊前工序為緊接某項工序的先行工序。

2.2 解碼設計

本文的解碼過程不僅是將編碼矩陣直譯為符合約束關系的工序順序，還需進一步按工序順序將服裝工序分配到工位，得到具體工序編制方案。

根據GA的碼空間與問題的可行解空間的對應關系，種群由S條染色體組成，每條染色體對應一個可行解編碼。以1條可行染色體為例，具體實現步驟如下。

(7)

步驟2：在滿足式(8)的情況下，按基因編碼對應的服裝工序依次分配到前(K-1)個工位，剩余的服裝工序無論總工時是否大于C，都分配到最后一個工位K上。

Tk≤C，(k=1,2,…,K)

(8)

步驟3：判斷工序分配是否結束。若此時仍滿足Tk≤C，則工序分配結束，該染色體對應工序編制方案的實際節拍為C；否則，進入步驟4。

步驟4：計算各工位時間的潛在最小時間增量Δt1,Δt2,…,Δtk,…,Δt(K-1)，其中，Δtk為分配至第(k+1)個工位第1個工序的工時。

步驟5：判斷搜索是否停止。令工位實際節拍C=max{Tk|k=1,2,…,K}，工位潛在節拍C′=min{Tk+Δtk|k=1,2,…,(K-1)}。若C≤C′，說明改變服裝工序分配方案并不能使實際生產節拍更小，搜索停止，該分配方案即為此染色體個體的最優分配方案，實際節拍為C；否則，更新C值，以C=C′為新的實際生產節拍，轉向步驟2重新對該染色體個體進行工序分配。

步驟6：步驟1～步驟5為1條可行染色體對應的解碼過程。當種群數量為S時，需要將以上解碼過程重復S次，生成S個問題可行解。

3 算法設計

在滿足服裝工序約束的情況下，同時考慮工位平順化和瓶頸節拍最小化2個優化目標，基于GA相關原理進行算法設計。基本框架如圖2所示。

圖2 GA基本框架

3.1 種群初始設計

初始種群的設計在一定程度上影響后代染色體的質量與分布。在初始化過程中染色體個體既要隨機分散地分布在可行解空間，也要滿足工序約束；因此，采用符合工序約束的隨機初始化策略來產生初始種群，使染色體都可譯碼為滿足服裝工序約束的隨機可行解。具體實現步驟如下。

步驟1：令s=1,并根據服裝綜合工序圖，得到綜合工序約束矩陣A。

步驟2：根據約束矩陣A搜索無緊前工序或緊前工序已全部分配完畢的服裝工序，即約束矩陣中對應列全為0，將其放入備選工序集合R。

步驟3：在集合R中隨機選擇一個工序，判斷該工序編碼是否已存在于第s個染色體的基因位中，若已存在，則重新隨機選擇；否則，分配給該工序1個染色體基因位，并更新約束矩陣A，即將矩陣A中已分配工序的行置0。

步驟4：再次轉入步驟2更新備選集合R，當第s個染色體內基因總數與服裝工序總數相同時，1條滿足工序約束關系的可行染色體生成。

步驟5：更新s值，令s=s+1，重復步驟2～步驟4，直至生成S個染色體。

3.2 適應度函數設計

適應度函數是評價個體優劣的依據，函數設計既要能體現種群內個體差異，也要符合優化目標，另外適應度評價過程還要簡潔高效，不然會一定程度影響GA的整體優化性能。本文平衡問題為多目標優化問題，優化目標主要有2個：一是整個計劃期內總工作時間最小，表示為工位實際節拍C(瓶頸節拍)最小化(見式(9))；二是各工位工作時間相對均衡，使產線運作更順滑，表示為平衡指數F2最小化(見式(10))。本文結合企業生產實際，利用加權求和法將多目標轉化為單目標，得目標函數F(見式(11))。

minC=min{maxTk}

(9)

(10)

F=aC+bF2

(11)

式中,a、b為目標函數權值。

適應度函數f通常是目標函數F變換構成，個體適應度越高，基因越優，被遺傳下來的概率也就越大。本文適應度函數為

(12)

3.3 遺傳操作設計

3.3.1 選擇操作

本文采用輪盤賭法對種群中染色體個體進行選擇。具體實現步驟如下。

步驟1：制作輪盤。根據式(12)～(14)計算種群中所有染色體的個體適應度f(x)、選擇概率px和累積概率wx。個體適應度越大，被選擇的概率越大。

(13)

式中，x,s分別為種群中第x,s個染色體。

(14)

步驟2：轉動輪盤。產生隨機數r1∈(0,1]。

步驟3：確定輪盤賭結果。依次判斷r1與wx的大小，當wx-1

步驟4：重復步驟2～步驟3，并保證迭代過程種群數量不變。

3.3.2 交叉操作

本文采用兩點交叉法進行交叉操作設計。為通過交叉操作增加種群多樣性的同時，保證交叉后的染色體序列仍滿足服裝綜合工序約束，具體實現步驟如下。

步驟1：首先選取種群內第s、(s+1)個染色體作為一對父代染色體。

步驟2：產生隨機數r2∈[0,1]，并判斷r2與交叉概率pc的大小。若r2

步驟3：交叉操作過程。隨機生成2個交叉點，如圖3所示。將父代P1除交叉片段以外的基因片段直接復制給子代C1，然后再將P1交叉片段基因編碼在父代P2中搜索出來，并按P2中基因順序賦給子代C1，一條符合工序約束的可行子代染色體便產生了。對于子代C2的產生過程同理。

圖3 交叉操作

3.3.3 變異操作

本文在變異操作設計中，采用單點變異法。為保證變異后的染色體序列仍為滿足服裝綜合工序約束的可行編碼序列，具體實現步驟如下。

步驟1：產生隨機數r3∈[0,1]，并判斷r3與變異概率pm的大小。若r3

步驟2：變異操作過程。如圖4所示，隨機產生變異點，變異點之前的染色體片段直接復制給子代，變異點后按照種群初始化的方法重新生成一段可行的染色體片段，一條新的子代染色體便產生了。

圖4 變異操作

步驟3：以上變異操作重復S次。

3.3.4 精英保留

本文為保證每代幾個較優解不被遺傳操作所破壞，對迭代進化過程新增一步精英保留操作。精英保留策略會將每代種群中幾個較優個體，即適應度最高的幾個可行染色體序列，直接復制到下一代種群，同時為保證種群總體數量不變，將經遺傳操作后產生的子代種群中適應度最差的相同數目個體刪除。

4 實例分析

4.1 遺傳參數設置

本文以某西服大規模定制生產企業為例進行實例分析。該企業生產車間混合生產線包括前片、過面、后片、領子、袖子、組裝共6組子生產線，保證物料在組內直線傳送，無組間交叉，總工序數達103道，單批次投產量最大為25，則以25件服裝產品為一個生產單元進行混合批量投產。

以前片子生產線為例，某生產單元內定制訂單信息如表1所示。綜合工藝信息如表2所示。將該實例中GA相關參數設置如下：目標函數權值分布為a=0.6、b=0.4，初始種群大小S=30，交叉概率Pc=0.8、變異概率Pm=0.3，迭代次數G=300。

表1 西服訂單信息表

根據GA算法特點，當G取值過大時，會降低運行速度，過小則無法收斂。本文G值是由具體生產數據多次試運行確定的合理值，運行結果是經G次迭代后保存下來的最優結果。表2中腰兜共包含5個定制選項，具體為：Y1表示直兜帶兜蓋；Y2表示直兜雙牙；Y3表示明貼兜；Y4表示斜兜帶兜蓋；Y5表示斜兜雙牙；胸兜共包含4個定制選項，具體為：X1表示直型；X2表示船型；X3表示明貼兜；X4表示獵裝口袋。

表2 西服綜合工藝信息表(前片組)

4.2 結果分析

由于各組子生產線工位數未知，在借助MatLab技術進行生產線平衡優化過程中，首先會基于“單工位包含工序數一般不大于4”這一編制原則確定前片組工位區間并進行試優化；然后結合人力成本、設備消耗成本等因素對表3中試優化結果進行綜合比較，認為K1=14時前片組優化結果最好。

表3 試優化結果(前片組)

另外，在試優化過程中發現，有些工序會因其綜合工時大于平均工位節拍影響到整體生產平衡，比如前片組工序3，本文會將其視為2個子工序(如表4中工序3-1、3-2)，默認這樣的工序可同時分配到2個工位，相應工時減半。對算法運行出的最優工序編制結果整理后，得前片組工序編制具體方案如表4所示。其他子生產線組同理。

表4 工序編制方案(前片組)

在保證各子生產線組內生產平衡的同時，還要考慮各生產線組之間平均工位節拍是否達到相對均衡。因此，在確定前片組平均節拍后，其他各組潛在工位數Ku分別由K′u進行四舍五入取整所得。

(15)

當Ku≤20時，子生產線u以工位區間[Ku-1，Ku+1]進行試優化，當Ku>20時，則以工位區間[Ku-2，Ku+2]進行試優化。

最終西服各組子生產線綜合最優工序編制效率匯總如表5所示。總生產線工位數為56，平均編制效率為85.77%，符合生產線編制要求。

表5 工序編制效率匯總

5 結束語

本文對更為復雜的具有工序約束的混合生產線平衡調度問題進行了深入探究并構建全新模型，該模型不僅適用于服裝大規模個性化定制，也適用于多品種小批量生產及單品種標準化生產，具有良好的兼容性。

本文完成了工位實際節拍最小化及平衡指數最小化多目標優化工作。同時，結合實際生產特點，建立了工序約束以保證染色體在迭代過程仍全部有效，提高了算法運算速度和較優解的搜索能力。

在服裝大規模定制生產線上，服裝種類和投產數量比例相對穩定為宜，服裝投產比例或種類發生較大變化時，工位分配方案應隨之做出相應調整。