沈春婭， 雷鈞杰， 汝 欣， 彭來湖， 胡旭東

(1. 浙江理工大學 機械與自動控制學院， 浙江 杭州 310018； 2. 浙江理工大學 浙江省現(xiàn)代紡織裝備技術重點實驗室， 浙江 杭州 310018)

《紡織工業(yè)發(fā)展規(guī)劃(2016—2020年)》[1]規(guī)劃中明確指出要推進紡織智能制造，建設紡織強國。在智能制造大背景下，我國紡織業(yè)雖然近幾年技術進步迅速，但仍屬于勞動密集型產業(yè)，人力資源成本占比高；同時生產工藝繁雜，品種多樣，對生產柔性要求高。紡織業(yè)實現(xiàn)智能化生產轉型意義重大[1]，智能調度在生產過程智能化中具有核心決策功能，是實現(xiàn)紡織智能制造的重要環(huán)節(jié)。

紡織織造的關鍵環(huán)節(jié)是將織軸上的經(jīng)紗加工為布匹，過程中涉及穿經(jīng)、織造，每道工序內的設備都為并行機，穿經(jīng)雖然先于織造，但是織軸是否需要穿經(jīng)卻取決于織造中選擇生產的織機，因此，這是一種混合流水車間逆工序調度問題(HFSPI)。HFSPI多目標優(yōu)化是一類NP-hard難題，已有研究中通過將最早完工時間最小、總拖期時間最小、能耗最小、機器效率最大等目標相互組合，形成了不同的多目標問題模型。對此已有較多智能優(yōu)化算法的研究，如三級遞階結構的蟻群算法[2]、模擬退火遺傳算法[3]、一種改進的緊致遺傳算法與局部指派規(guī)則結合的方法[4]、NSGAII_3[5]、EA-MOA[6]、一種帶精英策略的多目標免疫克隆選擇算法[7]等，但對HFSPI多目標優(yōu)化的研究較少。

織造調度除考慮織造和穿經(jīng)之間獨特的工序關系、工藝的復雜和資源約束帶來的調度困難外，還需考慮其多織機、多織軸、多產品形成的大規(guī)模調度問題。對大規(guī)模調度，一些學者利用啟發(fā)規(guī)則縮小解空間，或通過貪婪變異算子[5]、多種群進化等方法提高算法搜索的深度和廣度，但已有最大仿真規(guī)模也無法滿足普遍調度規(guī)模在300臺織機、1 000個織軸的中小型織造企業(yè)的需求。

實際織造生產調度過程中存在多源隨機動態(tài)擾動，易使生產偏離原有計劃，甚至原有計劃失效，靜態(tài)調度并不適用。動態(tài)調度一般根據(jù)工件(或任務)實時所處的加工階段為其分類[8-9]，然后確定可以被重新調度的工件。動態(tài)調度機制主要有事件驅動、周期性驅動及混合驅動[10]，但這些調度機制可適應的場景有限，無法應對復雜的織造生產現(xiàn)場。

目前，針對織造車間這種大規(guī)模多目標的HFSPI研究較少，雖有學者研究過織造的織軸調度，但是只考慮了織造工序，并未考慮穿經(jīng)與織造間的雙向約束關系，且實驗調度規(guī)模也未達到普通生產規(guī)模。鑒于此，本文從織造大規(guī)模調度出發(fā)，研究織造和穿經(jīng)之間獨特的逆工序調度關系，構建織造大規(guī)模多目標排產模型，提出一種融合改進優(yōu)先分配規(guī)則、自適應貪婪算子的NSGAII織造車間動態(tài)調度算法，以期解決傳統(tǒng)動態(tài)調度機制在織造插單、打樣等復雜生產場景中適應性不強的問題。

1 問題描述及建模

1.1 問題描述

織造車間的生產流程如圖1所示。織造車間輸入原料是織軸，輸出產品為布匹。生產涉及設備包括織機、穿經(jīng)機和結經(jīng)機，工序包括穿經(jīng)、結經(jīng)、換軸和織造。

圖1 織造車間工藝流程Fig.1 Process flow of weaving workshop

按照工序流程進入織造車間的織軸，若需穿經(jīng)就必先占有一定數(shù)量的鋼筘，并選擇一臺穿經(jīng)機進行穿經(jīng)，最后選擇一臺織機完成換軸和織造，若不需穿經(jīng)，則選擇一臺織機完成結經(jīng)和織造。結經(jīng)機數(shù)量充足，其可能帶來的約束本文不予考慮。

雖然穿經(jīng)工序在織造工序的前面，但是否需要穿經(jīng)取決于織軸織造時織機的選擇，若織軸與織機上織軸不屬于同一品種，即不滿足結經(jīng)的工藝要求，就必須先完成穿經(jīng)工序，反之可以選擇相對簡單快捷的結經(jīng)工序；工藝上由于織造過程中有的經(jīng)紗會隨機變換位置，同一織機連續(xù)多次結經(jīng)會使經(jīng)紗相互扭絞，另外綜、筘、經(jīng)停片也需要修理或更換，因此，一般3次結經(jīng)后改用一次穿經(jīng)的工藝解決此問題[11]，即同一臺織機連續(xù)3次結經(jīng)后必須穿插穿經(jīng)工序。同時鋼筘的數(shù)量有限，直接約束穿經(jīng)的進行，進而影響織造。綜上可見，織造車間的調度問題相比其他行業(yè)要更加復雜，既需要考慮織造和穿經(jīng)之間獨特的工序關系，還要時刻關注鋼筘資源帶來的約束，所以織造車間的調度問題是帶有資源約束的HFSPI。

織造車間除工序間的特殊關系、工藝的復雜和資源約束帶來的調度困難之外，織造行業(yè)多設備、多任務形成的調度規(guī)模之大也要遠遠超過其他行業(yè)，增加了調度難度。

1.2 基本定義與假設

為量化織造車間調度中的各類因素，簡化車間內任務、機器和資源的調度，本文做出以下合理的定義與假設。

1) 有n個相互獨立的織軸，單個織軸不再拆分，織軸編號i= 1，2，…，n；織軸具有所屬訂單、品種、繞長、經(jīng)紗根數(shù)等屬性。

2) 若織軸品種與匹配織機原織軸品種相同，且織機連續(xù)結經(jīng)次數(shù)小于3時就可在織機上結經(jīng)，結經(jīng)時間與織軸經(jīng)紗根數(shù)有關；否則必須使用穿經(jīng)機穿經(jīng)。

3) 有m臺功能相同的織機，編號z= 1，2，…，m；所有織軸都可在織機上生產。織造前穿經(jīng)的織軸需在織機上先進行換軸，不需要穿經(jīng)的則在織機上進行結經(jīng)。換軸時間為定值，一般換軸時間大于結經(jīng)時間。加工時1臺織機同一時刻只能加工1個織軸，加工時間與機器的轉速、織軸繞長和緯密有關。

4) 有q臺功能相同的穿經(jīng)機，編號c= 1，2，…，q；穿經(jīng)機可對所有織軸進行加工。加工時1臺穿經(jīng)機同一時刻只能加工1個織軸，加工時間與機器速度和織軸經(jīng)紗根數(shù)有關；可用鋼筘數(shù)量必須要滿足穿經(jīng)需要。

5) 有g個相同的鋼筘，鋼筘是一種互斥資源?？椵S穿經(jīng)時需要占用一定數(shù)量的鋼筘，同時織機換軸后會釋放原織軸的鋼筘。穿經(jīng)時未被占用的鋼筘數(shù)量應滿足穿經(jīng)需要，否則需進行等待。

6) 零時刻，所有工件均處于待加工狀態(tài)，所有機器均處于初始空閑狀態(tài)，進入各織機的第1個織軸需要穿經(jīng)，鋼筘數(shù)量為織機數(shù)量的1.5倍。

1.3 問題建模

1.3.1 目標函數(shù)

為應對織造車間調度的需要，實現(xiàn)各需求間的相互平衡，本文為織造車間調度模型設置了3個目標。

1.3.1.1最小化逾期損失 隨著產業(yè)鏈各企業(yè)間的聯(lián)系日益緊密，按時完成生產變得越來越重要，但生產旺季時訂單集中到來，訂單量在某些時間會超過最大產能，逾期往往在所難免，所以如何讓逾期帶來的損失最小逐漸成為調度的一個重點。企業(yè)往往會根據(jù)客戶和訂單的重要程度給織軸任務賦予不同的權重，但實際生產時很容易忽視權重低的任務。本文為更好反映逾期損失與逾期時間的關系，構建了以任務權重為底數(shù)，逾期時間為指數(shù)的指數(shù)關系模型。圖2示出權重hi為1.3、1.5、1.7和1.9時逾期時間與損失之間的關系?？芍嗤挠馄跁r間，權重越高的任務損失越大，同時權重較低的任務如果逾期過多，損失也會指數(shù)級增長，因此，該模型既可以很好地關注權重較高的任務，也不會因為任務的權重低而將其忽視。相比文獻[12]中客戶滿意度與交期關系中簡單的線性變化，指數(shù)模型更能體現(xiàn)企業(yè)損失(或客戶滿意度)與逾期之間的關系。

式中:f1為最小化逾期損失；xi為織軸i的逾期時間，h；Ci為織軸i的織造完工時間，h；di為織軸i的截止時間，h；hi為織軸i的逾期損失權重，是大于1的實數(shù)。

圖2 逾期時間與損失的關系Fig.2 Relationship between overdue time and loss

1.3.1.2最小化完工時間 最小化完工時間(f2)是大多數(shù)調度算法都會確定的目標，也可宏觀反映生產的狀況，隨著生產管理的精細化，車間需要更加具體的調度指標，因此，本文針對織造車間提出了最小化織機空閑時間的目標。

1.3.1.3最小化織機空閑時間 織機是織造車間數(shù)量最多、管理最困難的機器，最小化織機空閑時間(f3) 可更加精細地對織機的運行進行優(yōu)化，提高織機整體效率，減少換軸和穿經(jīng)工序的次數(shù)。

1.3.2 約束條件

織造車間調度問題既要考慮穿結經(jīng)和織造工序間的約束關系，還要加入鋼筘資源的約束，為此建立3個約束條件。

1.3.2.1織造約束 對于要先后在同一臺織機上加工的織軸i和i+1：

1.3.2.2穿經(jīng)約束 對于要先后在同一臺穿經(jīng)機上加工的織軸i和i+1:

1.3.2.3鋼筘約束 任意時刻，鋼筘的總數(shù)量g要不小于正在穿經(jīng)織軸集JC、已穿經(jīng)但未織造織軸集JCC和正在織造織軸集JZ所占用鋼筘的數(shù)量之和，即：

g≥JC+JCC+JZ

2 動態(tài)調度

實際生產中因為插單、故障、交貨期改變等各種不確定因素，導致實際生產偏離原有計劃，甚至原有計劃失效，因此，根據(jù)實際情況動態(tài)的調整計劃是非常必要的。

2.1 動態(tài)調度窗口

實現(xiàn)動態(tài)調度首先要標注織軸的處理狀態(tài)，確定動態(tài)調度窗口，即可調度織軸集JS。本文將所有織軸分成未加工織軸集JU、正在穿經(jīng)織軸集JC、已穿經(jīng)但未織造織軸集JCC、正在織造織軸集JZ和已織造織軸集JZC。調度開始前,根據(jù)織軸狀態(tài)將織軸集JU、JC和JCC作為動態(tài)可調度織軸集JS，實時更新機器動態(tài)信息和鋼筘信息。調度時，將JS中的織軸按逾期損失最小、最大完工時間最小和織機空閑時間最小的多目標從全局出發(fā)進行調度。

2.2 基于支配關系評價的動態(tài)調度機制

目前，針對車間的動態(tài)調度機制主要分為事件驅動、周期性驅動和事件與周期性混合驅動3種。事件驅動機制為及時應對車間生產加工過程中的突發(fā)事件，當設定事件發(fā)生時就進行調度；周期性驅動機制是確定1個時間周期進行調度；事件與周期性混合驅動的機制是前二者的融合，綜合了前二者的優(yōu)點。這些調度機制是根據(jù)不同的應用場景提出的，也各有優(yōu)缺點，但這些調度機制都缺少量化的評價機制來衡量是否需要調度，因此，本文提出了基于支配關系評價的動態(tài)調度機制。

當一些突發(fā)或周期性事件導致實際生產偏離原有計劃時，根據(jù)原方案的調度計劃可計算出f1、f2、f3這3個目標函數(shù)值，同時調度系統(tǒng)也會生產新的Pareto調度方案解集。若新解集存在新方案的目標值f′1、f′2、f′3，若原方案目標函數(shù)fi與新方案目標函數(shù)f′i滿足支配關系公式：

則新方案優(yōu)于舊方案，新方案可取代舊方案。

為使該評價可滿足調度要求，本文做出以下合理的設定：當系統(tǒng)初次調度時原方案不存在或有新織軸插入，使得原方案不再適用時，則令舊方案的fi為無容大，讓新舊方案目標值必然滿足支配關系公式。圖3示出動態(tài)調度程序框圖。

圖3 動態(tài)調度流程圖Fig.3 Dynamic scheduling flow chart

3 改進的NSGAII調度算法設計

遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的高度并行、隨機、自適應的搜索算法，被廣泛應用于函數(shù)優(yōu)化、組合優(yōu)化、生產調度、機器學習等[13]。NSGAII作為一種多目標遺傳算法[14]，其基于Pareto支配關系的排序方式降低了非劣排序復雜性，運行速度快，解集收斂性好，但解空間過大時易陷入局部最優(yōu)。啟發(fā)式規(guī)則(啟發(fā)式算法)是一種基于直觀或經(jīng)驗構造的算法，合理的構造可有效減小算法搜索空間。本文為解決搜索失靈問題，將遺傳算法與啟發(fā)式規(guī)則融合。

3.1 基于決策變量的調度規(guī)模分析

根據(jù)上述問題描述及模型，實現(xiàn)織造調度共要求解4組決策變量，分別是織軸進入織造工序的順序、織軸對織機的選擇、織軸進入穿經(jīng)的順序和穿經(jīng)機的選擇。

參考浙江某小型織造車間的數(shù)據(jù)為例：100臺織機，2臺穿經(jīng)機，300個織軸的織造車間調度規(guī)模下，全部織軸進入織造工序的順序有300！種可能；若每個織軸可選任一織機，共有100300種可能；假設20%織軸需要穿經(jīng)，則織軸的穿經(jīng)順序有60！種選擇；穿經(jīng)機選擇有260種，此時完整解空間中可行解個數(shù)為300!×100300×60!×260= 2.94×101 314。遺傳算法按照種群規(guī)模100，最大迭代次數(shù)為500計算，算法最多能評價到的解為50 000個，此時算法能評價到的解和完整解空間已經(jīng)不成比例，搜索宛如大海撈針，遺傳算法很難在有限的時間內在如此巨大的空間中進化出高質量解，且極易陷入局部最優(yōu)，本文稱這種現(xiàn)象為搜索失靈。

隨著調度規(guī)模的增大，解空間呈指數(shù)級膨脹，這也是遺傳算法在小規(guī)模調度中的效果良好，大規(guī)模調度中求解能力迅速下降的原因。文獻[5-6]也注意到了這個問題，并通過縮小解空間、增大算法評價范圍、利用啟發(fā)式規(guī)則引導算法搜索等來進行克服，但實現(xiàn)的規(guī)模遠沒有達到本案例的需求。

3.2 求解決策變量的啟發(fā)式規(guī)則

為縮小解空間，本文針對不同的決策變量設計了相應啟發(fā)算法?？紤]織造車間中織機選擇對穿經(jīng)工序的逆影響，且調度關鍵工藝主要在織造工序上，因此，將織軸與織機的匹配選擇作為核心決策變量，提供2種啟發(fā)式規(guī)則，以每個織軸的織機選擇規(guī)則作為染色體基因進行編解碼，然后再利用遺傳算法對啟發(fā)規(guī)則的選擇進行全局優(yōu)化；將織軸進入織造工序的順序、織軸進入穿經(jīng)的順序和穿經(jīng)機選擇作為非核心決策變量，采用單一的啟發(fā)式規(guī)則。

3.2.1 織機選擇啟發(fā)規(guī)則

依據(jù)織軸匹配織機的實際需求，提煉出3個織機排產特征：最早可用時間、是否需要穿經(jīng)和織速，然后根據(jù)特征的優(yōu)先級為織軸選擇織機。本文設計了a、b2個規(guī)則。

規(guī)則a：按照最早可用時間較小>無需穿經(jīng)>織速較快的優(yōu)先級順序為織軸選擇匹配織機，即優(yōu)先選擇最早可用時間最小的織機，最早可用時間相同時優(yōu)先選擇無需穿經(jīng)的織機，若前2個條件仍無法匹配到織機，則優(yōu)先選擇織速最快的織機。

規(guī)則b：按照無需穿經(jīng)>最早可用時間較小>織速較快的優(yōu)先級順序選擇匹配織機，即優(yōu)先選擇無需穿經(jīng)的織機，在無需穿經(jīng)的織機中優(yōu)先選擇最早可用時間最小的織機，最早可用時間相同時，則優(yōu)先選擇織速最快的織機。

3.2.2 織造排序的啟發(fā)式規(guī)則

基于最早截止時間優(yōu)先(EDF)，將可調度織軸集JS中的織軸按其截止時間從小到大進行排序，優(yōu)先選擇截止時間小的，在截止時間相同時按照織軸到達時間排序。

3.2.3 穿經(jīng)排序啟發(fā)規(guī)則

根據(jù)織造排序和織機選擇的決策變量可確定哪些織軸需要穿經(jīng)和其織造的開始時間，將織造工序的開始時間作為穿經(jīng)工序的截止時間，基于EDF按照穿經(jīng)工序的截止時間從小到大排序，優(yōu)先選擇截止時間小的，截止時間相同時以織軸到達時間排序；鋼筘的占用優(yōu)先級也服從此排序。

3.2.4 穿經(jīng)機選擇啟發(fā)規(guī)則

穿經(jīng)機的選擇則在排序的基礎上，將織軸優(yōu)先分配到最早可用時間最小的穿經(jīng)機上。

3.3 啟發(fā)規(guī)則的染色體編解碼

核心決策變量織機選擇的啟發(fā)規(guī)則有a、b2種， 對規(guī)則選擇進行編碼求解，本文采用實整數(shù)編碼，是實質編碼的一種，其編碼的染色體不需要解碼即可直接表示對應的決策變量。染色體個體可用一維矩陣表示為 [x1,…，xi,…，xn]，染色體長度為可調度織軸集JS中織軸的個數(shù)，xi的值對應啟發(fā)式規(guī)則的編號。例如某個體染色體矩陣為 [0,1,1,0,1] 時，表示排序后對應的織軸分別按照 [a,b,b,a,b] 的啟發(fā)規(guī)則匹配選擇對應特征的織機。

這樣任意織軸的調度路線只有2種可選，根據(jù)3.1節(jié)中的案例，全部織軸共有2300種調度可能，即使織機數(shù)量增加，也不會使解空間增大，解空間僅與織軸個數(shù)呈指數(shù)關系。按照本文這種方法將遺傳算法與啟發(fā)式規(guī)則融合，前者負責全局優(yōu)化，后者負責具體任務的調度，在保障算法優(yōu)化質量的同時，極大縮小遺傳算法的搜索范圍，提高搜索效率，但本文這種編碼方式不能表達完整的解空間。

3.4 自適應貪婪進化算子

NSGAII隨著進化代數(shù)的增加，種群個體的相似度可能逐漸增加，進而陷入局部最優(yōu)，而且NSGAII缺乏局部深入搜索的能力。為此，本文提出了自適應貪婪進化算子，其并非獨立存在，是一個貫穿種群進化始終的框架，該算法主要通過檢查子代中是否有新精英個體出現(xiàn)，用循環(huán)來推進算法更加深入的搜索，以此防止進化陷入局部最優(yōu)。為避免某一代過度貪婪循環(huán)，設置了貪婪循環(huán)的次數(shù)上限igreed，同時為避免全局的過度貪婪搜索，設置了連續(xù)無效貪婪代數(shù)的上限jgen。

貪婪算子在算法中的全局搜索過程步驟如下。

步驟1：以父代種群P(t)為基礎進行進化操作，并通過局部貪婪搜索獲得新子代D(t)，若局部貪婪搜索為無效進化，則進入步驟2，否則進入步驟3。

步驟2：連續(xù)無效貪婪次數(shù)j加1，若j未超過設定最大次數(shù)jgen，進入步驟1；若j超過jgen，則退出貪婪算子，不再進入。

步驟3:父代種群P(t)和子代種群D(t)合并獲得混合種群R(t)，通過NSGAII算法的快速非支配排序分層及個體擁擠距離的計算，從R(t)中選擇合適個體生成下一代父種群P(t+1)，種群規(guī)模和前一代一致。種群迭代次數(shù)i加1，并返回步驟1。

貪婪算子的局部搜索過程步驟如下。

步驟1：以父代種群P(t)為基礎進行選擇、交叉、變異獲得新子代D(t)。

步驟2：實現(xiàn)對某一代的貪婪搜索，將父代種群P(t)與子代種群D(t)進行對比，若?Xa∈D(t)，對Xb∈P(t)，使Xa>Xb或Xa、Xb互不匹配，則記為有效進化進入步驟4；否則記為無效進化，進入步驟3。

步驟3：貪婪搜索次數(shù)i加1，若i未超過設定最大循環(huán)次數(shù)igreed，進入步驟1；若i超過igreed仍未實現(xiàn)有效進化，記為無效貪婪，放棄本代的貪婪循環(huán)進入步驟4。

步驟4:將父代種群P(t)與子代種群D(t)合并生成R(t),本代搜索結束。本文使用的選擇、交叉和變異算子分別為：二元錦標賽選擇策略[15]、模擬二進制交叉[16]和多項式變異算子[17]。

4 仿真與分析

為驗證織造車間調度模型及其求解算法，本文在參考浙江蘭溪某紡織企業(yè)數(shù)據(jù)的基礎上，編寫案例參數(shù)。其中，m表示織機數(shù)，k表示訂單數(shù)，每個訂單的權重為[1,2]間的任一小數(shù)，各訂單的到達時間均設為0，截止時間滿足ceil(7/m)×500

本文使用Python編程，用到的開源程序包主要有geatpy、numpy、matplotlib。計算機操作系統(tǒng)為64位 win7，內存16 GB，處理器主頻2.90 GHz。

4.1 貪婪進化算子的有效性驗證

為驗證本文貪婪進化算子對算法搜索能力的提升，將NSGAII與帶自適應的貪婪進化算子的NSGAII(NSGAII_G)進行對比，比較二者Pareto 前沿解集的收斂性。在控制變量、編解碼方式，選擇算子、交叉算子和變異算子等均相同條件下，按照參數(shù)生成規(guī)則，并令m=12,k=10，種群規(guī)模Popsize為100，最大迭代次數(shù)maxGen為300，交叉概率Pc=1，變異概率Pm=1/n(n為織軸個數(shù))，igreed=5，jgen=5，隨機生成a、b、c、d 4個調度仿真案例，每個案例分別進行 4次仿真。

圖4分別示出NSGAII和NSGAII_G的a、b、c、d的4個案例仿真結果的Pareto前沿解集分布對比圖。3個目標函數(shù)f1、f2、f3越小越好。圖中NSGAII_G的Pareto前沿點主要分布在NSGAII的左下側，可知，NSGAII_G的前沿點的各目標值相對更小，支配能力更強。同時用C指標[18]對結果量化分析,結果如表1所示?？芍珻(NSGAII,NSGAII_G)< C(NSGAII_G,NSGAII)，即NSGAII_G的Pareto解集收斂性更好。

4.2 與已有算法靜態(tài)調度仿真對比

近視算法[19-20]是按啟發(fā)規(guī)則調度的算法；NSGAII_3是求解多目標混合流水車間調度的改進NSGAII，因為原算法與本文的應用場景存在差異，本文在使用時均做了適當修改，主要還原其算法思路。

多目標算法所得結果為一個包含多個個體的Pareto最優(yōu)解集，解集中所有個體均互不支配。為方便多目標算法與近視算法的比較，本文根據(jù)織造車間的實際需求，在解集中按照f1逾期損失>f2最大完工時>f3織機空閑時間的優(yōu)先級順序選出“最優(yōu)個體”，即優(yōu)先選擇逾期損失最小的個體，逾期損失相同時優(yōu)先選擇完工時間最短的，完工時間相同時優(yōu)先選擇織機空閑時間最小的。

圖4 前沿解集分布Fig.4 Frontier solution set distribution.(a)Case a; (b)Case b; (c)Case c;(d)Case d

表1 C指標結果對比Tab.1 Comparison of C index results

將近視算法、本文設計的融合啟發(fā)規(guī)則并帶自適應貪婪算子的NSGAII(H-NSGAII_G)和NSGAII_3 的調度結果進行對比。按照參數(shù)生成規(guī)則，分別令m=6、k=12，m=100、k=200和m=500、k=600 生成a1、b1、c13組不同規(guī)模的調度案例。仿真時選取不同數(shù)量的織機和織軸，算法參數(shù)設置同4.1節(jié)，結果如表2所示。

表2 3種算法的實驗結果統(tǒng)計Tab.2 Three algorithms of experimental results statistics

從表2中各目標值的仿真結果可知，a1組中織機數(shù)量較少時，當織軸數(shù)n為14、28時，NSGAII_3最優(yōu)，H-NSGAII_G次之；當n為42時，H-NSGAII_G最優(yōu)，NSGAII_3次之；當n為56、70時，H-NSGAII_G最優(yōu)，近視算法次之?？梢娍椵S數(shù)較少時，解空間還較小，此時擁有較完整解空間的NSGAII_3可以找到更優(yōu)的解；但隨著織軸增多，解空間增大，NSGAII_3的搜索空間快速擴大搜索能力開始下降，H-NSGAII_G的能力開始展現(xiàn)。

b1組中，織機數(shù)量為100，雖然NSGAII_3含有啟發(fā)式規(guī)則的輔助引導，但由于搜索空間膨脹，已出現(xiàn)本文3.1節(jié)中描述的搜索失靈現(xiàn)象，表現(xiàn)極差。n為245時，近視算法與H-NSGAII_G在f1和f2上還各有優(yōu)勢，但隨著織軸數(shù)量增加，在f1、f2和f3上H-NSGAII_G均優(yōu)于或等于近似算法和NSGAII_3。相比近似算法，當n=490、735、980、1 225時，完工時間分別減少11、26、54、30 h。

在c1組中織機為500臺，織軸有4 000個，其已達到中小型的織造車間的規(guī)模。H-NSGAII_G調度結果遠優(yōu)于近視算法和NSGAII_3，相比近視算法可節(jié)省完工時間626 h，這主要是因為H-NSGAII_G全局優(yōu)化能力較強，而近視算法只是符合一般經(jīng)驗的調度規(guī)則，因此，規(guī)模越大情況越復雜，H-NSGAII_G 的優(yōu)化能力就越突出。

從表2可見：近視算法在計算耗時上始終保持較高優(yōu)勢；H-NSGAII_G與NSGAII_3的耗時會隨調度規(guī)模增大快速增加，特別是在c1組的大規(guī)模調度中，H-NSGAII_G調度耗時約為6.4 h，近視算法僅為22.24 s，但考慮到H-NSGAII_G節(jié)省完工時間626 h，H-NSGAII_G仍有較大的優(yōu)勢。

圖5 織造工序再調度甘特圖Fig.5 Weaving process is rescheduled Gantt chart

4.3 動態(tài)調度可行性驗證

緊急插單是織造生產時常見的需動態(tài)調度的事件，本文以此來驗證動態(tài)調度可行性。根據(jù)參數(shù)生成規(guī)則，令m=6，k=4時，案例調度結果見表3。其中15號到16號織軸的開始時刻跨度變大是因為鋼筘資源有限，16號織軸需等待鋼筘資源釋放后才能開始穿經(jīng)。

表3 穿經(jīng)工序調度Tab.3 Drawing-in process scheduling

在時間為200 h時出現(xiàn)一個緊急訂單，訂單到達時間為200 h，截止時間為900 h，生產5號品種，4個織軸編號分別為71、72、73、74，織軸經(jīng)紗繞長為 2 500 m， 經(jīng)紗根數(shù)為8 500根。根據(jù)3.2節(jié)的動態(tài)調度機制重排后結果見表3，再調度部分見圖5。圖5 中淺色條塊表示織機處于運行狀態(tài)，深色表示空閑，其上的數(shù)字表示任務編號及品種，如“8(5)”表示 8號織軸5號品種。

表3中，時間為200 h時初始調度中只有29號織軸未開始穿經(jīng)，再調度后緊急訂單中的71號織軸先于29號加工，29號織軸擁有了新穿經(jīng)計劃，新增了 20號， 21號等在初始調度中不需要穿經(jīng)的織軸。圖5 中2號織機在4號織軸與71號織軸間存在較長的空閑時間，是因為鋼筘資源對71號織軸的穿經(jīng)約束造成的，重調度后逾期損失為0，可見緊急訂單被很好的插入生成計劃。

根據(jù)本文2.1節(jié)中的動態(tài)調度規(guī)則，本次再調度的實際只為時間200 h時還未開始的21個任務進程，已完工或正在生產的任務不參與再調度。整體調度耗時/織軸任務數(shù)=單個織軸調度耗時，根據(jù)表2 H-NSGAII_G 的單織軸調度理論耗時約5 s，本次再調度理論耗時約105 s，實際運行H-NSGAII_G再調度耗時102.5 s，可見臨時緊急任務的插入并未對算法耗時產生影響。

5 結 論

本文針對多織機、多織軸、多產品的大規(guī)?？椩煺{度，且織造和穿經(jīng)工序之間存在逆工序調度關系，已有的啟發(fā)式算法優(yōu)化搜索效率低的問題，在綜合考慮穿經(jīng)約束下，以完工時間、訂單逾期、織機空閑時間為優(yōu)化目標構建了織造多目標大規(guī)模排產模型；提出了一種大規(guī)模動態(tài)調度的改進NSGAII 遺傳算法，為適應織造調度模型的特點，設計了一種改進啟發(fā)規(guī)則的編解碼方式，極大縮小了解空間，解決已有優(yōu)化方法在織造工序大規(guī)模調度尋優(yōu)中時間長，易陷入局部最優(yōu)的問題。設計了一種基于支配關系評價的動態(tài)調度機制，通過實驗驗證了策略的有效性，解決傳統(tǒng)調度優(yōu)化方法在織造實際應用中響應機制較差的問題。

本文在解決大規(guī)模調度問題上，實際是利用啟發(fā)式規(guī)則對完整解空間進行切割，遺傳算法在其中起著全局指揮的角色，雖然剔除了大量質量較差解，但也會失去一些優(yōu)秀的解，而且算法在處理大規(guī)模調度時計算耗時較長，這些問題還有待解決。