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．
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), 2015, 49(3): 421-429.
［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. C45 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．
