Dispatching rule extraction method for job shop scheduling problem

doi:10.3785/j.issn.1008-973X.2015.03.005

JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)

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

Download:

PDF(1081KB) HTML
Export: BibTeX | EndNote (RIS)

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．

Published: 28 August 2015

CLC:

TP 18

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors

Cite this article:

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.

URL:

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

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

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

［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]	ZHU Dong-yang, SHEN Jing-yi, HUANG Wei-ping, LIANG Jun. Fault classification based on modified active learning and weighted SVM[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(4): 697-705.

[2]	FENG Xiao yue, LIANG Yan chun, LIN Xi xun, GUAN Ren chu. Research and development of never-ending language learning[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(1): 82-88.

[3]	QIU Ri hui, LIU Kang ling, TAN Hai long, LIANG Jun. Classification algorithm based on extreme learning machine and its application in fault identification of Tennessee Eastman process[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(10): 1965-1972.

[4]	JI Yu,QIU Qing ying,FENG Pei en,HUANG Hao. Extraction and utilization of design knowledge in international patent classification[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(3): 412-418.

[5]	JU Bin, QIAN Yun-tao, YE Min-chao. Collaborative filtering algorithm based on structured projective nonnegative matrix factorization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(7): 1319-1325.

[6]	WANG Guo-fang, FANG Zhou, LI Ping. Natural Actor-Critic based on batch recursive least-squares[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(7): 1335-1342.

[7]	TAN Hailong, LIU Kangling, JIN Xin, SHI Xiang rong, LIANG Jun. Multivariate time series classification based on μσ-DWC feature and tree-structured M-SVM[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(6): 1061-1069.

[8]	MIAO Feng, XIE An-huan, WANG Fu-an, YU Feng, ZHOU Hua. Method for multi-stage alternative grouping parallel machines scheduling problem[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(5): 866-872.

[9]	WANG Li-jun, HUANG Zhong-chao, ZHAO Yu-qian. New spatial-coherent latent topic model based on super-pixel segmentation and scene classification method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(3): 402-408.

[10]	YU Jun, WANG Zeng-fu. Video stabilization based on empirical mode decomposition and several evaluation criterions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2014, 48(3): 423-429.

[11]	LIU Ye-feng, XU Guan-qun, PAN Quan-ke, CHAI Tian-you. Magnetic material molding sintering production scheduling optimization method and its application[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(9): 1517-1523.

[12]	LIN Yi-ning, WEI Wei, DAI Yuan-ming. Semi-supervised Hough Forest tracking method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(6): 977-983.

[13]	HAO Chuan-chuan, FANG Zhou, LI Ping. Output feedback reinforcement learning control method based on reference model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(3): 409-414.

[14]	WANG Peng-jun, WANG Zhen-hai, CHEN Yao-wu, LI Hui. Searching the best polarity for fixed polarity Reed-Muller circuits based on delay model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(2): 361-366.

[15]	LI Kan, HUANG Wen-xiong, HUANG Zhong-hua. Multi-sensor detected object classification method based on support vector machine[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2013, 47(1): 15-22.

Viewed

Full text

Abstract

Cited

Shared

Discussed