基于決策樹挖掘技術(shù)的調(diào)度算法研究

陳雯雯，王艷紅

（沈陽工業(yè)大學 人工智能學院，遼寧 沈陽 110870）

0 引言

作業(yè)車間調(diào)度問題(Job Shop Scheduling Problem，JSP）是對實際作業(yè)車間優(yōu)化調(diào)度問題的簡化模型。然而在大規(guī)模作業(yè)車間調(diào)度中，計算效率和實際操作能力普遍偏低，以至于工業(yè)界和學術(shù)界迫切想要改善這類問題。可行的改進方案是從調(diào)度相關(guān)的歷史數(shù)據(jù)中挖掘調(diào)度規(guī)則(Dispatching Rules，DRs），并應(yīng)用到作業(yè)車間調(diào)度活動中。

Zahmani等［1］提出了一種結(jié)合調(diào)度規(guī)則、遺傳算法、數(shù)據(jù)挖掘和仿真的新方法，實時為機器分配不同的調(diào)度規(guī)則。Wang等［2］提出一種通過決策樹挖掘出最佳的調(diào)度規(guī)則，神經(jīng)網(wǎng)絡(luò)準確預(yù)測調(diào)度規(guī)則性能的方法。韓松來等［3］提出了一種通過屬性的關(guān)聯(lián)度函數(shù)值作為決策樹算法的屬性選取標準。李廣霞等［4］提出一種基于遺傳算法的多決策樹融合研究，具有更高的分類精度。劉民［5］對基于數(shù)據(jù)的生產(chǎn)過程調(diào)度問題做了進一步研究，主要包括生產(chǎn)過程調(diào)度問題建模和優(yōu)化方法兩部分。

從現(xiàn)有成果來看，研究者們普遍使用決策樹的二叉樹挖掘調(diào)度規(guī)則，并完全按照歷史調(diào)度規(guī)則庫選取屬性、屬性值，這會忽略數(shù)據(jù)中更為關(guān)鍵的調(diào)度信息。為使數(shù)據(jù)挖掘技術(shù)更適應(yīng)實際大規(guī)模作業(yè)車間調(diào)度，應(yīng)充分考慮分類屬性、屬性值的選取問題。為此，本文提出一種針對大規(guī)模作業(yè)車間調(diào)度問題的調(diào)度規(guī)則挖掘改進方法。

1 基于決策樹挖掘調(diào)度規(guī)則的算法設(shè)計

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

本文提出了一種應(yīng)用于作業(yè)車間調(diào)度問題的數(shù)據(jù)挖掘技術(shù)的預(yù)處理方法，包括屬性選擇、確定屬性值、數(shù)據(jù)整合3個部分。

1.1.1 屬性選擇

本文提出一種以最大完工時間最小化為性能指標作為屬性選擇依據(jù)，SPT，LWR，LOR 3種規(guī)則作為屬性選擇標準的比較方法。在同一臺設(shè)備上等待加工的多道工序中，分別比較PT(加工時間）、RPT(剩余加工時間）和ROPN(剩余工序）3項數(shù)據(jù)值，得到Job＿pt，Job＿rpt和Job＿ropn 3個新的屬性。

1.1.2 屬性值的選擇

通過比較同一臺設(shè)備上等待加工的多道工序的PT，RPT和ROPN 3項數(shù)據(jù)值。例如，某時刻可加工的工序有Oij和O＇ij，根據(jù)調(diào)度數(shù)據(jù)集和歷史調(diào)度規(guī)則庫，比較其PT，RPT及ROPN 3項數(shù)據(jù)值。若Oij的PT值大于O＇ij的PT值，則Job＿pt屬性值記為yes；若Oij的PT值等于O＇ij的PT值，則Job＿pt屬性值記為equal；若Oij的PT值小于O＇ij的PT值，則Job＿pt屬性值記為no。

1.1.3 數(shù)據(jù)整合

數(shù)據(jù)整合的目的是以最優(yōu)調(diào)度方案為單元，按照能夠反映車間調(diào)度本質(zhì)的特征屬性劃分數(shù)據(jù)，并轉(zhuǎn)化為適合數(shù)據(jù)挖掘的表達形式。本文對排序結(jié)果的表示為：先加工的工序記為類別yes，后加工的工序記為類別no。

1.2 基于C4.5算法創(chuàng)建決策樹

C4.5算法是一種挖掘車間數(shù)據(jù)的經(jīng)典決策樹算法。在經(jīng)過數(shù)據(jù)預(yù)處理后的數(shù)據(jù)集中，C4.5算法計算屬性的信息增益率(information Gain Ratio），進行遞歸運算，得到初步?jīng)Q策樹。C4.5算法生成的初步?jīng)Q策樹需要采用后剪枝算法剪枝。本文采用悲觀錯誤剪枝法(PEP）對決策樹自上而下剪枝。通過多次剪枝計算形成最佳決策樹模型，根據(jù)建立最佳的模型生成一系列IF-THEN規(guī)則，實現(xiàn)對數(shù)據(jù)集的分類。

2 調(diào)度規(guī)則優(yōu)化算法設(shè)計

因為數(shù)據(jù)挖掘出的調(diào)度規(guī)則搜索次數(shù)少，容易造成局部最優(yōu)，需要優(yōu)化調(diào)度，所以本文提出一種基于數(shù)據(jù)挖掘技術(shù)和調(diào)度規(guī)則的啟發(fā)式算法(Heuristic Algorithm Based on Data-mining and Dispatching Rules，HA-DDR）。在HA-DDR算法中，通過樹狀規(guī)則嵌入啟發(fā)式算法作為選擇導(dǎo)向，優(yōu)化約束了啟發(fā)式算法選擇初始種群的不確定性，降低了問題的復(fù)雜度，提高了求解效率。HA-DDR算法設(shè)置迭代更新時間，每到迭代時間進行一次調(diào)度規(guī)則調(diào)用，使得遺傳算法的子代種群逐漸優(yōu)化，加快得到最優(yōu)解的速度，并減少遺傳算法的總迭代次數(shù)，具體流程如圖1所示。

圖1 HA-DDR算法流程

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

為了驗證上述改進HA-DDR算法解決JSP的有效性，將LA01(10×5）作為測試算例，生成C4.5樹狀調(diào)度規(guī)則，將生成的規(guī)則進行PEP剪枝算法剪枝。如圖2所示為經(jīng)過多次剪枝的最佳決策樹規(guī)則，將其嵌入遺傳算法，針對LA06算例，HA-DDR算法與傳統(tǒng)遺傳算法(Genetic Algorithm，GA）的收斂性對比如圖3所示。

圖2 決策樹剪枝后規(guī)則

圖3 算例LA06的HA-DDR和GA收斂性對比

4 結(jié)語

本文在傳統(tǒng)調(diào)度規(guī)則、數(shù)據(jù)挖掘、遺傳算法相結(jié)合的作業(yè)車間調(diào)度方法的基礎(chǔ)上，從數(shù)據(jù)挖掘的屬性、屬性值的選取方面進行了改進，所設(shè)計的嵌套進C4.5多叉樹規(guī)則的遺傳優(yōu)化算法能夠快速處理加工時間相等、剩余加工時間相等、剩余工序相等的情況，縮小了算法的初始種群搜索范圍，使算法具有較強的尋優(yōu)速度和能力。