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

陈雯雯，王艳红

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

0 引言

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

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

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

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

1.1 数据预处理

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