采用主目標進化遺傳算法的織造排程研究

孟 朔， 潘如如， 高衛東， 王靜安， 周利軍

(1. 生態紡織教育部重點實驗室(江南大學)， 江蘇 無錫 214122；2. 丹陽市丹盛紡織有限公司， 江蘇 鎮江 212309)

織造作為紡織企業生產的核心工序，決定了企業的生產效益，而目前個性化的產品需求使紡織企業存在訂單多、批量小、品種雜、交期要求嚴格的問題。當前人工排程不僅會引起訂單超期，品種翻改次數增多，還會增加計劃工人的勞動強度，降低車間生產效率，因此，合理高效的計算機排程方法成為企業關注的焦點。Abedinnia等[1]總結了車間調度問題的相關智能算法。鄒澤樺等[2]使用改進遺傳算法來解決車間多目標調度問題，取得了較優效果。

盡管調度問題在各領域也都有研究應用，但在紡織領域并針對織造環節的研究仍較少。文獻[3]提出使用簡單遺傳算法對織造問題進行建模求解，雖取得了一定成果，但對多個優化目標使用線性加權計算適應度，具有一定局限性，且未考慮織機約束。韓江洪等[4]采用的基于Petri網的建模方法理論嚴密，圖形表達直觀，但同樣存在模型復雜，計算效率低的問題。EROGLU等[5]同時考慮了織機約束與訂單分割，但當解決大規模織機調度問題時運算時間較長，且為單目標優化。

本文研究立足于工廠的實際生產，在現有研究的基礎上從多目標與單目標轉化角度出發，提出用主目標進化遺傳算法來解決織造排程問題，并以某織造車間生產實例進行了仿真實驗。

1 織造生產排程模型

1.1 問題描述

在企業，織造車間擁有多臺不同類型的織機，其生產進度各不相同，需要對多個訂單的多個小批量品種進行排程，以安排織造生產，提高企業效益。

已知某時刻下的織機、織造、品種與訂單等信息，在企業實際排程中，通常以滿足訂單交期為主來盡量提高生產效益，主要體現在：提高織機利用率，減少空車數與品種翻改次數，并且當訂單交期較長時盡可能使用較少的織機來完成生產以降低庫存成本，便于安排其他訂單；同時由于訂單批量小，生產周期相對較短，一般不會調整其他訂單完工時間來保證緊急單的生產。

基于企業實際排程需求，為簡化計算復雜度，本文忽略人工、生產管理、緊急插單等，假設織軸的上機時間均為T，織機均服從經驗數據進行生產。算法通過對訂單分軸，滿足織機可織品種約束，優化實現多個目標要求。另外，每當出現插單、停單、機臺故障或者偏離實際計劃較大時，算法會對所有未實際安排的訂單重新排程，尋求更優計劃來指導生產。

1.2 優化目標

織造企業調度計劃的目標主要體現在按時交貨、降低成本與提高織機利用率，結合企業實際需求，設立如下目標函數：

f1=max(T1,T2,···,Tm)

f2=sum(Dt

f3=sum(M0)

目前，人力資源管理信息化軟件產品的規則與質量，在社會市場上的標準還不統一，產品還不規范，銷售廠商較為混雜，這些問題都在一定程度上制約著人力資源管理的信息化發展。

f4=sum(Pk≠Pk+1)

f5=3n-(3sum(S3)+2sum(S2)+sum(S1))

f6=Q1+Q2+···+Qr

式中：f1為最大完工時間，其取值范圍為[Tc,T1+T2+ …+Tm]，Tc為當前時間；max表示取最大值；Ti為第i臺織機的完工時間(i=1,2,3,...,m，其中m為織機總數)，完工時間包含織機在織織軸的剩余時間及待安排織軸織造的總時間；f2為訂單超期總數,其取值范圍為[0,r]；sum表示求總數；Dt為第t個訂單截至日期；Ot為第t個訂單完成時間(t=1,2,3，...，r，其中r為訂單數量)；f3為空車總數，取值范圍為[0,m]；M0為機臺空車數；f4為品種翻改總數，取值范圍為[0,n]，n為織軸總數；Pk表示當前織機第k個織軸的織造品種；f5為機型不合適度，其取值范圍為[0,3n]；S3表示合適度系數為3的當前織機織造最合適品種；S2表示合適度系數為2的當前織機織造較合適品種；S1表示合適度系數為1的當前織機可織造品種；若不可以使用當前織機織造此品種，則合適度系數為0；f6為訂單占用織機總次數，取值范圍為[0,mr]；Qr為第r個訂單使用的織機次數(j=1,2,3,…，r，)。

訂單占用較少的織機數可減少品種翻改，符合企業的實際生產需要，但會導致完工時間的增加，各目標之間具有一定的矛盾關系，故此問題屬于多目標優化問題。而實際的織造排程是以滿足訂單交期為首要條件，來盡量優化其他目標。

1.3 約束條件

1.3.1 機型約束

織造企業中不同類型的織機適用于不同的品種，并具有一定的交叉性。表1示出某織造企業不同類型織機的品種適應情況。

表1 不同織機的品種適應情況Tab.1 Suitable varieties for different machines

1.3.2 織軸長度約束

織造排程的基本依據是織造時間，織軸的織造時間計算公式如下式所示。本文按照實際工藝計算織軸長度，同時決策者可修改織軸的數量及長度。

式中：Tr為預計織造時間，h；Pw為品種緯密，根/(10 cm)；Lo為織軸上經紗長度，m；j為經紗織縮率；L為織軸回絲長度,m；Ms為織機車速，r/min；η為織造效率，%。

2 主目標進化遺傳算法

帶精英選擇策略的快速非支配遺傳算法(NSGA-II)是目前常用的多目標優化算法之一，具有較好的魯棒性，常用來解決多目標條件下的優選問題[6]。傳統的NSGA-II對多個目標同時優化，無主次之分[7-8]，本文對此算法加以改進，設計了 1種主目標進化的遺傳算法。

2.1 編 碼

染色體通例如圖 1(a)所示。染色體的總長為織軸總數N，每個基因C的位置對應一個織軸，按照織軸的品種依次表示復雜品種、普通品種、高速品種的織軸。基因C取值都是一個大于等于0的實數(小數位不做限制，圖中只是為顯示需要)，C的整數部分表示的是對應織軸的待上機編號。織機編號n為從0開始遞增的整數，n∈[0,Md)代表多臂織機(Md為多臂織機數)，n∈[Md,Md+Mt)代表踏盤織機(Mt為踏盤織機數)，n∈[Md+Mt,Md+Mt+Me)代表電子織機(Me為電子織機數)。當若干基因的整數部分相同時，對應織軸均使用同一臺織機織造，小數部分決定其上機次序，小數部分小的先上機織造。基因C的取值范圍由該織軸的適應機型來確定，如復雜品種織軸只可用多臂織機織造，其基因C取值范圍即為[0,Md)；普通品種織軸，既可用踏盤織機織造，也可用多臂織機織造，其取值范圍即為[0,Md+Mt)；高速品種織軸，可使用所有機型織造，故其取值范圍為[0,Md+Mt+Me)。

圖1 染色體編碼通例與實例Fig.1 General chromosome encoding case(a) and example(b)

本文模型對于織機和織軸的數目沒有限制：當織機數變化時，算法可自動根據數據庫織機信息，調整相應基因的取值范圍；當織軸數變化時，算法可自動根據數據庫織軸信息，在染色體對應位置上插入或刪除相應織軸，改變染色體的長度，因此，此染色體編碼模型具有較強的適應性，滿足了品種與織機類型匹配的約束，并可表示織軸的所上織機及上機次序。

本文以一個有5臺織機的車間、10個待上機織軸的排程問題為例，介紹編碼規則。上述10個織軸包含2個復雜品種織軸，3個普通品種織軸，5個高速品種織軸。上述5臺織機均參與織造過程，其中包含1臺電子織機，2臺多臂織機，2臺踏盤織機。此問題對應的一條染色體示例如圖1(b)所示。此染色體表示的含義即為：0號多臂織機織造F2號織軸；1號多臂織機依次織造F1、G3、P1號織軸；2號踏盤織機依次織造P3、G2、P2號織軸；3號踏盤織機織造G4號織軸；4號電子織機依次織造G1、G5號織軸。

2.2 種群適應度評價

使用傳統NSGA-Ⅱ方法中的快速非支配算法與擁擠度算法來比較不同個體的Pareto支配關系與個體擁擠度，實現對種群進行適應度排序[7]。針對此問題，對于任意的個體解i，其目標函數值分別為f1(i)，f2(i)，…，f6(i)。若對于任意p∈(1,2,3,4,5,6)均有fp(i)≤fp(j)，且存在fp(i)

2.3 選擇交叉變異

由于個體之間的適應度值并不是線性關系，因此，采用一種常用的二元錦標賽選擇算法。其主要步驟即隨機從種群中選擇2個個體進入錦標賽，然后按照非支配關系選擇適應度最高的個體。

考慮到織軸的安排具有離散性，不受染色體中基因片段位置的影響，對染色體基因順序要求不高，故分別選擇隨機個數和位置進行交叉與變異操作，其過程示例如圖 2所示。主要步驟即在染色體長度范圍內生成隨機個數的交叉變異位置，每個交叉變異位置也隨機選定，以Pc的交叉率和Pm的變異率分別進行交叉和變異。

圖2 交叉變異示意圖Fig.2 Crossover and mutation operations

2.4 主目標進化

當應用傳統的NSGA-Ⅱ算法時，會對所有的目標同時進行優化，往往會產生訂單超期的方案，對于實際織造生產而言，所有的其他目標都是建立在滿足交期f2=0的基礎上的，一旦存在訂單超期，該排程方案即不理想。

基于此，本文將傳統的NSGA-Ⅱ算法加以改進，以最小化訂單超期數為主目標進行單目標遺傳算法進化，當無訂單超期后，變為以最小化品種翻改數、空車數、完工時間、訂單占用織機次數、機型不匹配度的多目標優化問題。若進化到達設定迭代次數始終存在訂單超期時，反饋決策者修改織軸長度或由算法增加織軸數來繼續排程。若再次迭代到最終設定次數仍出現訂單超期時，說明該訂單無法按時交期，算法會直接進行多目標優化，生成最終方案。整個算法的流程如圖 3所示。

圖3 主目標進化算法(改進NSGA-II)Fig.3 Main objective evolution (improved NSGA-II)

3 實驗與討論

3.1 應用實例

本文以某車間的實際生產情況為例，取工廠的實際訂單數據以及織造生產信息，在某一時刻下共擁有60個訂單，316個織軸。

本算法使用Java語言編程，并在頻率為3.6 Hz的AMD R5-1600X處理器的計算機上運行，對最后排程方案的染色體進行解碼，其部分排程甘特圖如圖4所示。

圖4 部分排程甘特圖Fig.4 Part of Gantt chart

當應用本文設立的目標函數，各遺傳參數取值分別為：交叉率Pc=0.8，變異率Pm=0.01，種群規模N=100，進化代數G=1 000時，采用本文提出的主目標進化遺傳算法與普通NSGA-II算法，同時使用工廠的實際排程數據，3種方法目標函數值結果對比如圖 5所示。

圖5 不同方法的排程效果對比Fig.5 Comparison of different algorithm scheduling of manual scheduling

由圖5結果顯示，本文算法相較于人工排程，完工時間縮短4.51%，品種翻改減少13.17%，訂單占用織機數減少10.65%，空車數減少40%，機型合適度得分提高23.57%，各目標函數評價效果平均提升了15.32%。而普通NSGA-II算法也能取得較好的效果，但由于其各目標權重是相同的，會出現訂單超期現象，魯棒性較低。

應用此主目標進化遺傳算法：當處理316個織軸，209臺織機，經過一次算法，計算時間用時僅為212 s；而當處理403個織軸時用時為323 s。可以看出，本文采用簡化模型，尋求相對最優解，具有較高的運算效率。

3.2 參數討論

遺傳算子參數的選擇會影響算法的運行效率，此算法的控制參數主要有交叉率Pc，變異率Pm，若選擇固定的Pc、Pm，易使算法陷入局部最優或者出現早熟現象，因此，常采用自適應方法來提高算法的局部和全局尋優能力[9]，而傳統的自適應策略依賴于種群的適應度值，對于多目標而言，其適應度值是根據非支配排序得出的，不同代種群適應度值之間不具有可比性，故本文采用了一種動態調整Pc、Pm的方法，自適應Pc、Pm的計算公式如下：

式中：Pm(g)與Pc(g)分別為第g代變異概率和交叉概率；Pcmin與Pcmax分別為最小和最大交叉概率；Pmmin與Pmmax分別為最小和最大變異概率； G為最大進化代數。

應用此公式后使得算法在初期擁有較大的Pc、Pm，隨著進化代數的增加，Pc、Pm逐漸減小，從而使得算法可在運行初期擁有較高的種群多樣性，在后期利于保留最佳個體而進行細致搜索。當使用Pc=0.8、Pm=0.01時，算法各目標函數值經歸一化，并映射到0～100范圍內的函數值隨進化代數的收斂曲線如圖6 (a)所示，圖中所示數值為最終代數的適應度函數值。而使用自適應Pc、Pm后，對于Pc、Pm最大、最小值在一般推薦范圍中取值[10]，Pcmin=0.4，Pcmax=0.99，Pmmin=0.001，Pmmax=0.1，優化后目標函數的收斂曲線如圖6 (b)所示。

圖6 主目標進化遺傳算法與采用自適應后的收斂曲線對比Fig.6 Comparision of convergence curves of main objective evolutionary genetic algorithm (a) and using adaptive methodhm (b)

對比圖6(a)、(b)可知，優化前后算法均在前期朝著訂單超期數為0的方向快速收斂。優化前算法在70代左右訂單超期數即可變為0，但隨著種群的不斷進化，其他目標函數值的進化卻較為緩慢，而且算法會出現訂單超期數大于0而無法收斂的現象，原因是由于算法早熟，使種群多樣性降低，進化能力喪失。當使用自適應方法進行優化后，算法在80代左右開始收斂，并且在進化后期存在著多次進一步尋優的過程：表明了使用自適應方法后算法可提高全局搜索能力，在一定程度上避免早熟現象；另一方面，應用此自適應的多目標優化方法避免了由于遺傳參數的選擇對算法效果的影響，且對算法運行效率并無較大影響。

應用自適應遺傳參數，對算法進一步優化后，按照支配關系取最優個體，其各目標的函數值為：[36.34, 0, 276, 5, 269, 567]。相較于使用固定的Pc、Pm，完工時間縮短0.06%，品種翻改減少1.51%，訂單占用織機數減少1.43%，空車數減少50%，但機型合適度得分降低了1.42%。總體而言應用自適應遺傳參數后算法的魯棒性進一步提高，并可應用于實際排程計劃中。

4 結束語

本文為解決目前多品種織造時的調度問題，建立了一個具有3種類型織機的并行生產環境模型，簡化了實際生產中織機類型約束的復雜性，并設計改進了一種主目標進化的遺傳算法。結果表明，本文提出的方法相較于人工方法排程具有很大的優勢，且計算時間較快，能夠指導實際生產排程。

在實際生產中，還需要考慮人員配備、生產管理、緊急插單等問題，導致實際約束會更為復雜，如何完善算法模型以及建立實用性強的織造排程系統是進一步的研究方向。

FZXB