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

Dispatching rule extraction method for job shop scheduling problem

作　　者：王成龙[1] 李诚[1] 冯毅萍[1] 荣冈[1] 

机构地区：[1]工业控制国家重点实验室,浙江大学智能系统与控制研究所,浙江杭州310027

出　　处：《浙江大学学报（工学版）》2015年第3期421-429,438,共10页Journal of Zhejiang University：Engineering Science

基　　金：国家"863"高技术研究发展计划资助项目(2013AA040701)

摘　　要：针对作业车间调度问题(JSP),提出基于决策树的调度规则挖掘方法,用于从基于传统优化方法所获得的优化调度方案中提取新的调度规则,指导作业车间调度过程.将时间Petri网络用于描述作业车间的调度过程,给出基于Petri网建模的分支定界算法用于搜寻优化调度方案.结合数据挖掘中的决策树分类技术,提出一种新的调度规则挖掘方法.该方法用于提取隐藏在优化调度方案中的调度模式,并将其用作新的作业车间调度规则.针对最小化最大完工时间(makespan)性能指标,在一组测试案例和一组benchmark问题上的对比实验结果表明:相对于已有的同类调度规则和传统的优先调度规则,利用该方法所构建的决策树调度规则能够生成更小的makespan值,从而证明了该方法的可行性和有效性.A novel decision tree based approach was proposed to extract new dispatching rules from optimal schedules generated by traditional optimization methods for job shop scheduling problems（JSP）.Timed Petri net was used to formulate JSP and an improved Petri net based branch and bound algorithm was developed to generate solutions.On this basis,a novel dispatching rule extraction method was proposed to mine scheduling knowledge implicit in solutions.The extracted knowledge,formulated by a decision tree,was used as a new dispatching rule.The new dispatching rule constructed by the proposed method was tested on a set of test cases and benchmark problems for the objective of minimizing makespan of JSP.The results show that the schedules generated by the extracted rule have smaller makespans than the schedules generated by the existing dispatching rules extracted from solutions of JSP and the common priority dispatching rules,verifying the feasibility and validity of the proposed method.

关 键 词：作业车间调度 调度规则 PETRI网 数据挖掘 决策树 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]