陳 莎，修 毅，李雪飛

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

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

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

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

1 生產(chǎn)線平衡模型構(gòu)建

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

1)確定混合生產(chǎn)線。在某特定生產(chǎn)計劃期內(nèi)，根據(jù)單批次訂單內(nèi)服裝產(chǎn)品的工序約束關(guān)系將各訂單的服裝工藝生產(chǎn)線整合為混合生產(chǎn)線。

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

注：圈內(nèi)數(shù)字為工序編號；圈外數(shù)字為工序?qū)?yīng)的工時，單位為min。

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

(1)

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

其中，生產(chǎn)單元內(nèi)訂單數(shù)M和訂單內(nèi)服裝生產(chǎn)量qm的不同狀態(tài)可衍生出各種生產(chǎn)模式。比如：當(dāng)該生產(chǎn)單元包含訂單數(shù)M=Q，qm均為1，即為個性化定制；M

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

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

(2)

2 編碼與解碼設(shè)計

2.1 編碼設(shè)計

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

(3)

(4)

(5)

(6)

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

2.2 解碼設(shè)計

本文的解碼過程不僅是將編碼矩陣直譯為符合約束關(guān)系的工序順序，還需進(jìn)一步按工序順序?qū)⒎b工序分配到工位，得到具體工序編制方案。

根據(jù)GA的碼空間與問題的可行解空間的對應(yīng)關(guān)系，種群由S條染色體組成，每條染色體對應(yīng)一個可行解編碼。以1條可行染色體為例，具體實現(xiàn)步驟如下。

(7)

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

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

(8)

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

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

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

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

3 算法設(shè)計

在滿足服裝工序約束的情況下，同時考慮工位平順化和瓶頸節(jié)拍最小化2個優(yōu)化目標(biāo)，基于GA相關(guān)原理進(jìn)行算法設(shè)計?；究蚣苋鐖D2所示。

圖2 GA基本框架

3.1 種群初始設(shè)計

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

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

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

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

步驟4：再次轉(zhuǎn)入步驟2更新備選集合R，當(dāng)?shù)趕個染色體內(nèi)基因總數(shù)與服裝工序總數(shù)相同時，1條滿足工序約束關(guān)系的可行染色體生成。

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

3.2 適應(yīng)度函數(shù)設(shè)計

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

minC=min{maxTk}

(9)

(10)

F=aC+bF2

(11)

式中,a、b為目標(biāo)函數(shù)權(quán)值。

適應(yīng)度函數(shù)f通常是目標(biāo)函數(shù)F變換構(gòu)成，個體適應(yīng)度越高，基因越優(yōu)，被遺傳下來的概率也就越大。本文適應(yīng)度函數(shù)為

(12)

3.3 遺傳操作設(shè)計

3.3.1 選擇操作

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

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

(13)

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

(14)

步驟2：轉(zhuǎn)動輪盤。產(chǎn)生隨機數(shù)r1∈(0,1]。

步驟3：確定輪盤賭結(jié)果。依次判斷r1與wx的大小，當(dāng)wx-1

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

3.3.2 交叉操作

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

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

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

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

圖3 交叉操作

3.3.3 變異操作

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

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

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

圖4 變異操作

步驟3：以上變異操作重復(fù)S次。

3.3.4 精英保留

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

4 實例分析

4.1 遺傳參數(shù)設(shè)置

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

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

表1 西服訂單信息表

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

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

4.2 結(jié)果分析

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

表3 試優(yōu)化結(jié)果(前片組)

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

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

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

(15)

當(dāng)Ku≤20時，子生產(chǎn)線u以工位區(qū)間[Ku-1，Ku+1]進(jìn)行試優(yōu)化，當(dāng)Ku>20時，則以工位區(qū)間[Ku-2，Ku+2]進(jìn)行試優(yōu)化。

最終西服各組子生產(chǎn)線綜合最優(yōu)工序編制效率匯總?cè)绫?所示?？偵a(chǎn)線工位數(shù)為56，平均編制效率為85.77%，符合生產(chǎn)線編制要求。

表5 工序編制效率匯總

5 結(jié)束語

本文對更為復(fù)雜的具有工序約束的混合生產(chǎn)線平衡調(diào)度問題進(jìn)行了深入探究并構(gòu)建全新模型，該模型不僅適用于服裝大規(guī)模個性化定制，也適用于多品種小批量生產(chǎn)及單品種標(biāo)準(zhǔn)化生產(chǎn)，具有良好的兼容性。

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

在服裝大規(guī)模定制生產(chǎn)線上，服裝種類和投產(chǎn)數(shù)量比例相對穩(wěn)定為宜，服裝投產(chǎn)比例或種類發(fā)生較大變化時，工位分配方案應(yīng)隨之做出相應(yīng)調(diào)整。