The dispatching rule is an effective tool for solving the dynamic job shop scheduling problem in practical productions. However, no single rule can outperform others under various scheduling circumstances, as the effectiveness of the dispatching rule depends on the shop configurations, the operating conditions and the performance measures. To study the dynamic job shop scheduling problem in practical productions, the methods for the development and the design of dispatching rules are reviewed in this paper. The development, the classification and the characteristics of dispatching rules are discussed, and the research hotspots of dispatching rules and the design methods are summarized. The design methods of dispatching rules include the popular manually performed method and the effective artificial intelligence method. In addition, the research results and the conclusions of the evolutionary algorithm, the genetic programming and the data mining methods for the design of dispatching rules are presented. The advantages and disadvantages of these methods are analyzed and compared. Finally the direction of future researches is pointed out.
[1] Gere W S. Heuristics in job shop scheduling[J]. Management Science, 1966, 13(3): 167-190.
[2] Haupt R. A survey of priority rule-based scheduling[J]. Operations Re-search Spektrum, 1989, 11(1): 3-16.
[3] Panwalker S S, Iskandar W. A survey of scheduling rules[J]. Operations Research, 1977, 25(1): 45-61.
[4] 张超勇. 基于自然启发式算法的作业车间调度问题理论与应用研究[D]. 武汉: 华中科技大学, 2006. Zhang Chaoyong. A heuristic-based research for the theory and applica-tion of Job shop scheduling problem[D]. Wuhan: Huazhong University of Science and Technology, 2006.
[5] 刑文训, 谢金星. 现代优化计算方法[M]. 北京: 清华大学出版社, 2001, Xing Wenxun, Xie Jinxing. Modern optimization and computing method[M]. Beijing: Tsinghua University Press, 2001.
[6] Glover F, Greenberg H J. New approaches for heuristic search: A bilat-eral linkage with artificial intelligence[J]. European Journal of Opera-tions Research, 1989, 39 (2): 119-130.
[7] Blackstone J H, Phillips D T, Hogg G L. A state-of-the-art survey of dispatching rules for manufacturing job shop operations[J]. International Journal of Production Research, 1982, 20(1): 27-45.
[8] Oliver H, Chandrasekharan R. Efficient dispatching rules for schedul-ing in a job shop[J]. International Journal of Production Economics, 1997, 48(1): 87-105.
[9] Ramasesh R. Dynamic job shop scheduling: A survey of simulation re-search[J]. Omega, 1990, 18(1): 43-57.
[10] Grady O P, Lee K H. An intelligent cell control system for automated manufacturing[J]. International Journal of Production Research, 1988, 26(5): 845-861.
[11] Pierreval H. Expert system for selecting priority rules in flexible manu-facturing systems[J]. Expert Systems with Applications, 1992, 5(1-2): 51-57.
[12] Pierreval H, Mebarki N. A real-time scheduling approach based on a dynamic selection of dispatching rules[J]. International Journal of Pro-duction Research, 1997, 35(6): 1575-1591.
[13] Baker K R, Bertrand J W M. A dynamic priority rule for scheduling against due-dates[J]. Journal of operations management, 1982, 3(1): 37-42.
[14] Conway R W, Maxwell W L, Miller L W. Theory of scheduling[M]. Ad-dison-Wesley, Reading, MA, 1967.
[15] Baker K R, Kennet J J. Job shop scheduling with modified due dates [J]. Operations Management, 1983, 4(1): 11-22.
[16] 范华丽, 熊禾根, 钱国洁, 等. 工序松弛规则及其在动态Job Shop调度问题中的应用仿真研究[J]. 制造业自动化. 2015, 37(3): 61-64. Fan Huali, Xiong Hegen, Qian Guojie, et al. Research on Slack-of-op-eration rule and the simulation of its application in dynamic job shop scheduling problem[J]. Manufacturing Automation, 2015, 37(3): 61-64.
[17] Chen B, Matis T I. A flexible dispatching rule for minimizing tardi-ness in job shop scheduling[J]. International Journal of Production Re-search, 2013, 141(1): 360-365.
[18] Raghu T S, Rajendran C. An efficient dynamic dispatching rule for scheduling in a job shop[J]. International Journal of Production Eco-nomics, 1993, 32(3): 301-313.
[19] Atabakhsh H. A survey of constraint based scheduling systems using an artificial intelligence approach[J]. Artificial Intelligence in Engi-neering, 1991, 6(2): 58-73.
[20] Aytug H, Bhattacharyya S, Koehler G J, et al. A review of machine learning in scheduling[J]. IEEE Transactions on Engineering Manage-ment, 1994, 41(2): 165-171.
[21] Priore P, De La Fuente, D Go'mez, et al. A review of machine learn-ing in dynamic scheduling of flexible manufacturing systems[J]. Artifi-cial Intelligence for Engineering Design Analysis and Manufacturing, 2001, 15(3): 251-263.
[22] Eiben A E, Smith J E. Introduction to evolutionary computing[D]. 1st ed. Berlin/Heidelberg: Natural Computing Springer, 2003.
[23] Branke J, Pickardt C W. Evolutionary search for difficult problem in-stances to support the design of job shop dispatching rules[J]. Europe-an Journal of Operations Research, 2011, 212 (1): 22-32.
[24] Rajendran C, Holthaus O. A comparative study of dispatching rules in dynamic flowshops and jobshops[J]. European Journal of Operational Research, 1999, 116(1): 156-170.
[25] Koza J. Genetic programming: On the programming of computers by means of natural selection[M]. Cambridge, MA: MIT Press, 1992.
[26] Dimopoulos C, Zalzala A M S. Investigating the use of genetic pro-gramming for a classic one-machine scheduling problem[J]. Advances in Engineering Software, 2001, 32(6): 489-498.
[27] Geiger C D, Uzsoy R, Aytug H. Rapid modeling and discovery of prior-ity dispatching rules: An autonomous learning approach[J]. Journal of Scheduling, 2006, 9(1): 7-34.
[28] Geiger C D, Uzsoy R. Learning effective dispatching rules for batch processor scheduling[J]. International Journal of Production Research, 2008, 46(6): 1431-1454.
[29] Tay J C, Ho N B. Evolving dispatching rules using genetic program-ming for solving multi-objective flexible job-shop problems[J]. Com-puters and Industrial Engineering, 2008, 54(3): 453-473.
[30] Kusiak A. Data mining: Manufacturing and service applications[J]. In-ternational Journal of Production Research, 2006, 44(18): 4175-4191.
[31] Harding J A. Data mining in manufacturing: A review [J]. Journal of Manufacturing Science and Engineering, 2006, 128(4): 969-976.
[32] Li X, Olafsson S. Learning effective new single machine dispatching rules from optimal scheduling data[J]. International Journal of Produc-tion Research, 2010, 128(1): 118-126.
[33] Koonce D A, Tsai S C. Using data mining to find patterns in genetic algorithm solution to a job shop schedule[J]. Computers and Industrial Engineering, 2000, 38(3): 361-374.
[34] Nooml H A, Radha R T. A bicriterian flow shop scheduling using arti-ficial neural network[J]. International Journal of Advanced Manufactur-ing Technology, 2006, 30(11-12): 1132-1138.
[35] Saravanan M, Noorrul H A, Vivek raj A R, et al. Performance evalua-tion of the scatter search method for permutation flow shop sequenc-ing problems[J]. International Journal of Advanced Manufacturing Technology, 2008, 37(11-12): 1200-1208.
[36] 王尧. 基于数据挖掘的Job-Shop 调度规则研究[J]. 江苏科技信息, 2010, 12: 49-51. Wang Yao. A data mining-based research of dispatching rules in Job-Shop scheduling[J]. Jiangsu Science & Technology Information, 2010, 12: 49-51.
[37] Shahzad A, Mebarki N. Data mining based job shop dispatching using hybrid simulation-optimization approach for shop scheduling problem [J]. Engineering Applications of Artificial Intelligence, 2012, 25(6): 1173-1181.
