基于NSGAII和神經網絡的織造車間大規模調度

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

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

隨著智能紡織的快速推進,紡織行業越來越關注織造車間智能調度問題。織造車間人員、機器、物料數量眾多,而且近年來又逐漸向多品種小批量的生產方式轉變,這導致織造車間實際的調度難度、問題復雜度和調度規模呈指數級增加,同時在織造車間實際的生產安排中,必須保證良好的調度質量和調度速度,因此,織造車間調度算法的研究是實現智能紡織較為重要的環節。

傳統調度算法中,如截止期優先調度算法[1]、近視算法[2-3]等,這些基于規則的調度算法,由于其調度邏輯是根據生產經驗抽象而來,因此,調度過程完全透明,對于具體的調度問題,結果穩定可控,而且技術門檻低,被工業生產大量應用,但算法的實現、迭代、調度的優劣非常依賴人工經驗,上限不高。

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

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

1 織造車間生產調度模型

1.1 織造車間工藝流程

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

圖1 織造車間工藝流程

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

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

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

1.2 模型描述

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

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

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

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

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

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

1.3 優化目標

為滿足織造車間精益生產的需要,同時讓多目標優化的結果更加多元,本文為織造車間調度設置如下3個優化目標。

1.3.1 最小化逾期損失

(1)

1.3.2 最小化最大完工時間

在織造車間生產中將現有任務加工完成的時間是生產的重要指標,因此,本文將最小化最大完工時間f2作為調度目標。

(2)

1.3.3 最小化改車次數

對于織機而言,平穩運行非常重要,減少改車次數不僅可以提高織機效率、減少工人的工作量,而且因為減少了使用復雜的改車工序,可以降低產品質量上的波動,所以將最小化改車次數作為優化目標。

(3)

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

2 織造車間智能調度算法

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

優化上,NSGAII作為優化模塊的核心。首先隨機生成多個NN125參數不同的調度模塊,然后根據調度結果的優劣,進行選擇、交叉和變異,經過重復迭代即可完成優化。

2.1 織軸排序

本文參考最早截止時間優先(EDF)等的思路[9,12],結合織造車間的調度特點,設計了織軸排序的規則,將織軸“織軸截止時間>織軸到達時間>織軸加工時長”的優先關系確定織軸排序。

2.2 織機選擇

2.2.1 輸入特征的設計

織軸一定時,織機的選擇成為調度的重點,為此本文設計了5個特征,作為評價織機的標準。

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

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

(4)

2.2.1.3是否改車 為更好地優化改車次數這個調度目標,本文設置了該特征,織軸選擇織機后是否需改車的表達式為:

(5)

2.2.1.4是否逾期 為更好地優化化逾期損失,本文設置了該特征。織軸選擇織機后是否會導致時間上的逾期的表達式為:

(6)

(7)

2.2.2 神經網絡設計

本文采用常規的全連接神經網絡結構,該網絡包括:輸入層、隱含層與輸出層,各層間的神經元以全連接方式連接,整個網絡為5維輸入,1維輸出,即輸入織機的5個特征數值,輸出1個評價數值。

表1示出本文的神經網絡的詳細信息。第1層為輸出層,輸入5個設計好的特征;2～5層為隱含層,結構相同,每層均為5個神經元,每個神經元有5個權重參數和1個偏置參數;第6層為輸出層。通過該表可知,此神經網絡共有125個參數,故稱其為“NN125”。用ReLU( )作為激活函數,其數學表達式為max(0,z)。

表1 NN125詳細信息

2.2.3 織機選擇流程

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

圖2 織機選擇流程

2.3 基于NSGAII的調度神經網絡優化

通過2.1節織軸排序和2.2節的織機選擇,可獲得一套完整的可細化到織機與織軸一一匹配的調度方案,但無法保證方案的優劣,又因為NN125的參數與調度結果密切相關,所以可以對NN125的參數進行優化,進而獲得良好的調度結果。

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

目前,經過眾多學者的研究,遺傳算法已經有很多優秀的版本和實現方法,本文采用帶精英保留策略的快速支配多目標遺傳算法NSGAII[14],對NN125的參數進行多目標優化。

2.3.1 決策變量的編碼和解碼

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

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

2.3.2 遺傳算法優化神經網絡

為對NN125的125個參數進行多目標優化,使用NSGAII遺傳算法優化神經網絡流程如圖3所示。

圖3 遺傳算法優化神經網絡流程

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

3 仿真與分析

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

為驗證調度算法性能,同時為方便復現本文的仿真,根據在浙江蘭溪某紡織企業的調研數據,案例生成表如表2所示。

表2 案例生成表

3.1 NSGAII-NN125調度性能驗證

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

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

算法參數設置上,種群規模Popsize=50,最大迭代次數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組需要調度的織機和織軸數量不斷增大,以此縱向對比和驗證算法的性能,實驗結果如表3所示。

表3 3種算法的實驗結果統計

根據3種算法的仿真結果,對比逾期損失f1、最大完工時f2和改車次數f3這3個目標值可知,在a組中,調度規模和復雜度較小,本文算法NSGAII-NN125、近視算法和NSGAII_3均能保障逾期損失f1為0;對比f2和f3不難發現,NSGAII_3與NSGAII-NN125優于近視算法,NSGAII-NN125和NSGAII_3的差距尚不明顯。

在b組中,織機和織軸數量較多。橫向對比f1、f2和f3發現,調度質量上:NSGAII-NN125> NSGAII_3>近視算法。

在c組中,織機和織軸數量進一步增多,相比a組和b組,最明顯的變化是NSGAII_3調度能力急轉直下,可以判斷NSGAII_3優化中已經陷入局部最優解,而NSGAII-NN125表現依舊領先,未陷入局部最優。最后,橫向對比f1、比f2和f3發現,調度質量上:NSGAII-NN125>近視算法> NSGAII_3。

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

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

3.2 已優化調度模塊性能驗證

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

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

表4 NN125集合的實驗結果統計

聯合表3、4對比調度耗時可知,調度消耗時間上,NSGAII-NN125> NSGAII_3> NN125集合>近視算法?？梢娨呀泝灮^的NN125集合具有很好的速度優勢,調度速度約為50個織軸/s。

綜上所述,NN125集合泛化效果較好,雖然調度目標值略遜于NSGAII-NN125,但調度速度上遠遠優于NSGAII-NN125,綜合考慮已優化的調度模塊有著更好的實用價值。

4 結 論

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

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