Automatic Discovery Method of Dynamic Job Shop Dispatching Rules Based on Hyper-Heuristic Genetic Programming

doi:10.16182/j.issn1004731x.joss.20-FZ0452

Abstract

Abstract: The dynamic job shop has the uncertainty of resource state and the randomness of tasks,so it is difficult to find the common dispatching rules applicable to a variety of complex production scenarios.A method for automatic discovery of dynamic shop dispatching rules based on Hyper-Heuristic genetic programming is proposed,with makespan and average weighted tardiness as the optimization goals,is improved by using the automatic discovery of machine sequencing rules and the dynamic adaptability of workshop scheduling under different production scenarios.Through the semantic analysis of dispatching rules,the function of terminators on different optimization objectives is analyzed.The experiment result shows that the proposed algorithm can effectively generate appropriate dispatching rules which is obviously better than the manual designed benchmark rules for different production scenarios.

Key words: genetic programming, dynamic job shop, dispatching rules, automatic discover

CLC Number:

TP391.9

Zhang Suyu, Wang Yan, Ji Zhicheng. Automatic Discovery Method of Dynamic Job Shop Dispatching Rules Based on Hyper-Heuristic Genetic Programming[J]. Journal of System Simulation, 2020, 32(12): 2494-2506.

References 31

[1]	Pickardt C W,Hildebrandt T,Branke J,et al.Evolutionary Generation of Dispatching Rule Sets for Complex Dynamic Scheduling Problems[J].International Journal of Production Economics (S0925-5273),2013,145(1):67-77.
[2]	Lourenco H R.Job-shop Scheduling:Computational Study of Local Search and Large-Step Optimization Methods[J].European Journal of Operational Research (S0377-2217),1995,83(2):347-364.
[3]	Balas E,Simonetti N,Vazacopoulos A.Job Shop Scheduling with Setup Times,Deadlines and Precedence Constraints[J].Journal of Scheduling (S1094-6136),2008,11(4):253-262.
[4]	Kundakci N,Kulak O.Hybrid Genetic Algorithms for Minimizing Makespan in Dynamic Job Shop Scheduling Problem[J].Computers &Industrial Engineering (S0360-8352),2016,96(6):31-51.
[5]	Branke J,Nguyen S,Pickardt C W,et al.Automated Design of Production Scheduling Heuristics:A Review[J].IEEE Transactions on Evolutionary Computation (S1089-778X),2016,20(1):110-124.
[6]	Tay J C,Ho N B.Evolving Dispatching Rules Using Genetic Programming for Solving Multi-Objective Flexible Job-shop Problems[J].Computers &Industrial Engineering (S0360-8352),2008,54(3):453-473.
[7]	Fan H L,Xiong H G,Jiang G Z,et al.Generation of Dispatching Rules for Dynamic Job Shop Scheduling Problem Based on Genetic Programming Algorithm[J].Computer Integrated Manufacturing Systems (S1006-5911),2018,24(4):876-885.
[8]	Jayamohan M S,Rajendran C.Development and Analysis of Cost-Based Dispatching Rules for Job Shop Scheduling[J].European Journal of Operational Research (S0377-2217),2004,157(2):307-321.
[9]	Kanet J J,Li X.A Weighted Modified Due Date Rule for Sequencing to Minimize Weighted Tardiness[J].Journal of Scheduling (S1094-6136),2004,7(4):261-276.
[10]	Burke E K,Gendreau M,Hyde M,et al.Hyper-heuristics:a Survey of the State of the Art[J].Journal of the Operational Research Society (S0160-5682),2013,64(12):1695-1724.
[11]	张国辉,高亮,李培根.基于遗传规划的作业车间调度算法研究[J].控制与决策,2008(8):924-928.Zhang Guohui,Gao Liang,Li Peigen.Job-Shop Scheduling Based on Genetic Programming Algorithm[J].Control and Decision,2008(8):924-928.
[12]	范华丽,熊禾根,蒋国璋,等.基于遗传规划的动态作业车间调度规则生成[J].计算机集成制造系统,2018,24(4):876-885.Fan Huali,Xiong Hegen,Jiang Guozhang,et al.Generation of Dispatching Rules for Dynamic Job Shop Scheduling Problem Based on Genetic Programming Algorithm[J].Computer Integrated Manufacturing Systems,2018,24(4):876-885.
[13]	Nguyen S,Zhang M J,Johnston M,et al.Genetic Programming for Job Shop Scheduling[M].Switzerland:Evolutionary and Swarm Intelligence Algorithms,2018.
[14]	Nie L,Shao X,Gao L,et al.Evolving Scheduling Rules with Gene Expression Programming for Dynamic Single-machine Scheduling Problems[J].The International Journal of Advanced Manufacturing Technology (S0268-3768),2010,50(5/8):729-747.
[15]	Zhou H,Cheung W,Leung L C.Minimizing Weighted Tardiness of Job-Shop Scheduling Using a Hybrid Genetic Algorithm[J].European Journal of Operational Research (S0377-2217),2009,194(3):637-649.
[16]	Koza J R.Genetic Programming:on the Programming of Computers by Means of Natural Selection[M].Cambridge:MIT Press,1992.
[17]	Mei Y,Nguyen S,Xue B,et al.An Efficient Feature Selection Algorithm for Evolving Job Shop Scheduling Rules with Genetic Programming[J].IEEE Transactions on Emerging Topics in Computational Intelligence (S2471-285X),2017,1(5):339-353.
[18]	Zitzler E,Thiele L.Multi-objective Evolutionary Algorithms:a Comparative Case Study and the Strength Pareto Approach[J].IEEE Transactions on Evolutionary Computation (S1089-778X),1999,3(4):257-271.
[19]	Deb K,Pratap A,Agarwal S,et al.A Fast and Elitist Multi-Objective Genetic Algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation (S1089-778X),2002,6(2):182-197.
[20]	Kanet J J,Li X.A Weighted Modified Due Date Rule for Sequencing to Minimize Weighted Tardiness[J].Journal of Scheduling (S1094-6136),2004,7(4):261-276.
[21]	Wu C C,Liu S C,Zhao C,et al.A Multi-machine Order Scheduling with Learning Using the Genetic Algorithm and Particle Swarm Optimization[J].The Computer Journal (S0010-4620),2018,61(1):14-31.
[22]	Nguyen S,Zhang M J,Johnston M,et al.A Computational Study of Representations in Genetic Programming to Evolve Dispatching Rules for the Job Shop Scheduling Problem[J].IEEE Transactions on Evolutionary Computation (S1089-778X),2013,17(5):621-639.
[23]	Nguyen S,Zhang M J,Johnston M,et al.Automatic Design of Scheduling Policies for Dynamic Multi-objective Job Shop Scheduling via Cooperative Coevolution Genetic Programming[J].IEEE Transactions on Evolutionary Computation (S1089-778X),2014,18(2):193-208.
[24]	Branke J,Nguyen S,Pickardt C W,et al.Automated Design of Production Scheduling Heuristics:a Review[J].IEEE Transactions on Evolutionary Computation (S1089-778X),2015,20(1):110-124.
[25]	Nguyen S,Zhang M J,Johnston M,et al.Automatic Programming via Iterated Local Search for Dynamic Job Shop Scheduling[J].IEEE Transactions on Cybernetics (S2168-2267),2015,45(1):1-14.
[26]	Jamrus T,Chien C F,Gen M,et al.Hybrid Particle Swarm Optimization Combined With Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing[J].IEEE Transactions on Semiconductor Manufacturing (S0894-6507),2018,31(1):32-41.
[27]	曹东风,王艳.基于组合权重的制造系统能效贝叶斯评价方法[J].系统仿真学报,2018,30(11):290-299.Cao Dongfeng,Wang Yan.Bayesian Evaluation Method for Energy Efficiency of Manufacturing System Based on Combined Weights[J].Journal of System Simulation,2018,30(11):290-299.
[28]	Nguyen S,Mei Y,et al.A Hybrid Genetic Programming Algorithm for Automated Design of Dispatching Rules[J].Evolutionary Computation (S1063-6560),2018,27(3):367-496.
[29]	Hildebrandt T,Branke J,Jürgen.On Using Surrogates with Genetic Programming[J].Evolutionary Computation (S1063-6560),2015,23(3):343-367.
[30]	Zhou Y,Yang J J,Zheng L Y.Hyper-Heuristic Coevolution of Machine Assignment and Job Sequencing Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling[J].IEEE Access (S2169-3536),2018,11(7):68-88.
[31]	Zhang F F,Mei Y,Zhang M J.A Two-Stage Genetic Programming Hyper-Heuristic Approach with Feature Selection for Dynamic Flexible Job Shop Scheduling[C].Genetic &Evolutionary Computation Conference.Czech Republic:Association for Computing Machinery,2019.