數據挖掘算法在作業車間調度問題中的應用

王艷紅,趙也踐,劉文鑫

(沈陽工業大學 人工智能學院,遼寧 沈陽 110870)

0 引言

車間調度在生產制造中扮演著重要的角色,一直是控制科學和制造領域的研究熱點。作業車間調度問題(Job Shop Scheduling Problem,JSSP)是車間調度領域中的經典案例,具有NP-Hard特性[1],即難以通過遍歷所有可行解來獲得最優解。傳統的JSSP優化方法分為最優化方法和近似優化方法兩大類。最優化方法能夠獲得JSSP的最優解,這類方法包括數學規劃法(mathematical programming)、分支定界法(branch and bound)和枚舉法(enumerative methods)等,然而這些方法只能求解小規模JSSP案例,隨著算例規模的不斷增大,可行解空間的規模會以指數形式增大,而遺傳算法(Genetic Algorithm,GA)[2]、粒子群優化(Particle Swarm Optimization,PSO)算法[3]等經典的近似優化方法雖然可以求取大規模JSSP的近似最優解,但是存在耗費時間更多和需要反復調參等缺陷。

隨著信息技術的發展與應用,車間在生產中積累了越來越多的離線或在線生產數據,這些數據中隱藏著大量可以反映和指導求解JSSP的調度信息,如果能夠高效利用這些生產數據,并使用某些技術提取出可靠的調度知識來提高調度算法的優化能力,則可提高作業車間的加工效率。傳統的數據處理與分析技術在處理當今海量數據時具有局限性。數據挖掘(Data Mining,DM)技術打破了這些瓶頸,使用DM技術從離線數據中獲取隱含在加工過程中的有效調度知識來分析與優化調度算法,進而指導作業車間的調度過程,成為一種求解JSSP的新思路。同時,這些調度知識能夠保留并增強原有調度算法的優化能力,生成更加接近最優解的較優調度策略,在JSSP調度過程中具有重要的意義。

從歷史生產數據中挖掘的調度知識中,調度規則(Dispatching Rules,DRs)是其一種重要的表現形式,也是在JSSP中常用的近似優化方法,其用于解決在同一時刻同一臺機器上進行加工的作業的沖突問題,并被證明是求解JSSP常用且有效方法之一[4]。DRs從長期積累的調度問題的專家知識抽象而來,但傳統的DRs性能較差,且不存在任何一個DR在不同生產場景和性能指標下優于其他規則的調度性能[5]。因此,一種基于數據挖掘算法(Data Mining Algorithm,DMA)的調度方法可以解決該問題,該方法通過從作業車間自身隱含的離線生產數據中提取若干有效的DRs嵌入GA等優化算法來求解JSSP。

HUYET等[6]開發了一種基于DM的方法來優化生產系統的設計和配置; HUYET[7]在車間調度問題上使用了相同的方法;LI等[8]介紹了一種使用數據驅動方法生成DRs的新方法,展示了通過將學習算法直接應用于生產數據并使用DMA發現以前未知DRs的詳細過程;BAYKASOGLU等[9]提出一種基于遺傳編程的DM方法來選擇DRs,以根據當前生產車間參數選擇最合適的DRs;BALASUNDARAM等[10]采用DMA中的決策樹算法從調度數據提取易于理解的特定調度規則,用來求解具有兩臺加工機器的車間調度問題;焦磊等[11]針對生產數據的特點,提出一種基于動態聚類的DM方法來挖掘DRs;林谷雨等[12]采用DMA中的決策樹學習算法發現離散車間中的調度知識;SHAHZAD等[13]為了解決元啟發式算法在求解車間調度中實時計算量較大的問題,采用決策樹離線提取車間中的if-then DRs,并將其應用到在線車間調度問題中;王成龍等[14]針對JSSP提出一種結合分支定界法和DMA中決策樹的DRs挖掘方法,該方法能夠提取隱藏在優化調度方案中的調度知識,在算例中得到了更小的完工時間;JUN等[15]為了求解動態單機調度問題,提出一種將調度轉換為包含底層調度決策的訓練數據并生成基于決策樹的DRs的方法,實驗表明,在最小化平均總加權延遲這一性能指標下,該方法優于其他調度規則。

從以上文獻可見,目前在JSSP中使用DMA挖掘DRs并優化調度算法的研究還比較少。本文以JSSP為研究對象,以最小化最大完工時間為性能指標,提出一種基于DMA的JSSP調度框架,來挖掘歷史生產數據中的調度知識(即DRs),進一步建立了該數據框架下面向改進GA的JSSP調度優化算法。所提取的DRs能夠進一步優化調度算法,改善調度算法性能。最后通過計算機仿真實驗驗證了所提調度算法的有效性。

1 JSSP的問題描述與數學模型

在JSSP中,設有n個待加工工件J={J1,J2,…,Ji,…,Jn}需要在m臺機器M={M1,M2,…,Mg,…,Mm}上加工。每個工件Ji要經過ni道不同的加工順序,已知各工序的加工時間和Ji在各機器上的加工次序約束。JSSP的任務目標是,明確為各個工件的每一道工序選擇合適的加工機器,確定其開始加工時間以及每一臺機器上工件的加工順序,從而使調度結果滿足預期的性能指標。

為了簡化當前的JSSP,本文設定如下約束:①所有的機器準備時間為0,即所有工件到達機器后都能立即開始加工;②按照加工工藝規定,每道工序必須在其之前工序加工完成后方可開始加工;③各個工件必須按照工藝路線以指定的次序在機器上加工,而且假定不同工件之間具有相同的優先權;④每一時刻每臺機器只能加工一個工件,某一時刻每個工件只能被一臺機器加工;⑤工序一旦開始加工不可中斷;⑥前一個操作未完成,后面的操作需要等待;⑦各工件的準備時間和完成時間一起計入加工時間。

在問題描述中涉及的參數如表1所示。

表1 JSSP的問題描述參數

本文采用最小化最大完工時間為性能指標,按照JSSP的特性設定若干約束條件,其數學表達式如下:

minJ=minCiMk。

(1)

ciMk≥tiMk;

(2)

ciMk-tiMk+β(1-aiMhMk)≥ciMh;

(3)

clMk-ciMk+β(1-bilMk)≥tlMk。

(4)

其中:式(1)表示性能指標為最小化最大完工時間;式(2)表示Ji在Mk上的完工時間CiMk不能小于其加工時間tiMk;式(3)表示工件Ji的前后兩道相鄰工序在機器Mh和Mk上加工的順序約束,且當Mh先于Mk加工Ji時,aiMhMk=1,否則aiMhMk=0;式(4)表示機器Mk完成一個加工任務后才能開始另一個加工任務,且當Ji先于Jl在Mk上加工時,bilMk=1,否則bilMk=0。β表示一個具有很小正值常數的調節因子。

2 DMA提取DRs的過程分析

2.1 調度知識挖掘框架

本文主要研究的是,針對JSSP的數學模型、作業車間的相關屬性以及不同類別的算例(每個算例的工件數量、機器數量和每個工件的工序數量不同)挖掘以DRs的形式存在的特定調度知識。挖掘到的DRs并非一成不變,而是隨算例或車間實例的增加不斷豐富,使逐漸形成的DRs庫適用于更多的JSSP案例。因此本文提出一種使用歷史調度數據框架挖掘DRs的方法。圖1所示為調度知識挖掘框架結構圖,其中DMA能夠揭示調度數據中隱藏的、用于進一步強化調度決策的調度知識。

2.2 決策樹算法

決策樹是構建決策模型時常用的方法,其由節點和葉子組成,有關參數值的決策在節點進行。決策樹通過逐層決策,最終使樹的底部葉子形成某些特定的類別。

決策樹包括ID3算法、C4.5算法和分類回歸樹(Classification And Regression Tree,CART)算法等。在以往使用DMA求解JSSP的研究中,ID3算法和C4.5算法雖然是主流求解工具,但是存在如下弊端:

(1)ID3算法利用信息增益作為決策樹選擇屬性的依據,其通用性強,適合大多數分類問題,且建樹思路簡單,成為DM技術領域中頗有影響的算法之一。該算法的主要缺點是不能處理連續型樣本屬性和存在缺失值的樣本集,因此出現了C4.5算法。

(2)C4.5算法采用信息增益率選擇屬性作為決策樹的節點,增加了剪枝和處理連續型數據等功能,不足之處是只能求解分類問題,不能求解回歸問題。另外,C4.5算法生成的可視化決策樹屬于多叉樹,許多情況下計算機對多叉樹的求解效率相對較低,因此設計了基于二叉樹的CART算法來解決這些問題。

CART算法所生成的決策樹的任意節點有且僅有兩個分枝結果,該決策樹被稱為CART二叉分類樹(以下簡稱CART樹),其目的是減小樹的深度,加快計算機的處理速度,因此被廣泛應用于求解各類分類問題和回歸問題。表2對這3種常用的決策樹從算法結構、剪枝效果及擴展性進行了比較。

表2 常用決策樹對比

JSSP中包括很多工件或機器的相關屬性,每個工件的各種屬性都具有一定相關性,例如工件的加工時間屬性有長和短兩種關系,交貨期屬性也有提交的早或晚等關系,符合CART樹的特點,因此本文選取CART樹對DRs進行挖掘。

CART樹的根節點是所有樣本中基尼指數最小的屬性,在根節點以下所有子樹包含的中間節點均在樣本數據子集中利用基尼不純度最小化原理構建形成,樣本訓練集的類別值構成了CART樹的葉子節點。CART樹的結構如圖2所示。

2.3 基于CART樹的DRs挖掘過程

2.3.1 CART樹的執行過程

CART樹通過計算基尼不純度系數來確定屬性劃分點,數據集所含的信息量采用基尼不純度系數來衡量[16]。

假設有K個類別,樣本點屬于第k個類的概率為Pk,則概率分布的基尼不純度系數的數學公式為

(5)

根據基尼系數定義得到樣本數據集U的基尼指數

(6)

式中Ik為U中屬于第k類的樣本子集。

如果U根據特征A在某一取值a上進行分割,得到U1和U2兩部分,則在特征A下集合U的基尼系數為

Gini(U,A)=

(7)

式中:基尼系數Gini(U)表示從U中隨機抽取兩個樣本,其類別標記不同的概率,其值越小,U的純度越高,分支越好;基尼系數Gini(U,A)表示A=a分割后集合U的不純度。

將CART樹挖掘DRs的詳細步驟進行如下描述,具體的算法流程如圖3所示:

(1)對調度數據集進行數據預處理。

(2)從調度樣本集中選出訓練集和測試集。

(3)在訓練集中運用CART樹,選擇基尼指數最小的屬性作為樹的根節點。

(4)在根節點的基礎上,按照基尼指數最小化原理,將其他屬性作為根節點之下的葉子節點并繼續分類,依次遞歸成樹圖。若訓練集中僅剩一個分類類別,則不再分裂。

(5)將(4)得到的DRs運用到測試集中,觀察調度結果是否存在偏差,是則對CART樹進行剪枝,重復(5),直到每個測試子集調度結果與測試集基本相同。

CART樹表示DRs的流程包括數據選擇、數據預處理、建樹、剪枝。

2.3.2 數據選擇

數據選擇過程一般選擇作業車間中的實際生產案例作為對挖掘有利的調度樣本集。本節的調度樣本集選自文獻[17]中“10個工件在1臺機器上加工”的單機調度案例(單機調度問題中的10個工件視為10道工序),如表3所示。

表3 單機調度算例數據

2.3.3 數據預處理

采用數據預處理技術挖掘有效調度知識的前提是對歷史調度數據進行轉換,調度問題數據預處理的關鍵是確定調度樣本集的屬性標簽和屬性類別。

為了更好地說明基于數據的DRs的產生過程,本節通過“權重”和“交貨期”這兩個屬性為基礎選擇相關的工序信息作為調度樣本集的屬性,具體如下:

(1)提交時間(Release Time,RT) 表示某道工序(若為單機調度,則表示為某個工件,余同)可以加工的最早時間。

(2)交貨期(Due Time,DT) 表示某道工序完成加工的最后期限。

(3)加工時間(Processing Time,PT) 表示某道工序在機器上加工的時間。

(4)權重(Weight,W) 表示某道工序相對于其他工序的重要性。

首先,對以上4個屬性的初始值進行離散化。對于機器M可同時加工的兩個工件,分別比較4個屬性值,將所得結果作為樣本集的屬性。依次比較10個任務的屬性,預處理后得到以下4個新屬性:

(1)Job1_release_earlier 同一機器上的兩道工序誰的提交時間更早。

(2)Job1_due_earlier 同一機器上的兩道工序誰的交貨期更早。

(3)Job1_weight_higher 同一機器上的兩道工序誰的權重更大。

(4)Job1_processing_lower 同一機器上的兩道工序誰的加工時間更短。

進一步比較上述4項屬性的樣本數據:

(1)對于Job1_release_earlier,Job1_due_earlier,Job1_processing_lower 3個屬性,任意兩個工件對比后(每次對比的第1個工件記為Job1,第2個記為Job2),第1個工件屬性數值較小的記為1,數值較大的記為0,Job1_weight_higher則相反。若出現屬性數據相等的情況(如表4的Weight屬性),則全部記為1。

(2)對于加工序列屬性,將優先加工的工序用Job1_first表示(該類別簡記為1),后加工的工序用others_first表示(該類別簡記為0)。

以表3中的一部分工件數據為例,用表4說明Job1_release_earlier的由來,其他3個屬性標簽的生成同理。

表4中,No.1表示表3單機調度算例中的”Job索引”為1。根據表3的算例數據,共有10個工件,每2個工件需要一一對比4個屬性數據,得到45組數據,結合上述數據預處理以及表3中的“加工序列”這一列,得到該算例數據預處理表,如表5所示。

表5 數據預處理

表5中,No.1表示表3中的Job索引為1;該表為45組對比數據,限于篇幅,省略其余組數據;Job1_first為0的情況實際上對應others_first類別。

2.3.4 建樹

CART樹根據“各屬性的基尼指數最小”這一標準選擇樹的決策節點,并以此建樹。在調度樣本集中,分別計算各調度屬性特征的基尼指數并進行比較,選擇各層屬性節點。

表5中有Job1_release_earlier,Job1_due_earlier,Job1_processing_lower,Job1_weight_higher 4個屬性,以及Job1_first的1和0兩個類別。有如下假設:

(1)假設4個屬性依次為特征RT,DT,PT,W。

(2)假設RT1,DT1,PT1,W1分別為特征RT,DT,PT,W為1的情況,RT2,DT2,PT2,W2分別為特征RT,DT,PT,W為0的情況;同理,F1為類別Job1_first為1的情況,F2為類別Job1_first為0(others_first為1)的情況。

(3)分別計算各特征的基尼指數,找到最優特征和最優切分點。

由表3算例樣本集及表5的調度結果數據預處理可知,在表5中的45個樣本中,有25個類別Job1_first為1的正例和20個類別Job1_first為0的負例,即F1為25,F2為20;在特征RT處取值為1的例子有32個,即RT1為32,取值為0的例子有13個,即RT2為13。得知特征RT的真正例有20個,假真例有12個,真負例有5個,假負例有8個。同理得到其他特征的這些信息,各特征詳情如表6所示。

表6 各個特征信息

根據表6,結合式(6)求出RT1所屬集合U1和RT2所屬集合U2的基尼指數分別為:

(8)

(9)

再由式(7)求得特征RT的基尼指數

(10)

同理可得:

Gini(U,A=DT)=0.485;

(11)

Gini(U,A=PT)=0.48;

(12)

Gini(U,A=W)=0.432。

(13)

由此可知,Gini(U,A=W)=0.432遠小于Gini(U,A=RT)=0.47和Gini(U,A=DT)=0.485,因此取Job1_weight_higher為CART樹的根節點。繼續按照這樣的分裂規則選出其他葉子節點,直到因基尼系數為0,或者葉子節點樣本數量不足,無法再形成分支時結束分裂。以此類推,CART樹完成建樹過程。

2.3.5 剪枝

CART樹對訓練集進行測試時很容易產生過擬合,導致泛化能力變差。在對JSSP算例進行數據挖掘后,會挖掘出一個包含若干DRs的初始DRs庫,因為有些DRs或者冗余或者已存在,所以這些DRs并不會改善調度問題的求解精度,反而會浪費系統資源。因此,很有必要對CART樹進行剪枝,這一過程與線性回歸的正則化表達相似。CART樹的剪枝是“測試集對現有生成樹加以剪枝并挑選出最優樹集”的過程,一般將“損失函數最小化”作為決策樹剪枝的原則。決策樹剪枝的方法有預剪枝和后剪枝,CART樹采用后剪枝,其過程是先從訓練集生成一棵完整的決策樹,再自底向上檢驗非葉子節點。若將該節點對應的子樹替換為該節點能提高樹的性能,則用該節點替換該節點對應的子樹。

決策樹剪枝中不僅看特征的基尼系數是否為0或者小于一定的閾值,還需要關注決策樹的最大深度max_depth、內部節點再劃分所需的最小樣本數min_samples_split、葉子節點最少樣本數min_samples_leaf、最大葉子節點數max_leaf_nodes等參數。

2.4 實驗仿真與結果分析

為了驗證以上關于挖掘DRs理論的可行性,現以表4中的單機調度算例為例,用CART樹挖掘隱藏的DRs。仿真實驗在加速頻率為2.20 GHz的Inteli5-4500U處理器、運行內存為4 GB的Windows 7 PC平臺進行,采用Python程序編寫,編譯環境為Python Jupyter,編譯器版本為Python 3.7.3。仿真程序是通過網格搜索法對CART樹進行多次剪枝,直到仿真出的樹狀規則滿足調度樣本測試集的加工順序,程序中DecisionTreeClassifier模塊的各參數為max_depth=3,min_samples_split=9,min_samples_leaf=8,max_leaf_nodes=5。經過39.973 s運行,剪枝完的CART樹狀規則圖如圖4所示,從而得到最終的決策樹。

在表4中,由2.3.3節可知,Job1_weight_higher和Job1_due_earlier兩個屬性特征尤為重要。由圖4同樣可知,CART樹狀規則圖的根節點屬性為Job1_weight_higher,與2.3.4節求得的結果相同,而且根節點的基尼不純度指數也與公式演算出的相同。從圖4可知,CART樹第1層節點的屬性為Job1_due_earlier和Job1_release_earlier,最后才是Job1_processing_lower,進一步證實了CART樹在求解基于DMA的JSSP的有效性和準確性。

針對圖4的CART樹,其自上而下的直線箭頭方向形成的路徑便是需要描述的DRs。因為CART樹是二叉分類樹,且每個屬性值均小于等于0.5,所以真實規則的True和False正好相反,得到如下DRs:

(1)If Job1_weight_higher=True and Job1_release_earlier=True,Then Job1_first=True。

(2)If Job1_weight_higher=True and Job1_release_earlier=False,Then Job1_first=False(others_first=True)。

(3)If Job1_weight_higher=False and Job1_due_earlier=False,Then Job1_first=False(others_first=True)。

(4)If Job1_weight_higher=False and Job1_due_earlier=True and Job1_processing_lower=True,Then Job1_first=True。

(5)If Job1_weight_higher=False and Job1_due_earlier=True and Job1_processing_lower=False,Then Job1_first=False(others_first=True)。

以上5條DRs簡單描述為,同一時刻兩道工序競爭同一臺設備時:

(1)若第1道工序的權重更大,且第1道工序在第2道工序之前提交發布,則優先加工第1道工序。

(2)若第1道工序的權重更大,且第1道工序在第2道工序之后提交發布,則優先加工第2道工序。

(3)若第1道工序的權重更小,且第1道工序在第2道工序之后完工交貨,則優先加工第2道工序。

(4)若第1道工序的權重更小,且第1道工序在第2道工序之前完工交貨,第1道工序的加工時間更短,則優先加工第1道工序。

(5)若第1道工序的權重更小,且第1道工序在第2道工序之前完工交貨,第1道工序的加工時間更長,則優先加工第2道工序。

3 基于DMA和DRs的GA調度算法

為了驗證CART樹挖掘出的DRs的有效性,本文提出一種基于DMA的改進GA調度算法。同時,來自車間的數據也可以用作訓練樣本或測試樣本,以創建新的DRs或修改現有的DRs。

3.1 基于GA的JSSP調度算法

GA是在1975年由Holland等專家基于生物有機體的遺傳過程提出的一種優化方法,可用于解決NP-Hard優化問題。以往研究曾用“強方法”和“弱方法”來描述各種優化算法與待求解問題的相關性?；镜腉A屬于一種通用算法,因此被劃為“弱方法”,在求解某些實際問題時,需要將GA轉化為“強方法“來提高求解效率,同時獲得更好的求解質量。因此在JSSP中,可以在GA中嵌入DRs來對基本GA進行改進,使其成為專門求解JSSP的改進GA調度算法,該算法在解決組合優化生產調度問題等NP-Hard問題的效果十分顯著。

在基于數據的調度框架基礎上,本文將CART樹直接應用于歷史生產數據,通過數據挖掘發現新的DRs,再將由系統積累數據獲取的DRs同GA結合,進行DRs優化,提出一種基于DMA和DRs的GA調度算法(Genetic Algorithm based on Data-mining and Dispatching Rules,GA-DDR)。該算法是在基本GA的基礎上嵌入通過DMA獲得的DRs來進行全局優化,有助于加快算法的求解速度和收斂速度。GA-DDR調度算法的步驟為:

(1)采用CART樹得到未知的新型DRs。

(2)將所獲得的DRs嵌入GA進行調度優化,并指導后續車間類似的調度問題。

這樣使GA的子代種群逐漸優化,加快了得到最優解的速度,并減少了GA的總迭代次數。

GA-DDR調度算法的具體流程如圖5所示。

3.2 GA-DDR調度算法流程

GA-DDR調度算法由染色體編碼、種群初始化、適應度函數、遺傳操作(選擇、交叉和變異)等步驟組成。

3.2.1 染色體編碼

本文采用基于工序的基因編碼表示個體,一組編碼代表一種可行的加工方案。例如,一組工序碼為“1 2 4 3 4 3 1 2 2 4 3 1 3 2 4 1”,每個數字表示待加工的工件序號,同一數字第幾次出現表示對應工件的第幾道工序,例如第1個“4”表示4號工件的第1道工序,即O41。

3.2.2 種群初始化

首先定義如下參數:

Nij為第i個工件第j道工序的加工機器編號;

OPmax為所有工件的最大工序數。

由此可知,N是一個n×OPmax的矩陣,即Nn×OPmax為機器順序陣。

初始群體:

(1)先計算“待加工工件“在CART樹中的根節點屬性值,再從其最大或最小集合中選取一個工件i(比較根節點的屬性值后,比較下一節點的屬性值,直至比較完畢),得到Ni1。

(2)Nig=Ni(g+1),r=OPmax-1,NiOPmax=0。

(3)如果N的所有元素均為0,則結束,否則轉(1)。

至此,DRs與GA完成結合,并得到基于DRs的初始種群群體。該初始種群基于DRs定義并生成,所有新個體的生成均基于該方法完成。

3.2.3 適應度函數

本文的性能指標為“最小化最大完工時間”,相當于求問題f(x)的最小值。為了方便算法選擇更接近目標函數值的下一代個體,可以使目標函數值與一個隨機數的和的倒數作為個體的適應度值,這種適應度函數會明顯增強不同個體之間的差異,進而加快收斂速度。設i為個體x對應的解,Cmin為個體x對應的完工時間最小值,則個體x對應的適應度函數

(14)

3.2.4 遺傳操作

(1)選擇操作

選擇時以適應值為選擇原則,通過適應度函數進行評估。具體過程為在種群繁殖階段,從種群中隨機選擇個體進行重組產生后代,這些后代構成下一代;然后從群體中隨機選擇兩個父代,通過交叉變異產生更健康的個體繼續繁殖。

本文采用輪盤賭法選擇個體,計算公式為

(15)

(2)交叉操作

本文采用擴展后的多點交叉法進行交叉操作,具體過程如下:

1)選取兩組染色體序列P1和P2。

2)隨機產生一個隨機數s,比較s與pc,如果pc>s,則進行正常的多點交叉操作,將父代P1和P2的基因段互換,記對換基因個數點為g;如果pcs,執行3)。

3)令g=g+1,重復步驟2),直到g等于多點交叉總對換基因的個數,生成新的子代C1和C2。

(3)變異操作

變異是通過替換個體染色體上的某些基因形成新個體來保證種群多樣性。本文采用“動態改變變異概率”(根據適應度值決定變異概率)隨機交換選中個體上兩個位置的基因,然后判斷相對應的工件工序是否滿足工序條件,滿足則進行變異操作,否則重新調整染色體上的基因位置。

4 仿真研究與結果分析

本文的實驗仿真分為3部分:

(1)為了初步展現GA-DDR調度算法在求解JSSP上的邏輯性,選取“15個工件在5臺機器上加工”的LA06算例進行研究,將所得結果與不包含DMA和DRs的基本GA算法求解JSSP的結果進行比較,分析兩種算法在收斂性方面的差異并得出初步結論,為其他實驗提供理論依據。

(2)為了進一步驗證GA-DDR調度算法的有效性,先對LA01算例的加工數據進行數據預處理、選擇屬性標簽、數據挖掘等操作,獲得新的樹狀DRs,進而形成GA-DDR調度算法,用該算法求解LA11,LA17,LA24,LA26,LA33,為后續其他大量的測試算例做準備。

(3)選取40個LA經典JSSP算例進行仿真,得出相關結論,將本文算法的求解結果與其他文獻算法的求解結果進行對比,證明本文GA-DDR調度算法對求解JSSP的有效性和優越性。

4.1 仿真環境

本節仿真實驗在加速頻率為2.20 GHz的Intel i5-4500U處理器、運行內存為4 GB的Windows 7 PC平臺進行,采用Python語言編寫,編譯環境為Python Jupyter,編譯器版本為Python 3.7.3。為使本文的GA-DDR調度算法效果最佳,經過多次仿真測試,GA的實驗參數中設種群規模為150,交叉概率初始為0.6,變異概率初始為0.02(程序中第1次交叉變異概率取值為0.6和0.02,后續為動態變化),終止迭代次數為800。

4.2 LA06算例研究

本節GA-DDR調度算法中嵌入的DRs是類似于2.4節“If Job1_weight_higher=True and Job1_release_earlier=True,then Job1_first=True”的DR。因為性能指標為“最小化最大完工時間”,所以某一工序的加工時間Processing Time屬性尤為重要,因此本節采用“If Job1_processing_lower=True, then Job1_first=True”這一DR對GA進行更新優化。

表7所示為LA06算例的工藝順序約束和加工時間,例如第1行數據表示工件1先在機器2上加工21個單位時間,然后在機器3上加工34個單位時間,再在機器5上加工95個單位時間,以此類推,最后在機器4上加工55個單位時間。

表7 LA06(15×5)的工件加工信息

由表7可得該算例的機器約束矩陣Tm和加工時間矩陣Tt,機器約束矩陣的轉置矩陣

(16)

(17)

GA-DDR調度算法和基本GA分別求解LA06算例獲得的最大完工時間收斂曲線對比如圖6所示?？梢?GA-DDR調度算法和基本GA最優調度的最大完工時間均為926個單位時間,但GA-DDR調度算法僅需73代便可以獲得實驗的最優解,而未嵌入DRs的基本GA在第157代才獲得最優解,說明嵌入DRs后,原算法的收斂性大幅度增強,進一步提高了性能。因此GA-DDR調度算法具有較強的搜索能力,具備求解JSSP的能力。

4.3 LA11,LA17,LA24,LA26,LA33算例研究

首先采用LA01(10×5)算例作為調度數據集,通過挖掘LA01算例得到相應的DRs,將挖掘的DRs庫應用到LA11(20×5),LA17(10×10),LA24(15×10),LA26(20×10),LA33(30×10)的大規模算例中驗證GA-DDR調度算法的有效性。

(1)選擇調度樣本集

基于CART樹的DRs提取步驟如下:①選擇表8所示的LA01作為待挖掘調度數據;②對靜態的調度數據集進行數據挖掘;③將挖掘的DRs應用到基本GA中,進一步求解JSSP。以上3個步驟組成了“DRs挖掘,調度優化,車間管理”的調度過程。

表8 LA01(10×5)的工件加工信息

(2)數據的表示

根據表8所示的LA01算例中的加工數據、工藝約束和“最小化最大完工時間”性能指標,選取常規的加工時間最短優先(Shortest Processing Time first,SPT)、剩余總加工時間最短優先(Least Work Remaining first,LWR)和總剩余工序數最少優先(Least Operations Remaining first,LOR)3個DRs組成算例歷史DRs庫,從而確定屬性、屬性值和類別值,如表9所示。

表9 屬性、屬性值和類別值

對于在同一臺設備上等待加工的多道工序,分別比較其PT,RPT,ROPN的屬性值,再經過預處理后,得到如下新屬性:

1)Job_pt_longer 同一機器上兩個任務的兩道工序誰的加工時間更長。

2)Job_rpt_longer 同一機器上兩個任務的兩道工序誰的剩余加工時間更長。

3)Job_ropn_more 同一機器上兩個任務的兩道工序誰的剩余工序數更多。

表10 O21和O51的加工信息示例

表11 O21和O51的加工信息離散化處理

(3)構建數據集

表12 樣本訓練集

(4)規則調度決策樹

將表12的樣本訓練集讀取到Python jupyter編譯環境下。首先,將其按4∶1分為訓練集和測試集(train_size=0.8);其次,在樣本訓練集中運用CART樹生成CART樹狀DRs,將生成的DRs應用到測試集,觀察該規則是否滿足測試集,滿足則該DRs庫為本算例需要的DRs庫,否則根據網格搜索法對此時的CART樹進行后剪枝,直到生成的規則滿足測試集,此時挖掘出的便是最佳DRs。圖7所示為未經剪枝的決策樹DRs圖。

為了更加具體地展示圖7所示決策樹的形成過程,給出基于Python語言的決策樹生成的程序代碼,如圖8所示。

圖9所示為經過多次剪枝的最佳決策樹DRs圖。

在圖9的最佳決策樹DRs中,因為CART樹是二叉分類樹,且每個屬性值均小于等于0.5,所以真實規則的True和False正好相反,得到以下組合DRs:

1)If Job_rpt_longer=True, then Job_Oi1=yes(工序1先加工)。

2)If Job_rpt_longer=False and Job_ropn_more=False,then Job_Oi1=yes。

3)If Job_rpt_longer=False and Job_ropn_more=True and Job_rpt_longer=False,then Job_Oi1=yes。

4)If Job_rpt_longer=False and Job_ropn_more=True and Job_rpt_longer=True,then Job_Oi1=no(工序1后加工)。

為了更加具體地展示圖9所示的剪枝后決策樹的形成過程,給出基于Python語言的剪枝后決策樹生成程序代碼,如圖10所示。

(5)GA-DDR調度算法求解結果

在挖掘出DRs的基礎上,將上述DRs嵌入GA,便可得到本文所提GA-DDR調度算法。對LA11,LA17,LA24,LA26,LA33應用該算法,并與基本GA的仿真計算結果進行比較,結果如表13所示。圖11～圖15所示分別為5個算例基于GA-DDR調度算法的調度結果以及各個算例中GA-DDR調度算法和基本GA的最優解收斂曲線對比。

表13 算例求解結果

從圖11～圖15和表13可見,相比基本GA,GA-DDR調度算法均較早求解出了JSSP的最優解。因此在嵌入挖掘出的DRs后,基本GA的求解速度大幅度增強,收斂性也獲得了提高,進一步證明了使用GA-DDR調度算法在求解較大規模JSSP中具有切實的可行性和高效性。

為了更加直觀地展示GA-DDR調度算法的生成過程,給出基于Python語言的GA-DDR調度算法的程序代碼,如圖16所示。

4.4 多個LA算例研究

為了進一步驗證GA-DDR調度算法的普適性和準確性,本節用多個Benchmark實例對該算法進行驗證,并采用從LA01算例中挖掘出的DRs。種群大小設置為200,每個算例用本文改進算法運行20次,算例結果取最優值,其中大部分算例僅需要迭代300次～500次,少部分算例需要迭代500次以上。

本文將GA-DDR調度算法與基于混合遺傳算法(Hybrid Genetic Algorithm,HGA)的調度算法[18]、基于粒子群優化(Particle Swarm Optimization,PSO)算法的調度算法[19]、GA(RM&COVERT)調度算法[20]和基于數據挖掘的DMA(data mining approach)調度算法[21]的仿真結果進行比較,如表14所示。

由表14可知,在實例規模較小的LA01～LA20中,各算法結果相差無幾;當實例為規模相對復雜的LA21～LA40時,GA-DDR調度算法在大部分實例上的最大完工時間優于其他算法,其可以在搜索空間快速找到最優區域。由此得出結論:本文所提GA-DDR調度算法充分結合了DMA和GA的優勢,即在基本GA的基礎上嵌入挖掘出的DRs,從而增強了調度算法的搜索能力,并在求解質量和收斂性上均具有優勢。

5 結束語

本文針對作業車間的生產數據具有離散性、多樣性、復雜性和隱蔽性等特點,采用DMA中的CART樹挖掘DRs作為有效的調度知識構建調度DRs庫。在實施過程中,本文所提GA-DDR調度算法能夠在不同JSSP實例中挖掘出不同的樹狀DRs,再將其與GA結合來求解更復雜的JSSP,并通過仿真實驗測試證明了所提調度算法的有效性。未來擬進一步研究具有機器隨機發生故障、多目標優化的JSSP及柔性車間的DRs提取等方面的問題,以提升調度算法的求解精度和收斂性等。