基于超启发式遗传规划的动态车间调度方法

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

系统仿真学报 ›› 2020, Vol. 32 ›› Issue (12): 2494-2506.doi: 10.16182/j.issn1004731x.joss.20-FZ0452

基于超启发式遗传规划的动态车间调度方法

张苏雨, 王艳, 纪志成

江南大学教育部物联网技术应用工程中心,江苏无锡 214122

收稿日期:2020-04-29 修回日期:2020-07-08 出版日期:2020-12-18 发布日期:2020-12-16
作者简介:张苏雨(1996-),女,江苏苏州,博士生,研究方向为动态离散作业车间调度规则发现;王艳(1978-),女,江苏无锡,博士,教授,博导,研究方向为制造系统能效优化。
基金资助:
国家自然科学基金(61973138),国家重点研发计划(2018YFB1701903)

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

Zhang Suyu, Wang Yan, Ji Zhicheng

Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China

Received:2020-04-29 Revised:2020-07-08 Online:2020-12-18 Published:2020-12-16

摘要/Abstract

摘要： 动态作业车间存在资源状态的不确定性和任务的随机性,难以寻找适用于多种复杂生产情景的通用调度规则。提出一种基于超启发式遗传规划的动态车间调度规则自动化发现方法,以最大完工时间和平均加权迟到时间为优化目标,利用机器排序规则的自动化发现,来提高不同生产情景下车间调度的动态适应性。通过对演化调度规则的语义分析,分析了GP树终端属性对不同优化目标的作用。实验结果表明,所提算法能够针对不同生产场景,生成适合的调度规则,且性能优于人工设计的基准调度规则。

关键词: 遗传规划算法, 动态作业车间, 调度规则, 自动化发现

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

中图分类号:

TP391.9

张苏雨, 王艳, 纪志成. 基于超启发式遗传规划的动态车间调度方法[J]. 系统仿真学报, 2020, 32(12): 2494-2506.

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.

参考文献 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.

基于超启发式遗传规划的动态车间调度方法

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 31

相关文章 2

编辑推荐

Metrics

本文评价

[1]	赵也践, 王艳红, 张俊, 于洪霞, 田中大. 改进Q学习算法在作业车间调度问题中的应用[J]. 系统仿真学报, 2022, 34(6): 1247-1258.
[2]	吴定会, 张桐瑞, 张秀丽. 扰动累积下基于数字孪生的车间重调度[J]. 系统仿真学报, 2022, 34(3): 573-583.