基于改進(jìn)型NSGAII的織造車間多目標(biāo)大規(guī)模動態(tài)調(diào)度

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

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

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

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

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

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

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

1 問題描述及建模

1.1 問題描述

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

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

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

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

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

1.2 基本定義與假設(shè)

為量化織造車間調(diào)度中的各類因素，簡化車間內(nèi)任務(wù)、機(jī)器和資源的調(diào)度，本文做出以下合理的定義與假設(shè)。

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

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

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

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

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

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

1.3 問題建模

1.3.1 目標(biāo)函數(shù)

為應(yīng)對織造車間調(diào)度的需要，實(shí)現(xiàn)各需求間的相互平衡，本文為織造車間調(diào)度模型設(shè)置了3個目標(biāo)。

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

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

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

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

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

1.3.2 約束條件

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

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

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

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

g≥JC+JCC+JZ

2 動態(tài)調(diào)度

實(shí)際生產(chǎn)中因?yàn)椴鍐?、故障、交貨期改變等各種不確定因素，導(dǎo)致實(shí)際生產(chǎn)偏離原有計(jì)劃，甚至原有計(jì)劃失效，因此，根據(jù)實(shí)際情況動態(tài)的調(diào)整計(jì)劃是非常必要的。

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

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

2.2 基于支配關(guān)系評價的動態(tài)調(diào)度機(jī)制

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

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

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

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

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

3 改進(jìn)的NSGAII調(diào)度算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 自適應(yīng)貪婪進(jìn)化算子

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

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

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

4.1 貪婪進(jìn)化算子的有效性驗(yàn)證

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

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

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

近視算法[19-20]是按啟發(fā)規(guī)則調(diào)度的算法；NSGAII_3是求解多目標(biāo)混合流水車間調(diào)度的改進(jìn)NSGAII，因?yàn)樵惴ㄅc本文的應(yīng)用場景存在差異，本文在使用時均做了適當(dāng)修改，主要還原其算法思路。

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

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

表1 C指標(biāo)結(jié)果對比Tab.1 Comparison of C index results

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

表2 3種算法的實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)Tab.2 Three algorithms of experimental results statistics

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

b1組中，織機(jī)數(shù)量為100，雖然NSGAII_3含有啟發(fā)式規(guī)則的輔助引導(dǎo)，但由于搜索空間膨脹，已出現(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。相比近似算法，當(dāng)n=490、735、980、1 225時，完工時間分別減少11、26、54、30 h。

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

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

圖5 織造工序再調(diào)度甘特圖Fig.5 Weaving process is rescheduled Gantt chart

4.3 動態(tài)調(diào)度可行性驗(yàn)證

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

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

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

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

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

5 結(jié) 論

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

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