采用主目標(biāo)進(jìn)化遺傳算法的織造排程研究

孟 朔， 潘如如， 高衛(wèi)東， 王靜安， 周利軍

(1. 生態(tài)紡織教育部重點(diǎn)實(shí)驗(yàn)室(江南大學(xué))， 江蘇 無錫 214122；2. 丹陽市丹盛紡織有限公司， 江蘇 鎮(zhèn)江 212309)

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

盡管調(diào)度問題在各領(lǐng)域也都有研究應(yīng)用，但在紡織領(lǐng)域并針對(duì)織造環(huán)節(jié)的研究仍較少。文獻(xiàn)[3]提出使用簡單遺傳算法對(duì)織造問題進(jìn)行建模求解，雖取得了一定成果，但對(duì)多個(gè)優(yōu)化目標(biāo)使用線性加權(quán)計(jì)算適應(yīng)度，具有一定局限性，且未考慮織機(jī)約束。韓江洪等[4]采用的基于Petri網(wǎng)的建模方法理論嚴(yán)密，圖形表達(dá)直觀，但同樣存在模型復(fù)雜，計(jì)算效率低的問題。EROGLU等[5]同時(shí)考慮了織機(jī)約束與訂單分割，但當(dāng)解決大規(guī)模織機(jī)調(diào)度問題時(shí)運(yùn)算時(shí)間較長，且為單目標(biāo)優(yōu)化。

本文研究立足于工廠的實(shí)際生產(chǎn)，在現(xiàn)有研究的基礎(chǔ)上從多目標(biāo)與單目標(biāo)轉(zhuǎn)化角度出發(fā)，提出用主目標(biāo)進(jìn)化遺傳算法來解決織造排程問題，并以某織造車間生產(chǎn)實(shí)例進(jìn)行了仿真實(shí)驗(yàn)。

1 織造生產(chǎn)排程模型

1.1 問題描述

在企業(yè)，織造車間擁有多臺(tái)不同類型的織機(jī)，其生產(chǎn)進(jìn)度各不相同，需要對(duì)多個(gè)訂單的多個(gè)小批量品種進(jìn)行排程，以安排織造生產(chǎn)，提高企業(yè)效益。

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

基于企業(yè)實(shí)際排程需求，為簡化計(jì)算復(fù)雜度，本文忽略人工、生產(chǎn)管理、緊急插單等，假設(shè)織軸的上機(jī)時(shí)間均為T，織機(jī)均服從經(jīng)驗(yàn)數(shù)據(jù)進(jìn)行生產(chǎn)。算法通過對(duì)訂單分軸，滿足織機(jī)可織品種約束，優(yōu)化實(shí)現(xiàn)多個(gè)目標(biāo)要求。另外，每當(dāng)出現(xiàn)插單、停單、機(jī)臺(tái)故障或者偏離實(shí)際計(jì)劃較大時(shí)，算法會(huì)對(duì)所有未實(shí)際安排的訂單重新排程，尋求更優(yōu)計(jì)劃來指導(dǎo)生產(chǎn)。

1.2 優(yōu)化目標(biāo)

織造企業(yè)調(diào)度計(jì)劃的目標(biāo)主要體現(xiàn)在按時(shí)交貨、降低成本與提高織機(jī)利用率，結(jié)合企業(yè)實(shí)際需求，設(shè)立如下目標(biāo)函數(shù)：

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

f2=sum(Dt

f3=sum(M0)

目前，人力資源管理信息化軟件產(chǎn)品的規(guī)則與質(zhì)量，在社會(huì)市場上的標(biāo)準(zhǔn)還不統(tǒng)一，產(chǎn)品還不規(guī)范，銷售廠商較為混雜，這些問題都在一定程度上制約著人力資源管理的信息化發(fā)展。

f4=sum(Pk≠Pk+1)

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

f6=Q1+Q2+···+Qr

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

訂單占用較少的織機(jī)數(shù)可減少品種翻改，符合企業(yè)的實(shí)際生產(chǎn)需要，但會(huì)導(dǎo)致完工時(shí)間的增加，各目標(biāo)之間具有一定的矛盾關(guān)系，故此問題屬于多目標(biāo)優(yōu)化問題。而實(shí)際的織造排程是以滿足訂單交期為首要條件，來盡量優(yōu)化其他目標(biāo)。

1.3 約束條件

1.3.1 機(jī)型約束

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

表1 不同織機(jī)的品種適應(yīng)情況Tab.1 Suitable varieties for different machines

1.3.2 織軸長度約束

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

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

2 主目標(biāo)進(jìn)化遺傳算法

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

2.1 編 碼

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

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

本文模型對(duì)于織機(jī)和織軸的數(shù)目沒有限制：當(dāng)織機(jī)數(shù)變化時(shí)，算法可自動(dòng)根據(jù)數(shù)據(jù)庫織機(jī)信息，調(diào)整相應(yīng)基因的取值范圍；當(dāng)織軸數(shù)變化時(shí)，算法可自動(dòng)根據(jù)數(shù)據(jù)庫織軸信息，在染色體對(duì)應(yīng)位置上插入或刪除相應(yīng)織軸，改變?nèi)旧w的長度，因此，此染色體編碼模型具有較強(qiáng)的適應(yīng)性，滿足了品種與織機(jī)類型匹配的約束，并可表示織軸的所上織機(jī)及上機(jī)次序。

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

2.2 種群適應(yīng)度評(píng)價(jià)

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

2.3 選擇交叉變異

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

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

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

2.4 主目標(biāo)進(jìn)化

當(dāng)應(yīng)用傳統(tǒng)的NSGA-Ⅱ算法時(shí)，會(huì)對(duì)所有的目標(biāo)同時(shí)進(jìn)行優(yōu)化，往往會(huì)產(chǎn)生訂單超期的方案，對(duì)于實(shí)際織造生產(chǎn)而言，所有的其他目標(biāo)都是建立在滿足交期f2=0的基礎(chǔ)上的，一旦存在訂單超期，該排程方案即不理想。

基于此，本文將傳統(tǒng)的NSGA-Ⅱ算法加以改進(jìn)，以最小化訂單超期數(shù)為主目標(biāo)進(jìn)行單目標(biāo)遺傳算法進(jìn)化，當(dāng)無訂單超期后，變?yōu)橐宰钚』贩N翻改數(shù)、空車數(shù)、完工時(shí)間、訂單占用織機(jī)次數(shù)、機(jī)型不匹配度的多目標(biāo)優(yōu)化問題。若進(jìn)化到達(dá)設(shè)定迭代次數(shù)始終存在訂單超期時(shí)，反饋決策者修改織軸長度或由算法增加織軸數(shù)來繼續(xù)排程。若再次迭代到最終設(shè)定次數(shù)仍出現(xiàn)訂單超期時(shí)，說明該訂單無法按時(shí)交期，算法會(huì)直接進(jìn)行多目標(biāo)優(yōu)化，生成最終方案。整個(gè)算法的流程如圖 3所示。

圖3 主目標(biāo)進(jìn)化算法(改進(jìn)NSGA-II)Fig.3 Main objective evolution (improved NSGA-II)

3 實(shí)驗(yàn)與討論

3.1 應(yīng)用實(shí)例

本文以某車間的實(shí)際生產(chǎn)情況為例，取工廠的實(shí)際訂單數(shù)據(jù)以及織造生產(chǎn)信息，在某一時(shí)刻下共擁有60個(gè)訂單，316個(gè)織軸。

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

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

當(dāng)應(yīng)用本文設(shè)立的目標(biāo)函數(shù)，各遺傳參數(shù)取值分別為：交叉率Pc=0.8，變異率Pm=0.01，種群規(guī)模N=100，進(jìn)化代數(shù)G=1 000時(shí)，采用本文提出的主目標(biāo)進(jìn)化遺傳算法與普通NSGA-II算法，同時(shí)使用工廠的實(shí)際排程數(shù)據(jù)，3種方法目標(biāo)函數(shù)值結(jié)果對(duì)比如圖 5所示。

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

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

應(yīng)用此主目標(biāo)進(jìn)化遺傳算法：當(dāng)處理316個(gè)織軸，209臺(tái)織機(jī)，經(jīng)過一次算法，計(jì)算時(shí)間用時(shí)僅為212 s；而當(dāng)處理403個(gè)織軸時(shí)用時(shí)為323 s?？梢钥闯?，本文采用簡化模型，尋求相對(duì)最優(yōu)解，具有較高的運(yùn)算效率。

3.2 參數(shù)討論

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

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

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

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

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

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

4 結(jié)束語

本文為解決目前多品種織造時(shí)的調(diào)度問題，建立了一個(gè)具有3種類型織機(jī)的并行生產(chǎn)環(huán)境模型，簡化了實(shí)際生產(chǎn)中織機(jī)類型約束的復(fù)雜性，并設(shè)計(jì)改進(jìn)了一種主目標(biāo)進(jìn)化的遺傳算法。結(jié)果表明，本文提出的方法相較于人工方法排程具有很大的優(yōu)勢，且計(jì)算時(shí)間較快，能夠指導(dǎo)實(shí)際生產(chǎn)排程。

在實(shí)際生產(chǎn)中，還需要考慮人員配備、生產(chǎn)管理、緊急插單等問題，導(dǎo)致實(shí)際約束會(huì)更為復(fù)雜，如何完善算法模型以及建立實(shí)用性強(qiáng)的織造排程系統(tǒng)是進(jìn)一步的研究方向。

FZXB