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

沈春婭， 雷鈞杰， 汝 欣， 彭來(lái)湖， 胡旭東

(1. 浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(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)國(guó)。在智能制造大背景下，我國(guó)紡織業(yè)雖然近幾年技術(shù)進(jìn)步迅速，但仍屬于勞動(dòng)密集型產(chǎn)業(yè)，人力資源成本占比高；同時(shí)生產(chǎn)工藝繁雜，品種多樣，對(duì)生產(chǎn)柔性要求高。紡織業(yè)實(shí)現(xiàn)智能化生產(chǎn)轉(zhuǎn)型意義重大[1]，智能調(diào)度在生產(chǎn)過(guò)程智能化中具有核心決策功能，是實(shí)現(xiàn)紡織智能制造的重要環(huán)節(jié)。

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

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

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

目前，針對(duì)織造車間這種大規(guī)模多目標(biāo)的HFSPI研究較少，雖有學(xué)者研究過(guò)織造的織軸調(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織造車間動(dòng)態(tài)調(diào)度算法，以期解決傳統(tǒng)動(dòng)態(tài)調(diào)度機(jī)制在織造插單、打樣等復(fù)雜生產(chǎn)場(chǎng)景中適應(yīng)性不強(qiáng)的問(wèn)題。

1 問(wèn)題描述及建模

1.1 問(wèn)題描述

織造車間的生產(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ù)量的鋼筘，并選擇一臺(tái)穿經(jīng)機(jī)進(jìn)行穿經(jīng)，最后選擇一臺(tái)織機(jī)完成換軸和織造，若不需穿經(jīng)，則選擇一臺(tái)織機(jī)完成結(jié)經(jīng)和織造。結(jié)經(jīng)機(jī)數(shù)量充足，其可能帶來(lái)的約束本文不予考慮。

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

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

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

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

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

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

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

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

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

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

1.3 問(wèn)題建模

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

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

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

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

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

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

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

1.3.2 約束條件

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

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

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

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

g≥JC+JCC+JZ

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

實(shí)際生產(chǎn)中因?yàn)椴鍐巍⒐收稀⒔回浧诟淖兊雀鞣N不確定因素，導(dǎo)致實(shí)際生產(chǎn)偏離原有計(jì)劃，甚至原有計(jì)劃失效，因此，根據(jù)實(shí)際情況動(dòng)態(tài)的調(diào)整計(jì)劃是非常必要的。

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

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

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

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

當(dāng)一些突發(fā)或周期性事件導(dǎo)致實(shí)際生產(chǎn)偏離原有計(jì)劃時(shí)，根據(jù)原方案的調(diào)度計(jì)劃可計(jì)算出f1、f2、f3這3個(gè)目標(biāo)函數(shù)值，同時(shí)調(diào)度系統(tǒng)也會(huì)生產(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)于舊方案，新方案可取代舊方案。

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

圖3 動(dòng)態(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)行速度快，解集收斂性好，但解空間過(guò)大時(shí)易陷入局部最優(yōu)。啟發(fā)式規(guī)則(啟發(fā)式算法)是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，合理的構(gòu)造可有效減小算法搜索空間。本文為解決搜索失靈問(wèn)題，將遺傳算法與啟發(fā)式規(guī)則融合。

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

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

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

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

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

為縮小解空間，本文針對(duì)不同的決策變量設(shè)計(jì)了相應(yīng)啟發(fā)算法。考慮織造車間中織機(jī)選擇對(duì)穿經(jīng)工序的逆影響，且調(diào)度關(guān)鍵工藝主要在織造工序上，因此，將織軸與織機(jī)的匹配選擇作為核心決策變量，提供2種啟發(fā)式規(guī)則，以每個(gè)織軸的織機(jī)選擇規(guī)則作為染色體基因進(jìn)行編解碼，然后再利用遺傳算法對(duì)啟發(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個(gè)織機(jī)排產(chǎn)特征：最早可用時(shí)間、是否需要穿經(jīng)和織速，然后根據(jù)特征的優(yōu)先級(jí)為織軸選擇織機(jī)。本文設(shè)計(jì)了a、b2個(gè)規(guī)則。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟3：貪婪搜索次數(shù)i加1，若i未超過(guò)設(shè)定最大循環(huán)次數(shù)igreed，進(jìn)入步驟1；若i超過(guò)igreed仍未實(shí)現(xiàn)有效進(jìn)化，記為無(wú)效貪婪，放棄本代的貪婪循環(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ù)，每個(gè)訂單的權(quán)重為[1,2]間的任一小數(shù)，各訂單的到達(dá)時(shí)間均設(shè)為0，截止時(shí)間滿足ceil(7/m)×500

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

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

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

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

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

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

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

將近視算法、本文設(shè)計(jì)的融合啟發(fā)規(guī)則并帶自適應(yīng)貪婪算子的NSGAII(H-NSGAII_G)和NSGAII_3 的調(diào)度結(jié)果進(jìn)行對(duì)比。按照參數(shù)生成規(guī)則，分別令m=6、k=12，m=100、k=200和m=500、k=600 生成a1、b1、c13組不同規(guī)模的調(diào)度案例。仿真時(shí)選取不同數(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ù)量較少時(shí)，當(dāng)織軸數(shù)n為14、28時(shí)，NSGAII_3最優(yōu)，H-NSGAII_G次之；當(dāng)n為42時(shí)，H-NSGAII_G最優(yōu)，NSGAII_3次之；當(dāng)n為56、70時(shí)，H-NSGAII_G最優(yōu)，近視算法次之。可見(jiàn)織軸數(shù)較少時(shí)，解空間還較小，此時(shí)擁有較完整解空間的NSGAII_3可以找到更優(yōu)的解；但隨著織軸增多，解空間增大，NSGAII_3的搜索空間快速擴(kuò)大搜索能力開(kāi)始下降，H-NSGAII_G的能力開(kāi)始展現(xiàn)。

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

在c1組中織機(jī)為500臺(tái)，織軸有4 000個(gè)，其已達(dá)到中小型的織造車間的規(guī)模。H-NSGAII_G調(diào)度結(jié)果遠(yuǎn)優(yōu)于近視算法和NSGAII_3，相比近視算法可節(jié)省完工時(shí)間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可見(jiàn)：近視算法在計(jì)算耗時(shí)上始終保持較高優(yōu)勢(shì)；H-NSGAII_G與NSGAII_3的耗時(shí)會(huì)隨調(diào)度規(guī)模增大快速增加，特別是在c1組的大規(guī)模調(diào)度中，H-NSGAII_G調(diào)度耗時(shí)約為6.4 h，近視算法僅為22.24 s，但考慮到H-NSGAII_G節(jié)省完工時(shí)間626 h，H-NSGAII_G仍有較大的優(yōu)勢(shì)。

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

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

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

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

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

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

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

5 結(jié) 論

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

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