襯衫吊掛流水線的自適應動態調度

謝子昂， 杜勁松,2， 趙國華

(1. 東華大學 服裝與藝術設計學院， 上海 200051； 2. 東華大學 現代服裝設計與技術教育部重點實驗室，上海 200051； 3. 報喜鳥控股股份有限公司， 浙江 溫州 325102)

由于服裝大規模個性化定制模式下的訂單到達時間、款式差異、插單返單等因素的影響，造成了生產調度的復雜性，因此企業有必要利用控制系統對生產線進行動態調度，確保生產的穩定性與連續性，提高生產調度的實時響應能力。

針對不確定條件下的車間動態調度問題，國內外學者提出了基于滾動時域的動態調度策略，通過對固定周期和事件驅動的重復調度，使生產線能夠不斷地根據車間實時情況進行調整[1-2]，并依托滾動調度的調度機制和調度算法研究來提高調度機動性[3-4]、減少重調度頻次[5]、提高設備利用率[6]。由于影響服裝生產效率的因素眾多，如服裝款式差異、加工設備差異、訂單批量差異[7]、人員技能差異等，使得目前訂單調度策略很難滿足服裝定制生產的需要。

本文針對襯衫定制的吊掛生產系統，利用吊掛流水線無物流浮余時間的特點，提出了適應吊掛生產方式的多目標自適應動態滾動調度模型，解決生產控制環節的不穩定問題。

1 生產動態調度模型

1.1 問題描述

1.1.1 調度問題描述

在服裝批量化定制生產過程中，服裝生產線調度的目標是將各工序分配至不同的加工工位上，其調度問題可以描述為：有n個訂單(J1,J2,…,Jn)在m臺設備(M1,M2,…,Mm)上加工，?Ji由加工順序已知的工序Oi={Oij,j∈(1,2,…,ni)}組成，訂單i的第j道工序可選設備集合為Mij?{1,2,…,M},(1≤i≤n,1≤j≤ni)。將所有工序Oij分配在設備Mk生產，其中1≤k≤m，以實現最優生產計劃安排目標。

1.1.2 生產不確定性描述

由于實際生產過程中訂單到達時間和款式要求不確定，導致了生產計劃的實時變更。其中，訂單到達時間t、工序內容O是影響生產調度安排的主要因素，因此任意訂單i可表示為二維變量(ti，Oi)。在生產排隊理論中，任意前后到達的訂單間隔服從參數λ的指數分布，其中λ為訂單的平均到達率，分布函數如下

F(t)=1-e-λt

(1)

假定第1個訂單到達時間t1=0，則第i個訂單到達時間ti為

(2)

1.2 動態模型構建

1.2.1 優化目標

本文研究以最后訂單完工的最小化時間f1和工位等待最小化時間f2作為優化目標，減少設備的閑置率。

f1=(maxCi|i=1,2,…,n)

(3)

(4)

式中：Ci為訂單i的完工時間；Ci(j-1)為訂單i的第j-1 道工序完工時間；Tijk為訂單i的第j道工序在設備k上的可加工時間。

1.2.2 約束條件

服裝訂單生產約束條件包括工序加工時間、訂單投放時間、工位選擇約束、人員技能水平：

(5)

Sijk≥ti,k∈Mij

(6)

(7)

Cijk=max{Ci(j-1)k,Tijk}+Pijkh,k∈Mij

(8)

Cijk≤Si(j+1)k,k∈Mij

(9)

式中：Pijkh為工序的加工時間約束；Pijk為訂單i第j道工序在設備k上加工時間；αh為不同技能等級的生產效率，人員技能等級為A、B、C，各等級生產效率比為αA∶αB∶αC=1.2∶1∶0.8；Xijk為訂單i第j道工序在設備k上加工的判別條件，當工序選擇設備k加工時候，則Xijk為1，反之為0；Sijk、Cijk分別為訂單i第j道工序在設備k上的實際開工時間和完工時間。公式(5)表示工序的實際加工時間受人員的生產效率影響，對于相同工序，高效員工的實際加工時間較短；公式(6)表示只有在用戶下單后才能對訂單投產；公式(7)表示一道工序只能在一臺設備上加工一次；公式(8)表示訂單的完工時間約束；公式(9) 表示訂單的加工順序約束。

除上述約束條件外，本文研究規定了如下假設：1臺機器只能加工1道工序；不同訂單的加工順序沒有先后約束等。

2 滾動調度策略

2.1 自適應滾動調度構建

服裝個性化訂單利用滾動調度可對服裝計劃排產過程進行多靜態區間劃分，隔離擾動因素帶來的負面影響，實現生產流水線暢通。滾動調度包括待加工工序集合Sa、正在加工工序集合Sw、已完工工序集合Sc等，并驅動窗口內各集合實時更新生產數據。窗口外未加工訂單集合Su記錄了動態到達的訂單信息，設備集合Sm記錄了所有設備的可用時間、工作狀態等。執行滾動調度的過程包括：1)在初始時刻從Su中取出未加工訂單，并拆分成工序放入Sa；2)經過Sm查詢各設備加工狀態，調用算法為Sa中的工序分配設備，若出現擾動事件則重復步驟1)；3)當到達重調度周期時，則清空Sc，重復步驟1)、2)。

由于不同訂單工藝要求不同，導致設備因換線產生調整時間，為了減少設備頻繁換線、設備待機過長現象，滾動調度窗口增加單次調度的訂單數量，提升調度性能[8]。當任意設備完工并能投入下周期生產時，生成自適應滾動調度窗口，此時待調度工序集合Sa包括了周期內積累的未加工訂單集Su所拆分出的工序和上一周期內未加工工序集合。滾動調度窗口在保證設備連續生產的同時，自動調整調度窗口大小，避免設備閑置對盡可能多的訂單進行調度。自適應動態調度流程如圖1所示。

圖1 滾動調度流程Fig.1 Rolling Scheduling flow chart

其中Tq為第q周期工件窗口Wq的生成時間；生產中，數據采集窗口持續采集訂單i的到達時間ti和對應的工序集合Oi；若ti1時)周期的未完工工序合與Owq合并生成待調度工序集合Sa，并依據設備集合Sm生成調度方案。當調度方案執行后若有設備加工完該周期的所有工序，并能立刻開始下一周期生產時，則生成下一周期的工件窗口進行調度。

2.2 非支配遺傳算法

調度過程中需要同時優化多個不可比較的目標函數，導致傳統目標線性加權的方法求解質量不高，目前常基于pareto支配關系對多目標問題進行求解，該方法能夠兼顧多個目標之間的均衡[9]，本文研究在遺傳算法基礎上采用pareto選擇機制對滾動窗口內的訂單工序進行調度。

2.2.1 編碼解碼

染色體采用工序鏈/機器鏈的二層編碼結構，每層染色體的長度實時調整，即為本次調度的工序數量。第1層為工序編碼，染色體中的基因代表對應訂單在該滾動調度窗口內的編號，數字出現的次數代表對應工序序號。第2層為對應工序所選擇的設備，工序必須滿足可選設備約束。

2.2.2 交叉變異

在染色體交叉過程中，工序鏈需要滿足訂單工序數量的約束，即子代C相同基因的數量與父代P相同，因此為滿足交叉的合法性，本文采用基于工件的POX(precedence operation crossover)交叉方法，交叉過程如圖2所示。

圖2 POX交叉示意圖Fig.2 Diagram of POX

首先隨機選擇2個非空子集J1、J2，存儲工件編號，將P1中對應J1的工件序列復制到C1中，剩余位置的染色體由P2中對應J2的工件填充得到完整的C1；C2則與C1相反，由P2中對應J1的工件序列復制到C2中，剩余位置的染色體由P1中對應J2的工件填充得到完整的C1。

機器鏈必須滿足工序的可選設備約束，采用MPX(multi-point preservative crossover)的多點交叉方法，如圖3所示。

圖3 MPX交叉示意圖Fig.3 Diagram of MPX

首先隨機生成1條與機器鏈等長的0、1序列Rand，然后將P1、P2中在Rand=1的位置交換基因得到C1、C2。工序鏈采用2點變異的方式，在染色體上隨機選擇連續的2道工序，對應基因進行交換完成變異；機器鏈通過隨機選擇1道工序，并選擇其中1個可加工該工序的設備作為替換完成變異操作。

2.2.3 選擇操作

Pareto支配關系的選擇機制是解決多目標優化問題的常用方法，對于n(n>1)個目標的F=(fk|k=1，…，n)，任意染色體i、j，若對?k有fk(i)≤fk(j)，且?fk(i)

3 實例仿真

3.1 參數設置

襯衫吊掛生產線人數為13人，1人1工位，每個工位上安置1臺或2臺設備。根據襯衫各工藝加工的時間比設置設備16臺，其中平縫機、燙臺、五線車、鏈式機、鎖眼機、釘扣機的配置比例為7∶4∶2∶1∶1∶1。設定訂單的平均到達率設定為90 s，產前到達訂單數量為60個。

襯衫可定制的款式為8種，襯衫款式的配置設計部件包括2種領型、2種貼袋型、2種克夫。各款式的加工時間如表1所示。

表1 不同款式加工時間Tab.1 Procedure process time of different styles

圖4示出吊掛生產流水線示意圖，圖中w1～w13代表工位編號，工位內的人員等級(A、B、C3個等級)和設備配置均有顯示。A級人員完成復雜的縫制工序；B級人員完成較復雜的縫制工序；C級人員只能完成簡單工序，如小燙等。

圖4 服裝吊掛產線布局Fig.4 Hanging production line layout

為提高求解的效率，盡量保證種群規模與最大迭代數的最大化，設定種群規模N=100，最大迭代數為500代，交叉率Pc=0.8，變異率Pm=0.02，交叉率Pc∈ (0.4，0.9)，變異率Pm∈(0.005，0.1)[10]。

3.2 仿真結果分析

仿真實驗分為固定周期調度和自適應滾動調度2種方案。固定調度周期設置一般根據企業生產條件而定，通常固定調度周期越小，設備閑置時間就越少，但生產線的快速反應效率會下降，而固定調度周期越大，會提升生產線的在制品率和調度的復雜性。自適應滾動調度是通過尋找生產前端工序設備的閑置時刻，自行判斷調度周期窗口，實現生產線的自適應性。

生產前已到達訂單數量為60件，根據上文的約束條件公式(1)～(9)進行計劃排產仿真。如圖5所示，圖中1#～8#分別代表款式1#-8#的款式編號，粗實線為生產前端工序出現閑置設備的時刻4 558 s，即為自適應滾動調度窗口位置。本實驗設定固定調度周期分別為3 600、7 200 s，如圖中虛線所示。固定調度周期為3 600 s的第1次滾動調度結果如圖6所示。自適應滾動調度的第1個周期如圖7所示。圖6、圖7的款式編號與圖5一致。

圖5 調度前計劃排產方案Fig.5 Advanced scheduling sequence

圖6 T=3 600 s的第1次滾動調度Fig.6 First rescheduling cycle under rolling scheduling of T=3 600 s

圖7 自適應第1次滾動調度Fig.7 The first rescheduling cycle of adaptive rolling schedule

實驗結果表明，完成288件襯衫所需要的生產時間和設備利用率分別為：固定調度周期(T=3 600 s)

為26124和63%；固定調度周期(T=7 200 s) 為32 104 s和57.8%；自適應調度為24 894 s 和67%。

4 結束語

基于多目標動態調度算法的自適應滾動窗口能夠解決現有服裝大規模定制生產的自主適應性能差的問題。針對實時性的訂單導入，自適應滾動調度窗口機制利用現有生產條件進行實時生產排程，最大限度地提高設備的使用率，實現生產線的效率提升。實驗表明自適應滾動調度相對固定周期調度(T=3 600 s)的完工時間減少4.9%，設備等待時間減少18.2%。