基于决策树挖掘技术的调度算法研究

陈雯雯，王艳红

（沈阳工业大学 人工智能学院，辽宁 沈阳 110870）

0 引言

作业车间调度问题(Job Shop Scheduling Problem，JSP）是对实际作业车间优化调度问题的简化模型。然而在大规模作业车间调度中，计算效率和实际操作能力普遍偏低，以至于工业界和学术界迫切想要改善这类问题。可行的改进方案是从调度相关的历史数据中挖掘调度规则(Dispatching Rules，DRs），并应用到作业车间调度活动中。

Zahmani等［1］提出了一种结合调度规则、遗传算法、数据挖掘和仿真的新方法，实时为机器分配不同的调度规则。Wang等［2］提出一种通过决策树挖掘出最佳的调度规则，神经网络准确预测调度规则性能的方法。韩松来等［3］提出了一种通过属性的关联度函数值作为决策树算法的属性选取标准。李广霞等［4］提出一种基于遗传算法的多决策树融合研究，具有更高的分类精度。刘民［5］对基于数据的生产过程调度问题做了进一步研究，主要包括生产过程调度问题建模和优化方法两部分。

从现有成果来看，研究者们普遍使用决策树的二叉树挖掘调度规则，并完全按照历史调度规则库选取属性、属性值，这会忽略数据中更为关键的调度信息。为使数据挖掘技术更适应实际大规模作业车间调度，应充分考虑分类属性、属性值的选取问题。为此，本文提出一种针对大规模作业车间调度问题的调度规则挖掘改进方法。

1 基于决策树挖掘调度规则的算法设计

1.1 数据预处理

本文提出了一种应用于作业车间调度问题的数据挖掘技术的预处理方法，包括属性选择、确定属性值、数据整合3个部分。

1.1.1 属性选择

本文提出一种以最大完工时间最小化为性能指标作为属性选择依据，SPT，LWR，LOR 3种规则作为属性选择标准的比较方法。在同一台设备上等待加工的多道工序中，分别比较PT(加工时间）、RPT(剩余加工时间）和ROPN(剩余工序）3项数据值，得到Job＿pt，Job＿rpt和Job＿ropn 3个新的属性。

1.1.2 属性值的选择

通过比较同一台设备上等待加工的多道工序的PT，RPT和ROPN 3项数据值。例如，某时刻可加工的工序有Oij和O＇ij，根据调度数据集和历史调度规则库，比较其PT，RPT及ROPN 3项数据值。若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 数据整合

数据整合的目的是以最优调度方案为单元，按照能够反映车间调度本质的特征属性划分数据，并转化为适合数据挖掘的表达形式。本文对排序结果的表示为：先加工的工序记为类别yes，后加工的工序记为类别no。

1.2 基于C4.5算法创建决策树

C4.5算法是一种挖掘车间数据的经典决策树算法。在经过数据预处理后的数据集中，C4.5算法计算属性的信息增益率(information Gain Ratio），进行递归运算，得到初步决策树。C4.5算法生成的初步决策树需要采用后剪枝算法剪枝。本文采用悲观错误剪枝法(PEP）对决策树自上而下剪枝。通过多次剪枝计算形成最佳决策树模型，根据建立最佳的模型生成一系列IF-THEN规则，实现对数据集的分类。

2 调度规则优化算法设计

因为数据挖掘出的调度规则搜索次数少，容易造成局部最优，需要优化调度，所以本文提出一种基于数据挖掘技术和调度规则的启发式算法(Heuristic Algorithm Based on Data-mining and Dispatching Rules，HA-DDR）。在HA-DDR算法中，通过树状规则嵌入启发式算法作为选择导向，优化约束了启发式算法选择初始种群的不确定性，降低了问题的复杂度，提高了求解效率。HA-DDR算法设置迭代更新时间，每到迭代时间进行一次调度规则调用，使得遗传算法的子代种群逐渐优化，加快得到最优解的速度，并减少遗传算法的总迭代次数，具体流程如图1所示。

图1 HA-DDR算法流程

3 仿真研究与结果分析

为了验证上述改进HA-DDR算法解决JSP的有效性，将LA01(10×5）作为测试算例，生成C4.5树状调度规则，将生成的规则进行PEP剪枝算法剪枝。如图2所示为经过多次剪枝的最佳决策树规则，将其嵌入遗传算法，针对LA06算例，HA-DDR算法与传统遗传算法(Genetic Algorithm，GA）的收敛性对比如图3所示。

图2 决策树剪枝后规则

图3 算例LA06的HA-DDR和GA收敛性对比

4 结语

本文在传统调度规则、数据挖掘、遗传算法相结合的作业车间调度方法的基础上，从数据挖掘的属性、属性值的选取方面进行了改进，所设计的嵌套进C4.5多叉树规则的遗传优化算法能够快速处理加工时间相等、剩余加工时间相等、剩余工序相等的情况，缩小了算法的初始种群搜索范围，使算法具有较强的寻优速度和能力。