基于決策樹挖掘技術的調度算法研究

陳雯雯，王艷紅

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

0 引言

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

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

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

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

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

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

1.1.1 屬性選擇

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

1.1.2 屬性值的選擇

通過比較同一臺設備上等待加工的多道工序的PT，RPT和ROPN 3項數(shù)據(jù)值。例如，某時刻可加工的工序有Oij和O＇ij，根據(jù)調度數(shù)據(jù)集和歷史調度規(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)調度方案為單元，按照能夠反映車間調度本質的特征屬性劃分數(shù)據(jù)，并轉化為適合數(shù)據(jù)挖掘的表達形式。本文對排序結果的表示為：先加工的工序記為類別yes，后加工的工序記為類別no。

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

C4.5算法是一種挖掘車間數(shù)據(jù)的經(jīng)典決策樹算法。在經(jīng)過數(shù)據(jù)預處理后的數(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 調度規(guī)則優(yōu)化算法設計

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

圖1 HA-DDR算法流程

3 仿真研究與結果分析

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

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

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

4 結語

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