基于改進型NSGAII的織造車間多目標大規模動態調度

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

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

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

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

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

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

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

1 問題描述及建模

1.1 問題描述

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

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

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

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

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

1.2 基本定義與假設

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

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

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

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

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

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

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

1.3 問題建模

1.3.1 目標函數

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

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

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

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

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

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

1.3.2 約束條件

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

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

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

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

g≥JC+JCC+JZ

2 動態調度

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

2.1 動態調度窗口

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

2.2 基于支配關系評價的動態調度機制

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

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

則新方案優于舊方案，新方案可取代舊方案。

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

圖3 動態調度流程圖Fig.3 Dynamic scheduling flow chart

3 改進的NSGAII調度算法設計

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

3.1 基于決策變量的調度規模分析

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

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

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

3.2 求解決策變量的啟發式規則

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

3.2.1 織機選擇啟發規則

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

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

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

3.2.2 織造排序的啟發式規則

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

3.2.3 穿經排序啟發規則

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

3.2.4 穿經機選擇啟發規則

穿經機的選擇則在排序的基礎上，將織軸優先分配到最早可用時間最小的穿經機上。

3.3 啟發規則的染色體編解碼

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

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

3.4 自適應貪婪進化算子

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

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

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

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

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

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

4.2 與已有算法靜態調度仿真對比

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

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

圖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

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

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

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

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

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

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

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

4.3 動態調度可行性驗證

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

表3 穿經工序調度Tab.3 Drawing-in process scheduling

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

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

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

5 結 論

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

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