Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机技术﹑电信技术     
作业车间调度规则的挖掘方法研究
王成龙,李诚,冯毅萍,荣冈
工业控制国家重点实验室, 浙江大学 智能系统与控制研究所, 浙江 杭州 310027
Dispatching rule extraction method for job shop scheduling problem
WANG Cheng-long, LI Cheng, FENG Yi-ping, RONG Gang
State Key Laboratory of Industrial Control Technology, Institute of Cyber-systems and Control, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1081 KB)  
摘要：

 针对作业车间调度问题（JSP）,提出基于决策树的调度规则挖掘方法,用于从基于传统优化方法所获得的优化调度方案中提取新的调度规则,指导作业车间调度过程. 将时间Petri网络用于描述作业车间的调度过程,给出基于Petri网建模的分支定界算法用于搜寻优化调度方案. 结合数据挖掘中的决策树分类技术,提出一种新的调度规则挖掘方法.该方法用于提取隐藏在优化调度方案中的调度模式,并将其用作新的作业车间调度规则. 针对最小化最大完工时间（Makespan）性能指标,在一组测试案例和一组Benchmark问题上的对比实验结果表明：相对于已有的同类调度规则和传统的优先调度规则,利用该方法所构建的决策树调度规则能够生成更小的Makespan值,从而证明了该方法的可行性和有效性．
关键词： 调度规则;  Petri网;  数据挖掘;  作业车间调度;  决策树    
Abstract:

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．
Key words: Petri net    decision tree    dispatching rule    job shop scheduling    data mining
出版日期: 2015-04-12
:  TP 18  
基金资助:

国家“863”高技术研究发展计划资助项目（2013AA040701）
通讯作者: 荣冈，男，教授     E-mail: grong@iipc.zju.edu.cn
作者简介: 王成龙(1991-)，男，硕士生，从事数据挖掘在工业调度中的应用研究. E-mail: wangchenglong@iipc.zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
李诚
荣冈
王成龙
冯毅萍

引用本文:

王成龙,李诚,冯毅萍,荣冈. 作业车间调度规则的挖掘方法研究[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2015.03.005.

WANG Cheng-long, LI Cheng, FENG Yi-ping, RONG Gang. Dispatching rule extraction method for job shop scheduling problem. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2015.03.005.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2015.03.005    或    http://www.zjujournals.com/xueshu/eng/CN/Y2015/V49/I3/421

［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): 10631-078．
［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 Job- shop 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．
[1] 许荣斌, 石军, 张鹏飞, 谢莹. Petri网的映射变迁关系相似性度量[J]. 浙江大学学报(工学版), 2017, 51(6): 1205-1213.
[2] 王青, 温李庆, 李江雄, 柯映林, 李涛, 张世炯. 基于Petri网的飞机总装配生产线建模及优化方法[J]. 浙江大学学报(工学版), 2015, 49(7): 1224-1231.
[3] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[4] 何智翔, 丁晓青, 方驰, 文迪. 基于LBP和CCS-AdaBoost的多视角人脸检测[J]. J4, 2013, 47(4): 622-629.
[5] 徐姗姗, 董利达, 朱丹, 朱承丞. S4PR网的极小信标计算方法[J]. J4, 2013, 47(3): 431-441.
[6] 罗继亮, 王飞,邵辉,赵良煦. 基于约束转换的Petri网最优监控器设计[J]. J4, 2013, 47(11): 2051-2056.
[7] 王相兵,童水光,钟崴,张健. 基于可拓重用的液压挖掘机结构性能方案设计[J]. J4, 2013, 47(11): 1992-2002.
[8] 张建明, 谢磊, 毛婧敏, 董方. 基于离散量子微粒群优化的作业车间调度[J]. J4, 2012, 46(5): 842-847.
[9] 宣琦, 吴铁军. 复杂open shop问题的网络模型及
调度规则设计[J]. J4, 2011, 45(6): 961-968.
[10] 王云, 冯毅雄, 谭建荣, 高一聪. 柔性作业车间分批调度多目标优化方法[J]. J4, 2011, 45(4): 719-726.
[11] 刘晓健,张树有,徐敬华. 基于网络流Petri网模型的设计更改技术[J]. J4, 2011, 45(1): 37-44.
[12] 董利达, 程曦浩, 郑寒. 基于工作流的安全库所替换网特性研究[J]. J4, 2010, 44(9): 1711-1718.
[13] 周晓慧, 陈纯, 谢作豪. 印染生产过程的仿真和优化[J]. J4, 2010, 44(7): 1377-1381.
[14] 董利达, 郑寒, 程曦浩. 一类含T-图环结构受控网显式控制器设计[J]. J4, 2010, 44(6): 1057-1066.
[15] 韩凝, 张秀英, 王小明, 陈利苏, 王珂. 高分辨率影像香榧树分布信息提取[J]. J4, 2010, 44(3): 420-425.