作业车间调度规则的挖掘方法研究

王成龙，李 诚，冯毅萍，荣 冈

（工业控制国家重点实验室，浙江大学 智能系统与控制研究所，浙江 杭州310027）

生产调度是现代工业先进制造和管理的核心技术.作业车间调度问题（job shop scheduling problem，JSP），作为研究最为广泛的确定性生产调度优化问题［1］，受到了学者们的广泛关注.JSP是许多实际工业生产调度问题的简化模型，许多非工业调度问题同样可以被转化为作业车间调度问题.JSP是一种复杂的NP-hard问题，即使对于小规模的问题案例，也无法通过遍历可行解的方式获得最优解.而且，其可行解空间的规模随着案例规模的增大而呈指数形式增大.一直以来，JSP都被看作是组合优化（Combinatorial optimization）问题的典型代表.针对这一问题所开发的求解策略，可以应用于许多其它组合优化问题的求解.

目前，应用于JSP的常用优化方法包括分支定界法［2］、遗传算法［3-5］、模拟退火算法［6-7］以及禁忌搜索算法［8］等自适应搜索算法.这些方法均能成功应用于求解JSP，并能求取最优解或近似最优解.求得的优化解中往往包含着有关该调度问题的有价值的规律或知识.但这些方法的实现过程复杂，需要进行大量的参数整定工作和较长的计算时间，无法适应作业车间实时变化的作业状态.这些方法虽然能够求取最优解或是近似最优解，但却无法解释优化解是如何生成的，或是无法说明这些优化解的共同特性［9］.相反，优先调度规则（priority dispatching rules，PDR）给出了一种基于知识的调度过程决策方法.PDR往往由长期积累获得的有关调度问题的专家知识抽象而来.利用PDR指导生产调度的过程容易实现，且计算简单，并能够适应作业车间的实时变化.但传统的优先调度规则往往性能较差，无法产生较优的结果.一种新的研究思路是从利用分支定界法或是自适应搜索算法所获得的优化解中挖掘有价值的规律或知识，用以构造新的调度规则.新调度规则既具有传统PDR的优点，又能够较好地保留这些优化算法的优化能力，生成逼近最优解的较优方案.

利用由传统优化算法所获得的调度问题优化解构造新的调度规则是一种新兴的研究思路［10-11］.Koonce等［12］利用遗传算法求解一个6×6基准问题，并应用一种面向属性的归纳算法挖掘优化解中的隐含规律.所生成的规则集能较好地逼近遗传算法的调度性能，优于传统的最短时间规则（shortest processing time，SPT）.Weckman等［9］同样采用遗传算法求解JSP，并运用人工神经网络（artificial neutral network，ANN）从优化解中学习新的调度规则.Kumar等［13-14］分别将蚁群算法和禁忌搜索算法应用于生产调度问题，并利用这两种自适应搜索算法生成的优化解构造新的调度规则.

本文利用Petri网对JSP进行建模，并给出一种分支定界算法用于搜寻优化调度方案.在此基础上，提出一种基于决策树（decision tree，DT）分类技术的调度知识挖掘方法，用于挖掘隐藏在优化调度方案中的调度知识.所提取的调度知识可以直接作为新的调度规则来指导作业车间的调度过程.

1 基于Petri网的作业车间调度问题建模及优化

1.1 经典Petri网络

经典的Petri网络可以表示为4元组

许多离散事件系统需要考虑时间属性，经典Petri网同样可以描述时间信息.时间Petri网根据时间属性所处的位置分为两类：时间属性位于库所（timed place Petri net，TPPN）；时间属性位于变迁（timed transition Petri net，TTPN）.本文采用TPPN对JSP进行建模.TPPN可以表达如下：

其中γ表示当前状态下各个库所的时间参数的集合.

1.2 作业车间调度问题建模

近年来，基于Petri网的生产调度问题研究取得了广泛的关注.Petri网模型可以简洁详细地表达出调度过程的所有状态［15］，并很好地表达生产调度过程中的动态行为特性.结合其他的优化方法，Petri网建模即可用于求解生产调度问题.通过这种方式，Petri网的状态表达能力可以与传统优化方法的优化求解能力有效地结合起来，并为进一步调度知识挖掘提供有价值的调度数据，因此，Petri网建模十分有利于生产调度过程中的知识发现.

对Ghaeli等［16］提出的Petri网建模方法进行改进，得到JSP建模策略.Ghaeli等［16］利用Petri网对批调度问题进行建模.但所提出的建模方法无法表达调度任务的全部中间过程，如各加工操作的开始与结束以及加工任务的中间等待过程等.这不利于对调度过程的分析和相关调度数据的提取.在此基础上，使用如下方式建立JSP的Petri网模型.

1）对于加工工件i，其第j个加工操作o ij对应于一个库所p ij，其时间参数为γij，代表这一加工操作的加工时间；2个相邻的加工操作库所p ij和p ik之间对应于一个等待库所p ijk，代表2个相邻的加工操作之间的等待状态，其时间参数为0；加工工件i还对应于一个起始库所p is和一个终止库所p if，用于代表该加工任务的开始和结束，其时间参数均为0.这4种库所即可用于代表加工工件i的所有不同状态.

2）加工机器m对应于一个库所p m，代表一个加工资源，其时间参数为0.

3）加工操作库所p ij拥有一个输入变迁t sij和一个输出变迁t fij，分别代表加工操作的开始和结束.变迁tsij以等待库所p i（j-1）j作为输入库所，变迁t fij以等待库所p ij（j+1）作为输出库所.特别地，变迁tsi1以起始库所p is作为输入库所，变迁t fim以终止库所p if作为输出库所.按这种方式，代表同一加工工件的各个库所和变迁按加工顺序相互连接.此外，任一个加工操作开始变迁tsij对应于一个机器库所作为输入，该机器为相应的加工操作所对应的加工机器，该连接代表对机器的占用.任一个加工操作结束变迁t fij对应于一个机器库所作为输出，该机器同样为相应的加工操作所对应的加工机器，该连接代表对机器的释放.

4）每个加工工件拥有一个令牌，并在起始阶段存储于起始库所中.令牌的位置代表该加工工件的当前加工状态.此外，每个机器库所在初始时刻也拥有一个令牌.机器库所的令牌代表该加工资源的空闲状态，即该机器已经准备好进行工件的加工.

利用上述方式，即可建立JSP的TPPN模型.其中除每个表示加工操作库所的时间属性代表其对应的加工时间外，其它库所的时间属性均为0，表示资源或加工状态的直接可用性.

以表1所示的一个2×2的JSP为例，其中每个数据表格中的第一个数据表示加工操作所对应的机器，第二个数据表示加工操作的加工时间.其TPPN模型如图1所示.图1所示的调度过程处于初始状态，该初始状态可以表示为

状态矩阵M0被分解为3个子矩阵，分别代表相应的加工工件和机器的当前状态.

表1 2×2作业车间调度问题示例Tab.1 Example of 2×2 job shop scheduling problem

图1 2×2作业车间调度问题TPPN模型Fig.1 TPPN model of the 2×2 job shop scheduling problem

1.3 基于Petri网的分支定界算法

在改进一种基于Petri网的启发式搜索算法［16］的基础上，针对最小化最大完工时间（Makespan）这一性能指标，提出一种基于Petri网的分支定界算法用于求解JSP.该算法可以用于求取JSP的优化解.所求取的优化调度方案即可以用于进一步的调度知识发现.

该分支定界算法是从Petri网模型的初始状态开始，通过不断触发允许的变迁来构建可达树.可达树一个节点对应于TPPN模型的一个状态.每个节点向下的不同分支代表触发不同的变迁.可达树的所有叶节点均代表TPPN的终止状态，即代表调度加工任务的结束.因此，每一条从可达树根节点到叶节点的路径均为对应JSP问题的一个可行解.

每个可行解由从起始状态到终止状态的状态序列组成，代表作业车间的动态调度过程.对于每个非叶结点，其向下可能通过多条路径到达叶节点，即对应着多个可行解.根节点对应着整个可行解空间.分支定界算法通过不断扩展可达树来搜索最优解，其分支策略即对应于可达树的分支策略.

对于每个非叶节点M k，采用Ghaeli等［16］提出的如下公式计算其所对应的可行解集合的makespan下界：

f（Mk）为Mk对应的可行解集合的Makespan下界.

g（Mk）为当前状态Mk的生成时间即当前时刻.

h（Mk）为从当前状态Mk到达叶节点即终止状态所需时间的下限估计.其中τij表示加工任务i在机器j上的加工时间.U j（Mk）表示机器j已经运行的时间（不包括其空闲时间），而代表它的剩余运行时间.表示工件i已被加工的时间，而代表工件i总的剩余加工时间.利用式（4）得到的最大完工时间估计值满足

f*（Mk）为Mk所对应的可能的调度方案的实际Makespan.f（Mk）可作为节点Mk所对应的可行解集合的Makespan下界，用以缩小搜索规模，提高计算效率.

基于Petri网的分支定界算法的重点在于如何由当前节点通过触发变迁到达新的节点.与文献［16］中的启发式算法不同，本文结合所构建的TPPN模型特点，提出一种新的变迁触发方法用以从当前节点生成新节点.对TPPN模型分析可得，所有加工操作输出变迁不会与其他变迁发生冲突，因此可以同时触发所有允许的输出变迁.触发顺序不会对结果产生影响.而加工操作输入变迁可能会由于与其他输入变迁争夺加工资源而发生冲突.为此，本文提出如下的变迁触发策略：

1）触发所有允许的加工操作输出变迁；

2）确定当前时刻所有的可用机器库所.对于其中每个库所，可以选定一个与之相连的允许的加工操作输入变迁（不存在的则忽略不计）.这些输入变迁即可以组成一个不冲突的变迁组合.依次触发其中的变迁，可以生成一个新的状态.找出所有不冲突输入变迁组合，即可生成当前节点的所有下行节点.

利用这种新状态生成策略可以同时触发多个变迁，从而有效减少可达树的节点数，缩减可达树的规模，进一步提高计算效率.

基于Petri网的分支定界算法采用递归的方式进行.递归从TPPN的初始状态开始，并以一个较大值作为当前获得的初始最小Makespan.递归函数运算步骤如下：

1）获取当前状态Mk.

2）计算后续调度生产时间下限h（Mk），结合当前时间g（Mk），计算 Makespan下界f（Mk）.若f（Mk）大于或等于当前的最小Makespan，程序返回.

3）若Mk等于终止状态，转到步骤5）.

4）由当前状态Mk确定下一个最近的调度决策点（调度决策点为一台机器刚刚完成一个加工操作时所对应的时刻）.在该调度决策点，利用如上所述的变迁触发策略，获取一组新的状态.分别利用新的状态重新调用递归函数，程序返回.

5）分支到达最终状态，如果该分支对应的可行解的最大完工时间小于当前获得的最小Makespan，将其更新为新的最大完工时间，程序返回.

2 作业车间调度规则挖掘

2.1 目标调度模式定义

对于JSP问题，在每一个调度决策点，可能会有多个加工操作等待在同一台空闲机器上进行加工.这些加工操作之间存在冲突.在这种情况下，需要依据优化目标的要求选择一个最优加工操作在这台机器上进行下一步加工.若能对任意2个冲突加工操作进行对比，确定应先对哪个加工操作进行加工，即可通过两两对比，从所有冲突的加工操作中选出最优的加工操作.据此，定义要挖掘的目标调度模式：给定2个需要在同一台机器上进行加工的冲突加工操作（oper1和oper2），如何根据其相关信息以及相应的调度环境信息等，确定哪一个加工操作应该先进行加工.Li等［17-18］将这一调度模式定义应用于单机器调度的知识发现当中.对于JSP问题，已有的同类方法［9，12-14］往往是以如何确定任意一个加工操作在相应加工机器上的加工序号作为要挖掘的模式.这些方法所提取的调度知识无法直接用于指导作业车间调度过程，需要再结合其他已有的启发式方法.与此不同，本文所定义的目标调度模式可以作为新的调度规则直接应用于任意规模的作业车间调度问题.

目标调度模式的挖掘问题可以看成是一个分类问题.类属性取值为0或1：取1表示oper1需要先进行加工，取0表示oper2需要先进行加工.模式挖掘的目标是构建分类模型，用以根据2个冲突加工操作的对比信息以及冲突发生时的调度环境信息，确定需要对哪个加工操作进行加工.

应用较为广泛的数据挖掘分类模型包括决策树、神经网络、贝叶斯分类器以及支持向量机等.选用决策树用以表达目标调度模式.决策树是一种类似于流程图的树状结构.其中每个非树叶节点代表在一个属性上的测试，而每个树叶节点对应一个类属性标号.给定一个类属性值未知的元组，在决策树上测试该元组的属性，根据测试结果从根节点移到一个叶节点.该叶节点就存放着该元组的类属性预测值.

相对于其他分类模型，决策树具有以下优点［19］：

1）决策树模型的学习和分类过程简单且只需要极少的计算时间.而且，决策树通常能够获得很好的分类准确率.

2）决策树模型以树的形式表示所获取的模式，直观且便于理解.而且，决策树模型可以转换成更加易懂的IF-THEN规则集的形式.这有利于用户理解所获取的调度知识.

3）决策树模型的构建不需要任何领域知识，且无需进行复杂的参数整定，更具有实用性.

2.2 数据收集

归纳出代表目标调度模式的决策树分类模型，需要收集有价值的相关调度数据用于构建训练数据集.即需要用一对已知先后加工顺序的冲突加工操作的相关信息来构建一个类属性值已知的训练实例.一组这样的训练实例即可用于训练代表目标调度模式的决策树分类模型.

在TPPN建模的基础上，JSP问题的可行解空间可以表示为一棵可达树，可达树上从根节点到叶节点的每条路径代表一个可行解.在每个非叶节点处，不同分支的出现是由于加工操作输入变迁之间因争夺资源令牌而发生冲突.其实际意义为当加工机器完成上一个加工操作而闲置时，可能会有多个加工操作正在等待利用该机器进行加工，从而导致加工队列的产生.这些加工操作即为冲突的加工操作，不同的分支对应于安排不同的加工操作在该机器上进行下一步加工.

利用基于Petri网模型的分支定界算法可以求取JSP问题的优化解.该优化解对应于可达树上的一条优化状态转移路径.在优化路径的每个非叶结点处，一个优化加工操作会从一组正在争夺同一台加工机器的冲突加工操作中被选出进行下一步的加工.在该优化调度方案中，这些优化加工操作相对于与其发生冲突的其它加工操作拥有更高的加工优先级.所以，一个最优加工操作与任意一个与其发生冲突的加工操作即可以用于构建一个类属性值已知的训练元组.该最优加工操作可以被选作oper1（训练元组类属性值为1）或oper2（训练元组类属性值为0）.

以表2所示的4×4规模的作业车间调度问题为例，对应的可达树如图2所示（由于可达树的规模较大，只提取可达树的前两层作为示例）.Mij表示第i层的第j个节点，M0为根节点.加粗路径表示由分支定界算法求取的优化调度方案.图中的矩阵集表示对应节点的状态矩阵.在初始时刻，工件1、2、3的第一个加工操作需要争夺机器4，而工件4的第一个加工操作可在机器1上直接完成.工件1、2、3的第一个加工操作即为一组冲突的加工操作.在优化调度方案中，工件1优先进行加工，因此工件1的第一个加工操作即为此次冲突中的最优加工操作.在这种情况下，工件1的第一个加工操作可以分别与工件2和工件3的第一个加工操作组合构建2个类属性值已知的训练实例.

表2 4×4作业车间调度问题示例__Tab.2 Example of 4×4 job shop scheduling problem_

图2 4×4作业车间调度问题的部分可达树示例Fig.2 Partial reachability tree of 4×4 job shop scheduling problem

2.3 构造输入属性集

决策树归纳需要用一组输入属性来描述所使用的训练实例.这些输入属性需要有效地反映有关2个冲突加工操作的对比信息以及冲突发生时的调度环境信息，以便较好地预测类属性的值.构造输入属性集的目的是利用有关加工操作和加工环境的现有属性或变量，构造出一组最优的属性集以描述分类问题和最大化分类模型的分类准确率.该过程包含以下2个步骤：

1）属性创建.基于Petri网表达的优化调度方案可以提供丰富的调度数据，但这些数据中的已有属性或变量并不足以用于进行分类预测任务.对于所要挖掘的目标模式，需要用一组对比属性来描述2个冲突加工操作的比较信息.因此，需要在已有属性或变量的基础上创建新的属性.

2）属性选择.属性选择的目的是从可以获得的所有属性中选择最优的属性子集用于构建分类模型.与目标分类问题不相关或冗余的属性会影响分类模型的分类精度，而且会使最终获得的分类模型更加难以解释.

已有的用于描述一个加工操作的属性包括加工时间，等待时间及其在所对应的加工工件中的加工序号.此外，一些已有的有关时间或加工机器的信息可以用于构造描述冲突时调度环境信息的属性.根据这些已有的属性，即可以构造有关2个冲突加工操作的对比属性和相应的调度环境属性.

对于面向属性的学习算法，目前尚无有效的方法用于最优属性子集的选择［20］.采用一种后向搜索（backward search）的启发式算法确定一组较优的属性子集.后向搜索方法从整个属性集开始，每次从该属性集中选择剔除一个属性，使得剔除该属性后分类评价函数达到最优，直到满足终止条件为止.

最终获得的较优输入属性集如表4所示.Machine_Time_Ratio用于描述有关冲突发生时刻的调度环境信息，表示此次冲突对应的加工机器的剩余运行时间占总运行时间（不包括空闲时间）的比值.剩余的4个属性用于描述有关2个冲突的加工操作的对比信息.

表3 参数符号定义Tab.3 Definition of notations____________

2.4 分类模型构建

包含5个输入属性和一个二元类属性的训练实例集即可以用于决策树模型的训练.使用文献［21］中的C4.5算法构建决策树分类模型（见图3）.C4.5算法是应用最广泛的决策树归纳算法，并已被成功应用于许多分类问题中.利用C4.5算法所构建的决策树模型可以用于表达目标调度模式.给定有关2个冲突加工操作的输入属性值，利用该决策树模型可以预测应先对哪个加工操作进行加工.该决策树模型可以作为新的调度规则，用于指导作业车间调度过程.

图3 目标调度模式的决策树模型Fig.3 Decision tree model of the target scheduling pattern

表4 决策树输入属性集定义Tab.4 Input attributes for the induction of decision trees

3 实验分析

为了验证所提出的作业车间调度规则挖掘方法的可行性，利用一组随机生成的JSP案例构建训练实例集，并进一步利用所构建的训练实例集训练获得代表目标调度模式的决策树模型.在此基础上，将所构建的决策树作为新的调度规则，在一组随机生成的JSP测试案例以及一组不同规模的benchmark调度问题上进行测试.并将测试结果与传统的优先调度规则以及已有的从JSP问题的优化解中提取的新调度规则进行对比.

3.1 决策树模型构建

使用随机生成的4×4规模的JSP案例构建决策树模型.其中每个工件在不同机器上的加工顺序随机生成，各个加工操作的加工时间服从1～10的离散均匀分布.最终共构建出包括300个训练实例在内的训练集用于训练决策树模型.所构建的决策树可以转化为一组IF-THEN规则，其中部分规则如表5所示.

表5 部分IF-THEN规则示例Tab.5 Partial lists of extracted IF-THEN rules

所构建的决策树即可用于确定任意2个冲突加工操作的先后加工顺序，并作为新的调度规则指导作业车间调度过程.该决策树模型不仅可以直接用于调度决策过程，还蕴含着许多有关相应调度任务的有价值的规律.Rule1表示如果job1的剩余加工操作数≤job2的剩余加工操作数，且job1的剩余加工时间≤job2的剩余加工时间的0.2倍，且job1与job2的等待时间之差≤2，则可确定应先对job2进行加工.通过进一步分析这些挖掘出的规则可以增加对相关调度过程的理解，有利于进一步的知识发现.

3.2 实验对比1

首先使用一组随机生成的6×6规模的测试案例用于测试该决策树规则的调度性能.在测试案例中，各个加工操作的加工时间服从［5，10］之间的离散均匀分布.6×6的JSP案例同样被广泛应用于已有的从优化算法获得的优化解中提取新的调度规则的方法之中，用于验证所提取的调度规则的调度性能［9，12，14］，在不考虑截止日期（due date）的情况下，SPT规则是应用最为广泛的优先调度规则，并已证明能够在JSP上产生较为理想的调度结果［12］.因此，通过将决策树调度规则与基于Petri网的分支定界优化算法以及SPT调度规则进行对比，测试其调度性能.

表6展示了3种方法在10个6×6规模的测试案例上获得的Makespan.基于Petri网的分支定界算法可以生成所有测试案例的优化解，将这些优化解用作对比的基准.由对比结果可知，在8个测试案例中，决策树调度规则产生了优于SPT规则的调度结果.在案例8上，二者产生了相同的调度结果.仅在案例3上，SPT的调度结果优于决策树调度规则的调度结果.对比结果说明：决策树调度规则能够较好地复现基于Petri网的分支定界算法的优化调度能力，并明显优于传统的SPT调度规则.为了进一步验证决策树调度规则的泛化能力，

表6 6×6测试案例优化结果对比Tab.6 Comparison results on 6×6 test instances

现构建如下的性能参数指标：式中：Mi（best）表示在第i个测试案例上利用分支定界算法所获得的 Makespan，Mi（rule）表示由一种调度规则所获得的Makespan，n表示测试案例数.η（rule）用于表示这种调度规则相对于分支定界算法的优化调度性能度量.测试案例数n取为100，针对决策树调度规则和SPT规则的性能参数指标η计算结果如表7所示.

表7中，η（DT）和η（SPT）分别表示决策树调度规则和SPT规则的性能参数指标.η（DT）的取值仅为η（SPT）的一半左右，从而进一步说明：相对于SPT规则，所提取的决策树调度规则能够生成更加逼近于最优结果的调度方案.决策树调度规则的泛化性能得以验证.

表7 性能参数指标η计算值Tab.7 Computed results of performance indexη___

3.3 实验对比2

使用一组不同规模的benchmark调度问题进一步测试所提取的决策树调度规则的调度性能.已有学者提出一些从不同优化算法的优化解中提取新的调度规则的方法.针对最小化Makespan的JSP问题，Weckman等［9］提出的人工神经网络（neural network，NN）调度器具有优于已有的同类调度规则和传统优先调度规则的调度性能.该研究利用一个4层感知器神经网络来提取由遗传算法得到的优化解中的调度知识.结合著名的Giffler-Thomson（GT）启发式算法，训练后的神经网络可以作为新的调度规则，用于指导作业车间调度过程.因此，将所提取的决策树调度规则与NN调度规则以及传统的优先调度规则在benchmark问题上进行对比，以进一步测试其调度性能.

首先使用Fisher等［22］提出的6×6 benchmark问题ft06进行对比实验.性能参数指标η同样用于表示不同调度规则相对于分支定界算法的优化调度性能（n=1）.Weckman等［9］在该benchmark问题上将NN调度器与4种常用的优先调度规则进行对比，将所提取的决策树规则与这四种优先调度规则以及NN调度规则进行对比，结果如表8所示.对比结果显示：决策树调度规则能够生成与NN调度器相同的调度结果.决策树调度规则与NN调度器的η值远小于其它优先调度规则的η值，说明2种调度规则的调度性能均优于传统的优先调度规则.

将一组规模更大的benchmark问题用于对比决策树调度规则与NN调度器以及传统调度规则的优化调度性能，并验证决策树规则在不同规模问题上的可扩展性.这些benchmark问题包括ft10［22］、la24［23］、la36［23］、abz7［24］和 yn1［25］.这 些 benchmark问题取自不同的基准问题集，因此具有较好的代表性.Weckman等［9］同样应用这组问题集验证NN调度器的调度性能.

表8 6×6 benchmark问题上的优化结果对比Tab.8 Comparison results on 6×6 benchmark problem

对比结果如表9所示.结果显示：决策树调度规则在所有benchmark问题上的调度结果均优于NN调度器和SPT规则.决策树调度规则的η值（19.42%）远小于 NN 调度器（40.39%）及 SPT（72.64%）的η值.对比结果说明：决策树调度规则的优化调度性能优于其他规则的性能.决策树调度规则能够产生最接近已知最优解的调度结果，其在不同规模上的可扩展性也得到了验证.

表9 不同规模基准问题上的结果对比Tab.9 Comparison results on different sized benchmark________problems

相对于传统的优化算法（如：分支定界法和遗传算法），所提取的调度规则虽然无法用于求取最优解或近似最优解，但是极小的计算量和极少的计算时间就能够获得较优的调度结果.所提取的调度规则可以较好地代替传统优先调度规则.

4 结 语

本文利用时间Petri网络对作业车间调度问题进行建模，提出一种基于Petri网建模的分支定界算法，用于生成优化调度方案.在此基础上，提出一种基于决策树分类方法的作业车间调度规则挖掘方法，用于挖掘隐藏在基于Petri网模型表达的优化调度方案中的调度模式.所提取的调度模式通过决策树模型加以表达，能够预测任意2个冲突加工操作的先后加工顺序.该调度模式可作为新的调度规则，用以指导作业车间调度过程.在测试案例和benchmark问题上的实验结果表明：所提取的决策树规则优于已有的同类规则和传统的优先调度规则.

由实验结果可知，构建的规则所生成的调度结果相对于已知最优解仍存在差距.因此，在今后的工作中，需要继续研究使用新的分类技术进行目标调度模式的挖掘.此外，Petri网同样适用于其它类型调度问题的建模和优化过程.

（

）:

［1］MEERAN S，MORSHED M S.A hybrid genetic tabu search algorithm for solving job shop scheduling problems：a case study［J］.Journal of Intelligent Manufacturing，2012，23（4）：1063- 1078.

［2］BRUCKER P，JURISCH B，SIEVERS B.A branch and bound algorithm for the job-shop scheduling problem ［J］.Discrete applied mathematics，1994，49（1）：107- 127.

［3］方水良，姚嫣菲，赵诗奎.柔性车间调度的改进遗传算法［J］.浙江大学学报：工学版，2012，46（4）：629- 635.FANG Shui-liang，YAO Yan-fei，ZHAO Shi-kui.Improved genetic algorithm for flexible job shop scheduling［J］.Journal of Zhejiang University：Engineering Science，2012，46（4）：629- 635.

［4］GONCALVES J F，DE MAGALHAES MENDES J J，Resende M G C.A hybrid genetic algorithm for the job shop scheduling problem［J］.European Journal of Operational Research，2005，167（1）：77- 95.

［5］王万良，宋毅，吴启迪.求解作业车间调度问题的双倍体遗传算法与软件实现［J］.计算机集成制造系统，2004，10（1）：65- 69.WANG Wan-liang，SONG Yi，WU Qi-di.Double Chromosomes Genetic Algorithm and Its Realization for Jobshop Scheduling Problems ［J］.Computer Integrated Manufacturing Systems，2004，10（1）：65- 69.

［6］VAN LAARHOVEN P J M，AARTS E H L，Lenstra J K.Job shop scheduling by simulated annealing［J］.Operations Research，1992，40（1）：113- 125.

［7］ZHANG R，WU C.A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective［J］.Computers and Operations Research，2011，38（5）：854- 867.

［8］NOWICKI E，SMUTNICKI C.An advanced tabu search algorithm for the job shop problem ［J］.Journal of Scheduling，2005，8（2）：145- 159.

［9］WECKMAN G R，GANDURI C V，KOONCE D A.A neural network job-shop scheduler［J］.Journal of Intelligent Manufacturing，2008，19（2）：191- 201.

［10］吴启迪，乔非，李莉，等.基于数据的复杂制造过程调度［J］.自动化学报，2009，35（6）：807- 813.WU Qi-di，QIAO Fei，LI Li，et al.Data-based Scheduling for Complex Manufacturing Processes［J］.Acta Automatica Sinica，2009，35（6）：807- 813.

［11］LI L，SUN Z J，NI J C，et al.Data-based scheduling framework and adaptive dispatching rule of complex manufacturing systems［J］.The International Journal of Advanced Manufacturing Technology，2013，66（9-12）：1891- 1905.

［12］KOONCE D A，TSAI S C.Using data mining to find patterns in genetic algorithm solutions to a job shop schedule ［J］.Computers and Industrial Engineering，2000，38（3）：361- 374.

［13］KUMAR S，RAO C S P.Application of ant colony，genetic algorithm and data mining-based techniques for scheduling［J］.Robotics and Computer-Integrated Manufacturing，2009，25（6）：901- 908.

［14］SHAHZAD A，MEBARKI N.Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem ［J］.Engineering Applications of Artificial Intelligence，2012，25（6）：1173- 1181.

［15］TUNCEL G，BAYHAN G M.Applications of Petri nets in production scheduling：a review［J］.The International Journal of Advanced Manufacturing Technology，2007，34（7／8）：762- 773.

［16］GHAELI M，BAHRI P A，LEE P，et al.Petri-net based formulation and algorithm for short-term scheduling of batch plants［J］.Computers and Chemical Engineering，2005，29（2）：249- 259.

［17］LI X，OLAFSSON S.Discovering dispatching rules using data mining ［J］.Journal of Scheduling，2005，8（6）：515- 527.

［18］OLAFSSON S，Li X.Learning effective new single machine dispatching rules from optimal scheduling data［J］.International Journal of Production Economics，2010，128（1）：118- 126.

［19］HAN J，KAMBER M.Data mining：concepts and techniques［M］.2th ed.San Francisco：Morgan Kaufmann Publishers，2006：291- 310.

［20］SHIUE Y R，GUH R S.The optimization of attribute selection in decision tree-based production control systems［J］.The international journal of advanced manufacturing technology，2006，28（7／8）：737- 746.

［21］QUINLAN J R.C4.5 programs for machine learning［M］.San Francisco：Morgan Kaufmann Publishers，1993：17- 26.

［22］FISHER H，THOMPSON G L.Probabilistic learning combinations of local job-shop scheduling rules ［J］.Industrial scheduling，1963，3：225- 251.

［23］LAWRENCE S.Resource constrained project scheduling：an experimental investigation of heuristic scheduling techniques（supplement）［J］.Graduate School of Industrial Administration，Carnegie-Mellon University，Pittsburgh，Pennsylvania，1984.

［24］ADAMS J，BALAS E，ZAWACK D.The shifting bottleneck procedure for job shop scheduling ［J］.Management Science，1988，34（3）：391- 401.

［25］YAMADA T，NAKANO R.A Genetic algorithm applicable to large-scale job-shop problems［C］∥International Conference on Parallel Problem Soluing frorn Nature（PPSN）.Amsterdam：Elsevier，1992：281- 290.