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)   HTML
摘要：

 针对作业车间调度问题（JSP）,提出基于决策树的调度规则挖掘方法,用于从基于传统优化方法所获得的优化调度方案中提取新的调度规则,指导作业车间调度过程. 将时间Petri网络用于描述作业车间的调度过程,给出基于Petri网建模的分支定界算法用于搜寻优化调度方案. 结合数据挖掘中的决策树分类技术,提出一种新的调度规则挖掘方法.该方法用于提取隐藏在优化调度方案中的调度模式,并将其用作新的作业车间调度规则. 针对最小化最大完工时间（Makespan）性能指标,在一组测试案例和一组Benchmark问题上的对比实验结果表明：相对于已有的同类调度规则和传统的优先调度规则,利用该方法所构建的决策树调度规则能够生成更小的Makespan值,从而证明了该方法的可行性和有效性．
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．
出版日期: 2015-08-28
:  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/eng/CN/10.3785/j.issn.1008-973X.2015.03.005    或    http://www.zjujournals.com/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] 朱东阳, 沈静逸, 黄炜平, 梁军. 基于主动学习和加权支持向量机的工业故障识别[J]. 浙江大学学报(工学版), 2017, 51(4): 697-705.
[2] 丰小月, 梁艳春, 林希珣, 管仁初. 永恒语言学习研究与发展[J]. 浙江大学学报(工学版), 2017, 51(1): 82-88.
[3] 裘日辉, 刘康玲, 谭海龙, 梁军. 基于极限学习机的分类算法及在故障识别中的应用[J]. 浙江大学学报(工学版), 2016, 50(10): 1965-1972.
[4] 冀瑜,邱清盈,冯培恩,黄浩. 国际专利分类表中设计知识的提取和利用[J]. 浙江大学学报(工学版), 2016, 50(3): 412-418.
[5] 居斌, 钱沄涛, 叶敏超. 基于结构投影非负矩阵分解的协同过滤算法[J]. 浙江大学学报(工学版), 2015, 49(7): 1319-1325.
[6] 王国芳, 方舟, 李平. 基于批量递归最小二乘的自然Actor-Critic算法[J]. 浙江大学学报(工学版), 2015, 49(7): 1335-1342.
[7] 谭海龙, 刘康玲, 金鑫, 石向荣, 梁军. 基于μσ-DWC特征和树结构M-SVM的多维时间序列分类[J]. 浙江大学学报(工学版), 2015, 49(6): 1061-1069.
[8] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[9] 王立军,黄忠朝,赵于前. 基于超像素分割的空间相关主题模型及场景分类方法[J]. 浙江大学学报(工学版), 2015, 49(3): 402-408.
[10] 於俊,汪增福. 基于经验模式分解和多种评价准则的电子稳像[J]. J4, 2014, 48(3): 423-429.
[11] 刘业峰，徐冠群，潘全科，柴天佑. 磁性材料成型烧结生产调度优化方法及应用[J]. J4, 2013, 47(9): 1517-1523.
[12] 林亦宁, 韦巍, 戴渊明. 半监督Hough Forest跟踪算法[J]. J4, 2013, 47(6): 977-983.
[13] 郝钏钏, 方舟, 李平. 基于参考模型的输出反馈强化学习控制[J]. J4, 2013, 47(3): 409-414.
[14] 汪鹏君, 王振海, 陈耀武, 李辉. 固定极性Reed-Muller电路最佳延时极性搜索[J]. J4, 2013, 47(2): 361-366.
[15] 李侃,黄文雄,黄忠华. 基于支持向量机的多传感器探测目标分类方法[J]. J4, 2013, 47(1): 15-22.