陳雯雯，王艷紅

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

0 引言

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

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

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

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

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

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

1.1.1 屬性選擇

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

1.1.2 屬性值的選擇

通過(guò)比較同一臺(tái)設(shè)備上等待加工的多道工序的PT，RPT和ROPN 3項(xiàng)數(shù)據(jù)值。例如，某時(shí)刻可加工的工序有Oij和O＇ij，根據(jù)調(diào)度數(shù)據(jù)集和歷史調(diào)度規(guī)則庫(kù)，比較其PT，RPT及ROPN 3項(xiàng)數(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)度方案為單元，按照能夠反映車(chē)間調(diào)度本質(zhì)的特征屬性劃分?jǐn)?shù)據(jù)，并轉(zhuǎn)化為適合數(shù)據(jù)挖掘的表達(dá)形式。本文對(duì)排序結(jié)果的表示為：先加工的工序記為類(lèi)別yes，后加工的工序記為類(lèi)別no。

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

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

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

因?yàn)閿?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ò)樹(shù)狀規(guī)則嵌入啟發(fā)式算法作為選擇導(dǎo)向，優(yōu)化約束了啟發(fā)式算法選擇初始種群的不確定性，降低了問(wèn)題的復(fù)雜度，提高了求解效率。HA-DDR算法設(shè)置迭代更新時(shí)間，每到迭代時(shí)間進(jìn)行一次調(diào)度規(guī)則調(diào)用，使得遺傳算法的子代種群逐漸優(yōu)化，加快得到最優(yōu)解的速度，并減少遺傳算法的總迭代次數(shù)，具體流程如圖1所示。

圖1 HA-DDR算法流程

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

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

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

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

4 結(jié)語(yǔ)

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