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

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

隨著智能紡織的快速推進,紡織行業(yè)越來越關(guān)注織造車間智能調(diào)度問題。織造車間人員、機器、物料數(shù)量眾多,而且近年來又逐漸向多品種小批量的生產(chǎn)方式轉(zhuǎn)變,這導(dǎo)致織造車間實際的調(diào)度難度、問題復(fù)雜度和調(diào)度規(guī)模呈指數(shù)級增加,同時在織造車間實際的生產(chǎn)安排中,必須保證良好的調(diào)度質(zhì)量和調(diào)度速度,因此,織造車間調(diào)度算法的研究是實現(xiàn)智能紡織較為重要的環(huán)節(jié)。

傳統(tǒng)調(diào)度算法中,如截止期優(yōu)先調(diào)度算法[1]、近視算法[2-3]等,這些基于規(guī)則的調(diào)度算法,由于其調(diào)度邏輯是根據(jù)生產(chǎn)經(jīng)驗抽象而來,因此,調(diào)度過程完全透明,對于具體的調(diào)度問題,結(jié)果穩(wěn)定可控,而且技術(shù)門檻低,被工業(yè)生產(chǎn)大量應(yīng)用,但算法的實現(xiàn)、迭代、調(diào)度的優(yōu)劣非常依賴人工經(jīng)驗,上限不高。

智能調(diào)度算法中,如蟻群算法[4]、遺傳算法[5]、粒子群算法[6]等,可以根據(jù)具體問題自行優(yōu)化,求解適應(yīng)性強,大大減少對人的依賴,但只能用于較小的調(diào)度規(guī)模,調(diào)度質(zhì)量上也沒有質(zhì)的提升,調(diào)度速度上也難以滿足企業(yè)需求。一些學(xué)者[7-9]為解決智能調(diào)度算法在大規(guī)模調(diào)度中的應(yīng)用問題,在限制求解范圍、引導(dǎo)智能算法搜索方向等方面進行了嘗試,但在調(diào)度質(zhì)量和調(diào)度速度上依然停留在實驗室層面。

為解決織造車間大規(guī)模調(diào)度問題,本文基于NSGAII和神經(jīng)網(wǎng)絡(luò)提出了織造車間調(diào)度算法(NSGAII-NN125)。該算法分為2個模塊,由以神經(jīng)網(wǎng)絡(luò)為主體的調(diào)度模塊和以遺傳算法為主體的優(yōu)化模塊組成。調(diào)度模塊負(fù)責(zé)具體的調(diào)度工作,生成調(diào)度方案,優(yōu)化模塊根據(jù)方案優(yōu)劣對NN125進行迭代優(yōu)化。將遺傳算法的優(yōu)化參數(shù)和調(diào)度方案間用神經(jīng)網(wǎng)絡(luò)“隔開”,這樣需要優(yōu)化的參數(shù)個數(shù),就不會隨調(diào)度規(guī)模的增大呈指數(shù)級增加,遺傳算法優(yōu)化時陷入局部最優(yōu)的風(fēng)險便可以得到規(guī)避。而且,NSGAII-NN125算法對織造車間調(diào)度問題求解后,輸入調(diào)度任務(wù)的帕累托最優(yōu)調(diào)度方案集合和最優(yōu)網(wǎng)絡(luò)參數(shù)集合,直接使用已經(jīng)優(yōu)化的NN125集合解決相似的問題,由于去除了NSGAII優(yōu)化模塊的優(yōu)化過程,可大大提高調(diào)度速度。

1 織造車間生產(chǎn)調(diào)度模型

1.1 織造車間工藝流程

圖1示出織造車間的工藝流程?？椵S為織造車間的輸入,其主要的工藝路線有3條。路線1:穿經(jīng)→改車換軸→織造;路線2:穿經(jīng)→同品種換軸→織造;路線3:結(jié)經(jīng)→織造。

圖1 織造車間工藝流程

隨著自動穿經(jīng)機的發(fā)展,穿經(jīng)工序已經(jīng)獨立出去,需要穿經(jīng)的織軸可提前完成,生產(chǎn)的瓶頸來到了換軸和結(jié)經(jīng)上。眾所周知,進行換軸和結(jié)經(jīng)工藝時,織機無法生產(chǎn),織機的產(chǎn)能將必然浪費。工藝耗時:改車換軸>同品種換軸>結(jié)經(jīng),因此優(yōu)化生產(chǎn)調(diào)度,將減少路線1和2的使用,增多路線3的使用成為調(diào)度的重點。

由圖1可知,在織造車間的生產(chǎn)中,織軸經(jīng)過穿經(jīng)或結(jié)經(jīng)后才能進行織造,但安排生產(chǎn)時必須提前考慮織造,因為穿經(jīng)、結(jié)經(jīng)和換軸本質(zhì)上是織造的準(zhǔn)備工序?？椩旃ば蛏?如果先后上機的2個織軸加工工藝不同,則織造的準(zhǔn)備工序為穿經(jīng)工序和改車換軸,即使用工藝路線1;如果先后上機的2個織軸加工工藝相同,同時織機累計結(jié)經(jīng)次數(shù)大于3[10-11],則織造的準(zhǔn)備工序為穿經(jīng)工序和同品種換軸,即使用工藝路線2;如果先后上機的2個織軸加工工藝相同,同時織機累計結(jié)經(jīng)次數(shù)不大于3次,則織造的準(zhǔn)備工序僅為結(jié)經(jīng),即使用工藝路線3。

綜上所述,織軸選擇哪條工藝路線,最終都取決于織機的選擇,因此,織造車間調(diào)度問題的核心是解決多個織軸與多臺織機的選擇。

1.2 模型描述

為限定織造車間模型范圍,方便行文描述,本文做出如下定義和假設(shè)。

1)織軸為最小調(diào)度單元,織軸編號i=1,2,…,N;織軸具有所屬訂單、品種、繞長等屬性。

2)織機用于織軸的加工,織機編號j=1,2,…,M?？棛C有織速、累計結(jié)經(jīng)次數(shù)等屬性。

3)同一臺織機上,若先后上機的織軸加工工藝相同,且織機累計結(jié)經(jīng)次數(shù)不大于3,則僅需要結(jié)經(jīng);若先后上機的織軸加工工藝相同且織機累計結(jié)經(jīng)次數(shù)大于3,則需要同品種換軸;若先后上機的織軸織物品種不同,則需要改車換軸。

4)穿經(jīng)機和結(jié)經(jīng)機充足,不是生產(chǎn)的瓶頸[11],結(jié)經(jīng)、同品種換軸和改車換軸耗時分別為1、3和4 h。

5) 初始時刻為0,所有織機都處于可用狀態(tài),所有織軸任務(wù)均就緒。

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

為滿足織造車間精益生產(chǎn)的需要,同時讓多目標(biāo)優(yōu)化的結(jié)果更加多元,本文為織造車間調(diào)度設(shè)置如下3個優(yōu)化目標(biāo)。

1.3.1 最小化逾期損失

(1)

1.3.2 最小化最大完工時間

在織造車間生產(chǎn)中將現(xiàn)有任務(wù)加工完成的時間是生產(chǎn)的重要指標(biāo),因此,本文將最小化最大完工時間f2作為調(diào)度目標(biāo)。

(2)

1.3.3 最小化改車次數(shù)

對于織機而言,平穩(wěn)運行非常重要,減少改車次數(shù)不僅可以提高織機效率、減少工人的工作量,而且因為減少了使用復(fù)雜的改車工序,可以降低產(chǎn)品質(zhì)量上的波動,所以將最小化改車次數(shù)作為優(yōu)化目標(biāo)。

(3)

式中:f3為最小化改車次數(shù);sj為織機j改車的次數(shù)。

2 織造車間智能調(diào)度算法

織造車間智能調(diào)度算法分為調(diào)度和優(yōu)化2個部分。調(diào)度上,又分為如下2個步驟。步驟1為織軸排序,利用固定的規(guī)則確定織軸進行織機選擇的先后次序。步驟2為織機選擇,本文設(shè)計了NN125,同時設(shè)計了5個織機的實時特征作為該網(wǎng)絡(luò)的輸入,NN125輸入織機的特征,輸出織機的評價數(shù)值,最后挑選出數(shù)值最大的織機。通過這2個步驟即可完成多個織軸與多臺織機的選擇。

優(yōu)化上,NSGAII作為優(yōu)化模塊的核心。首先隨機生成多個NN125參數(shù)不同的調(diào)度模塊,然后根據(jù)調(diào)度結(jié)果的優(yōu)劣,進行選擇、交叉和變異,經(jīng)過重復(fù)迭代即可完成優(yōu)化。

2.1 織軸排序

本文參考最早截止時間優(yōu)先(EDF)等的思路[9,12],結(jié)合織造車間的調(diào)度特點,設(shè)計了織軸排序的規(guī)則,將織軸“織軸截止時間>織軸到達(dá)時間>織軸加工時長”的優(yōu)先關(guān)系確定織軸排序。

2.2 織機選擇

2.2.1 輸入特征的設(shè)計

織軸一定時,織機的選擇成為調(diào)度的重點,為此本文設(shè)計了5個特征,作為評價織機的標(biāo)準(zhǔn)。

2.2.1.1織速 織速是體現(xiàn)織機性能的重要屬性。實際生產(chǎn)中織速不僅受織機本身力學(xué)性能的影響,還會隨織軸的工藝要求等各方面的差異而變動,為此用vij表示加工織軸i時織機j的織造速度。

2.2.1.2相對可用時間tj為織機的相對可用時間,為織機j可用時間與織機中可用時間最小值的差,計算公式為

(4)

2.2.1.3是否改車 為更好地優(yōu)化改車次數(shù)這個調(diào)度目標(biāo),本文設(shè)置了該特征,織軸選擇織機后是否需改車的表達(dá)式為:

(5)

2.2.1.4是否逾期 為更好地優(yōu)化化逾期損失,本文設(shè)置了該特征。織軸選擇織機后是否會導(dǎo)致時間上的逾期的表達(dá)式為:

(6)

(7)

2.2.2 神經(jīng)網(wǎng)絡(luò)設(shè)計

本文采用常規(guī)的全連接神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu),該網(wǎng)絡(luò)包括:輸入層、隱含層與輸出層,各層間的神經(jīng)元以全連接方式連接,整個網(wǎng)絡(luò)為5維輸入,1維輸出,即輸入織機的5個特征數(shù)值,輸出1個評價數(shù)值。

表1示出本文的神經(jīng)網(wǎng)絡(luò)的詳細(xì)信息。第1層為輸出層,輸入5個設(shè)計好的特征;2～5層為隱含層,結(jié)構(gòu)相同,每層均為5個神經(jīng)元,每個神經(jīng)元有5個權(quán)重參數(shù)和1個偏置參數(shù);第6層為輸出層。通過該表可知,此神經(jīng)網(wǎng)絡(luò)共有125個參數(shù),故稱其為“NN125”。用ReLU( )作為激活函數(shù),其數(shù)學(xué)表達(dá)式為max(0,z)。

表1 NN125詳細(xì)信息

2.2.3 織機選擇流程

織機選擇流程如圖2所示。在不保證選擇優(yōu)劣的情況下,任意參數(shù)的NN125通過該流程均能實現(xiàn)織軸對織機選擇。根據(jù)2.1節(jié)中的織軸排序結(jié)果,為所有織軸逐個依次挑選織機。假設(shè)為第i個織軸選擇織機,先求出所有織機相對于該織軸的織速vij、相對可用時間tij、準(zhǔn)備時間hij、是否逾期dij和進度pij(j=1,2,…,M),再將每個織機的這5個數(shù)值代入NN125的數(shù)學(xué)表達(dá)式中,運算得出所有織機的評價數(shù)值:Scoreij(j=1,2,…,M),最后挑選出Scoreij數(shù)值最大的織機。重復(fù)運行上述步驟,直至獲得一套完整的可細(xì)化到織機與織軸一一匹配的調(diào)度方案。

圖2 織機選擇流程

2.3 基于NSGAII的調(diào)度神經(jīng)網(wǎng)絡(luò)優(yōu)化

通過2.1節(jié)織軸排序和2.2節(jié)的織機選擇,可獲得一套完整的可細(xì)化到織機與織軸一一匹配的調(diào)度方案,但無法保證方案的優(yōu)劣,又因為NN125的參數(shù)與調(diào)度結(jié)果密切相關(guān),所以可以對NN125的參數(shù)進行優(yōu)化,進而獲得良好的調(diào)度結(jié)果。

優(yōu)化算法的選擇上,以梯度下降為代表的優(yōu)化算法不僅需要大量的訓(xùn)練樣本,而且為調(diào)度的各類情況設(shè)計訓(xùn)練標(biāo)簽極其困難。相較之下,遺傳算法[13]可以按照自然進化的原理,通過種群中個體的相互競爭直接對問題進行優(yōu)化,不需要訓(xùn)練樣本。

目前,經(jīng)過眾多學(xué)者的研究,遺傳算法已經(jīng)有很多優(yōu)秀的版本和實現(xiàn)方法,本文采用帶精英保留策略的快速支配多目標(biāo)遺傳算法NSGAII[14],對NN125的參數(shù)進行多目標(biāo)優(yōu)化。

2.3.1 決策變量的編碼和解碼

NN125的參數(shù)是決定調(diào)度優(yōu)劣的關(guān)鍵,稱其為遺傳算法欲優(yōu)化的決策變量。實整數(shù)編碼簡單易用,本文采用其對決策變量進行編碼。為縮小求解范圍,將決策變量的取值范圍設(shè)為[-γ,+γ],這樣遺傳算法初始化、交叉、變異生成的個體基因數(shù)值就被限制在[-γ,+γ]中,種群個體可以用一維數(shù)組[x1,x2,…,x125]表示,該數(shù)組長度為125,表示NN125的125個參數(shù),若種群規(guī)模Popsize=50,則種群可標(biāo)為50行、125列的二維數(shù)組。

解碼時將個體的125個決策變量,按照表1中神經(jīng)元所處的層級和序號,從小到大逐個填充。例如在種群中,已知某染色體數(shù)組的7～12元素值[…,1.3,5.6,-6,8,7.93,4,…],則解碼后神經(jīng)網(wǎng)絡(luò)對應(yīng)的第2層的第2個神經(jīng)元的實際運算式即為y=ReLU(1.3v+5.6t-6g+8d+7.93p+4)。

2.3.2 遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)

為對NN125的125個參數(shù)進行多目標(biāo)優(yōu)化,使用NSGAII遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)流程如圖3所示。

圖3 遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)流程

先將欲調(diào)度的織軸和織機的初始信息輸入,進行織軸排序的同時初始化遺傳算法中NN125種群:[NN1251,NN1252,…,NN125n]。因為每個NN125均為隨機生成,所以其參數(shù)值各不相同,最終形成的的調(diào)度結(jié)果也各有優(yōu)劣:[結(jié)果1,結(jié)果2,…,結(jié)果n]。然后,計算每個調(diào)度結(jié)果的3個目標(biāo)值,再利用非支配排序,結(jié)合各方結(jié)果的目標(biāo)值和擁擠度,計算出每個NN125的適應(yīng)度。最后通過二元錦標(biāo)賽選擇[15],模擬二進制交叉[15]和多項式變異[16]讓NN125種群完成一次迭代進化。經(jīng)過多代的選擇、交叉、變異等流程對NN125種群進行迭代更新,滿足迭代次數(shù)后停止進化。因為是多目標(biāo)優(yōu)化,所以最終輸出符合輸入調(diào)度任務(wù)的帕累托(Pareto)最優(yōu)調(diào)度方案集合和最優(yōu)網(wǎng)絡(luò)參數(shù)集合。

3 仿真與分析

本文使用Python作為編程語言,主要涉及的開源庫和計算機操作系統(tǒng)為Window10,設(shè)備硬件與文獻[10]相同。

為驗證調(diào)度算法性能,同時為方便復(fù)現(xiàn)本文的仿真,根據(jù)在浙江蘭溪某紡織企業(yè)的調(diào)研數(shù)據(jù),案例生成表如表2所示。

表2 案例生成表

3.1 NSGAII-NN125調(diào)度性能驗證

將本文算法NSGAII-NN125、近視算法和NSGAII_3這3種進行橫向?qū)Ρ?以此來驗證本文算法的調(diào)度性能。近視算法[3]是有明確的調(diào)度規(guī)則的一種算法,被廣泛使用在簡單的車間調(diào)度中;改進的NSGAII調(diào)度算法NSGAII_3[9],用于求解多目標(biāo)混合流水車間調(diào)度。在實際實驗中,本文均采用Python還原近視算法和NSGAII_3的調(diào)度思路。

因為本文采用多目標(biāo)求解,結(jié)果是一個解集,解集中所有個體均互不支配,即各有各的好處,但實際生產(chǎn)中必須從中選擇1個,本文按“逾期損失f1>最大完工時f2>改車次數(shù)f3”的優(yōu)先級順序選出最終用于對比的方案。

算法參數(shù)設(shè)置上,種群規(guī)模Popsize=50,最大迭代次數(shù)Maxgen=250,交叉概率Pc=0.7,變異概率Pm=0.008,γ=100。將M為6,N分別為50、100、150帶入表1,生成a組的3個案例;再將M為50,N分別為400、700、1 000生成b組的3個案例;最后將M為300,N分別為2 000、4 000、6 000生成c組的3個案例。從a組到c組需要調(diào)度的織機和織軸數(shù)量不斷增大,以此縱向?qū)Ρ群万炞C算法的性能,實驗結(jié)果如表3所示。

表3 3種算法的實驗結(jié)果統(tǒng)計

根據(jù)3種算法的仿真結(jié)果,對比逾期損失f1、最大完工時f2和改車次數(shù)f3這3個目標(biāo)值可知,在a組中,調(diào)度規(guī)模和復(fù)雜度較小,本文算法NSGAII-NN125、近視算法和NSGAII_3均能保障逾期損失f1為0;對比f2和f3不難發(fā)現(xiàn),NSGAII_3與NSGAII-NN125優(yōu)于近視算法,NSGAII-NN125和NSGAII_3的差距尚不明顯。

在b組中,織機和織軸數(shù)量較多。橫向?qū)Ρ萬1、f2和f3發(fā)現(xiàn),調(diào)度質(zhì)量上:NSGAII-NN125> NSGAII_3>近視算法。

在c組中,織機和織軸數(shù)量進一步增多,相比a組和b組,最明顯的變化是NSGAII_3調(diào)度能力急轉(zhuǎn)直下,可以判斷NSGAII_3優(yōu)化中已經(jīng)陷入局部最優(yōu)解,而NSGAII-NN125表現(xiàn)依舊領(lǐng)先,未陷入局部最優(yōu)。最后,橫向?qū)Ρ萬1、比f2和f3發(fā)現(xiàn),調(diào)度質(zhì)量上:NSGAII-NN125>近視算法> NSGAII_3。

調(diào)度耗時在算法的具體應(yīng)用中非常重要,由表3的時間對比可知,消耗時間上,NSGAII-NN125>NSGAII_3>近視算法。這是因為NSGAII-NN125不僅要進行種群的迭代進化,還要計算NN125種群的輸入特征值;而NSGAII_3只需迭代進化,近視算法規(guī)則明確、邏輯簡單,無需額外的計算。

綜上所述,NSGAII-NN125在逾期損失f1、最大完工時f2和改車次數(shù)f3這3個目標(biāo)值上明顯最優(yōu),但由于迭代進化和特征值計算,使其調(diào)度速度較慢。為提高調(diào)度速度,后文將使用已經(jīng)優(yōu)化的NN125進行調(diào)度。

3.2 已優(yōu)化調(diào)度模塊性能驗證

NSGAII-NN125由NSGAII優(yōu)化模塊和NN125調(diào)度模塊2個部分組成,且二者相互獨立,如2.3節(jié)所述,NSGAII-NN125在完成1次調(diào)度后會輸出最優(yōu)調(diào)度方案集合和最優(yōu)NN125集合。為提高NSGAII-NN125的調(diào)度速度,如果直接使用優(yōu)化過的NN125集合解決相似的問題,因為去除了NSGAII優(yōu)化模塊的優(yōu)化過程,可大大提高調(diào)度速度。

為驗證該猜想,本文設(shè)計了如下實驗。將3.1節(jié)中最后1個案例的帕累托最優(yōu)NN125集合取出,然后重新調(diào)度3.1節(jié)所有案例,結(jié)果如表4所示。通過表3、4數(shù)據(jù)對比逾期損失f1、最大完工時f2和改車次數(shù)f3這3個目標(biāo)值可知,在a組和b組中,NSGAII-NN125>NN125集合> NSGAII_3>近視算法;在c組中,NSGAII-NN125> NN125集合>近視算法> NSGAII_3。

表4 NN125集合的實驗結(jié)果統(tǒng)計

聯(lián)合表3、4對比調(diào)度耗時可知,調(diào)度消耗時間上,NSGAII-NN125> NSGAII_3> NN125集合>近視算法。可見已經(jīng)優(yōu)化過的NN125集合具有很好的速度優(yōu)勢,調(diào)度速度約為50個織軸/s。

綜上所述,NN125集合泛化效果較好,雖然調(diào)度目標(biāo)值略遜于NSGAII-NN125,但調(diào)度速度上遠(yuǎn)遠(yuǎn)優(yōu)于NSGAII-NN125,綜合考慮已優(yōu)化的調(diào)度模塊有著更好的實用價值。

4 結(jié) 論

針對織造車間調(diào)度規(guī)模較大的問題,本文結(jié)合神經(jīng)網(wǎng)絡(luò)和遺傳算法的基本原理,提出了NSGAII-NN125算法用于織造車間調(diào)度,該算法由NN125調(diào)度模塊和NSGAII優(yōu)化模塊組成。將遺傳算法的優(yōu)化參數(shù)和調(diào)度方案間用神經(jīng)網(wǎng)絡(luò)隔開,這樣需要優(yōu)化的參數(shù)個數(shù),就不會隨調(diào)度規(guī)模的增大呈指數(shù)級增加,使得遺傳算法優(yōu)化時陷入局部最優(yōu)的風(fēng)險得到規(guī)避。而且,NSGAII-NN125調(diào)度算法的輸出包含參數(shù)已被優(yōu)化的NN125集合,通過復(fù)用模型可提高實際的調(diào)度速度。

仿真實驗表明,NSGAⅡ-NN125具有較好的調(diào)度性能,以及對大規(guī)模調(diào)度問題的優(yōu)化能力。通過NSGAⅡ-NN125獲得的NN125集合,其調(diào)度質(zhì)量高、調(diào)度速度快,調(diào)度速度可達(dá)50個織軸/s,表明用NSGAⅡ-NN125優(yōu)化出的調(diào)度模塊更具實用價值。