數(shù)據(jù)挖掘算法在作業(yè)車間調(diào)度問題中的應(yīng)用

王艷紅,趙也踐,劉文鑫

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

0 引言

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

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

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

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

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

1 JSSP的問題描述與數(shù)學(xué)模型

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

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

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

表1 JSSP的問題描述參數(shù)

本文采用最小化最大完工時間為性能指標(biāo),按照J(rèn)SSP的特性設(shè)定若干約束條件,其數(shù)學(xué)表達式如下:

minJ=minCiMk。

(1)

ciMk≥tiMk;

(2)

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

(3)

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

(4)

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

2 DMA提取DRs的過程分析

2.1 調(diào)度知識挖掘框架

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

2.2 決策樹算法

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

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

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

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

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

表2 常用決策樹對比

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

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

2.3 基于CART樹的DRs挖掘過程

2.3.1 CART樹的執(zhí)行過程

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

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

(5)

根據(jù)基尼系數(shù)定義得到樣本數(shù)據(jù)集U的基尼指數(shù)

(6)

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

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

Gini(U,A)=

(7)

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

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

(1)對調(diào)度數(shù)據(jù)集進行數(shù)據(jù)預(yù)處理。

(2)從調(diào)度樣本集中選出訓(xùn)練集和測試集。

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

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

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

CART樹表示DRs的流程包括數(shù)據(jù)選擇、數(shù)據(jù)預(yù)處理、建樹、剪枝。

2.3.2 數(shù)據(jù)選擇

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

表3 單機調(diào)度算例數(shù)據(jù)

2.3.3 數(shù)據(jù)預(yù)處理

采用數(shù)據(jù)預(yù)處理技術(shù)挖掘有效調(diào)度知識的前提是對歷史調(diào)度數(shù)據(jù)進行轉(zhuǎn)換,調(diào)度問題數(shù)據(jù)預(yù)處理的關(guān)鍵是確定調(diào)度樣本集的屬性標(biāo)簽和屬性類別。

為了更好地說明基于數(shù)據(jù)的DRs的產(chǎn)生過程,本節(jié)通過“權(quán)重”和“交貨期”這兩個屬性為基礎(chǔ)選擇相關(guān)的工序信息作為調(diào)度樣本集的屬性,具體如下:

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

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

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

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

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

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

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

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

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

進一步比較上述4項屬性的樣本數(shù)據(jù):

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

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

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

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

表5 數(shù)據(jù)預(yù)處理

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

2.3.4 建樹

CART樹根據(jù)“各屬性的基尼指數(shù)最小”這一標(biāo)準(zhǔn)選擇樹的決策節(jié)點,并以此建樹。在調(diào)度樣本集中,分別計算各調(diào)度屬性特征的基尼指數(shù)并進行比較,選擇各層屬性節(jié)點。

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

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

(2)假設(shè)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)分別計算各特征的基尼指數(shù),找到最優(yōu)特征和最優(yōu)切分點。

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

表6 各個特征信息

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

(8)

(9)

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

(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遠(yuǎn)小于Gini(U,A=RT)=0.47和Gini(U,A=DT)=0.485,因此取Job1_weight_higher為CART樹的根節(jié)點。繼續(xù)按照這樣的分裂規(guī)則選出其他葉子節(jié)點,直到因基尼系數(shù)為0,或者葉子節(jié)點樣本數(shù)量不足,無法再形成分支時結(jié)束分裂。以此類推,CART樹完成建樹過程。

2.3.5 剪枝

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

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

2.4 實驗仿真與結(jié)果分析

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

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

針對圖4的CART樹,其自上而下的直線箭頭方向形成的路徑便是需要描述的DRs。因為CART樹是二叉分類樹,且每個屬性值均小于等于0.5,所以真實規(guī)則的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簡單描述為,同一時刻兩道工序競爭同一臺設(shè)備時:

(1)若第1道工序的權(quán)重更大,且第1道工序在第2道工序之前提交發(fā)布,則優(yōu)先加工第1道工序。

(2)若第1道工序的權(quán)重更大,且第1道工序在第2道工序之后提交發(fā)布,則優(yōu)先加工第2道工序。

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

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

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

3 基于DMA和DRs的GA調(diào)度算法

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

3.1 基于GA的JSSP調(diào)度算法

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

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

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

(2)將所獲得的DRs嵌入GA進行調(diào)度優(yōu)化,并指導(dǎo)后續(xù)車間類似的調(diào)度問題。

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

GA-DDR調(diào)度算法的具體流程如圖5所示。

3.2 GA-DDR調(diào)度算法流程

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

3.2.1 染色體編碼

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

3.2.2 種群初始化

首先定義如下參數(shù):

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

OPmax為所有工件的最大工序數(shù)。

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

初始群體:

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

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

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

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

3.2.3 適應(yīng)度函數(shù)

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

(14)

3.2.4 遺傳操作

(1)選擇操作

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

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

(15)

(2)交叉操作

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

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

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

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

(3)變異操作

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

4 仿真研究與結(jié)果分析

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

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

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

(3)選取40個LA經(jīng)典JSSP算例進行仿真,得出相關(guān)結(jié)論,將本文算法的求解結(jié)果與其他文獻算法的求解結(jié)果進行對比,證明本文GA-DDR調(diào)度算法對求解JSSP的有效性和優(yōu)越性。

4.1 仿真環(huán)境

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

4.2 LA06算例研究

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

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

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

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

(16)

(17)

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

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

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

(1)選擇調(diào)度樣本集

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

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

(2)數(shù)據(jù)的表示

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

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

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

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

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

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

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

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

(3)構(gòu)建數(shù)據(jù)集

表12 樣本訓(xùn)練集

(4)規(guī)則調(diào)度決策樹

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

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

圖9所示為經(jīng)過多次剪枝的最佳決策樹DRs圖。

在圖9的最佳決策樹DRs中,因為CART樹是二叉分類樹,且每個屬性值均小于等于0.5,所以真實規(guī)則的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調(diào)度算法求解結(jié)果

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

表13 算例求解結(jié)果

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

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

4.4 多個LA算例研究

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

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

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

5 結(jié)束語

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