Grammar-guided Linear Genetic Programming for Dynamic Job Shop Scheduling
Pages 1137 - 1145
Abstract
Dispatching rules are commonly used to make instant decisions in dynamic scheduling problems. Linear genetic programming (LGP) is one of the effective methods to design dispatching rules automatically. However, the effectiveness and efficiency of LGP methods are limited due to the large search space. Exploring the entire search space of programs is inefficient for LGP since a large number of programs might contain redundant blocks and might be inconsistent with domain knowledge, which would further limit the effectiveness of the produced LGP models. To improve the performance of LGP in dynamic job shop scheduling problems, this paper proposes a grammar-guided LGP to make LGP focus more on promising programs. Our dynamic job shop scheduling simulation results show that the proposed grammar-guided LGP has better training efficiency than basic LGP, and can produce solutions with good explanations. Further analyses show that grammar-guided LGP significantly improves the overall test effectiveness when the number of LGP registers increases.
References
[1]
Filipe Assunção, Nuno Lourenço, Penousal Machado, and Bernardete Ribeiro. 2019. DENSER: deep evolutionary network structured representation. Genetic Programming and Evolvable Machines 20 (2019), 5--35. Issue 1.
[2]
Ying Bi, Bing Xue, and Mengjie Zhang. 2022. Genetic Programming-Based Evolutionary Deep Learning for Data-Efficient Image Classification. IEEE Transactions on Evolutionary Computation (2022), 1--15. Early Access.
[3]
Markus Brameier and Wolfgang Banzhaf. 2007. Linear Genetic Programming. Springer US.
[4]
Edmund K. Burke, Mathew R. Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and John R. Woodward. 2009. Exploring hyper-heuristic methodologies with genetic programming. Computational Intelligence 1 (2009), 177--201. Issue 1.
[5]
F. Corman and E. Quaglietta. 2015. Closing the loop in real-time railway control: Framework design and impacts on operations. Transportation Research Part C: Emerging Technologies 54 (2015), 15--39.
[6]
Grant Dick and Peter A. Whigham. 2022. Initialisation and grammar design in grammar-guided evolutionary computation. In Proceedings of the Genetic and Evolutionary Computation Conference. 534--537.
[7]
Stefan Forstenlechner, David Fagan, Miguel Nicolau, and Michael O'Neill. 2017. A Grammar Design Pattern for Arbitrary Program Synthesis Problems in Genetic Programming. European Conference on Genetic Programming, 262--277.
[8]
Stefan Forstenlechner, David Fagan, Miguel Nicolau, and Michael O'Neill. 2018. Extending Program Synthesis Grammars for Grammar-Guided Genetic Programming. In Proceedings of Parallel Problem Solving from Nature. 197--208.
[9]
Christopher D. Geiger, Reha Uzsoy, and Haldun Aytuǧ. 2006. Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling 9 (2006), 7--34. Issue 1.
[10]
Erik Hemberg, Jonathan Kelly, and Una May O'Reilly. 2019. On domain knowledge and novelty to improve program synthesis performance with grammatical evolution. In Proceedings of the 2019 Genetic and Evolutionary Computation Conference. 1039--1046.
[11]
Torsten Hildebrandt, Jens Heger, and Bernd Scholz-reiter. 2010. Towards Improved Dispatching Rules for Complex Shop Floor Scenarios --- a Genetic Programming Approach. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation. 257--264.
[12]
Zhixing Huang, Yi Mei, Fangfang Zhang, and Mengjie Zhang. 2022. Graph-based linear genetic programming: a case study of dynamic scheduling. In Proceedings of the Genetic and Evolutionary Computation Conference. 955--963.
[13]
Zhixing Huang, Yi Mei, Fangfang Zhang, and Mengjie Zhang. 2023. Multitask Linear Genetic Programming with Shared Individuals and its Application to Dynamic Job Shop Scheduling. IEEE Transactions on Evolutionary Computation (2023).
[14]
Zhixing Huang, Yi Mei, and Mengjie Zhang. 2021. Investigation of Linear Genetic Programming for Dynamic Job Shop Scheduling. Proceedings of IEEE Symposium Series on Computational Intelligence, 1--8.
[15]
Zhixing Huang, Fangfang Zhang, Yi Mei, and Mengjie Zhang. 2022. An Investigation of Multitask Linear Genetic Programming for Dynamic Job Shop Scheduling. In Proceedings of European Conference on Genetic Programming. 162--178.
[16]
Rachel Hunt, Johnston Richard, and Mengjie Zhang. 2015. Evolving Dispatching Rules with Greater Understandability for Dynamic Job Shop Scheduling Mark Johnston. Technical report ECSTR-15-6.
[17]
Domagoj Jakobović and Leo Budin. 2006. Dynamic Scheduling with Genetic Programming. In Proceedings of European Conference on Genetic Programming. 73--84.
[18]
Leonardo Lamorgese and Carlo Mannino. 2019. A noncompact formulation for job-shop scheduling problems in traffic management. Operations Research 67, 6 (2019), 1586--1609.
[19]
Wong Man Leung, Leung Kwong Sak, Man Leung Wong, and Kwong Sak Leung. 1995. Applying logic grammars to induce sub-functions in genetic programming. Proceedings of the IEEE Conference on Evolutionary Computation 2, 737--740.
[20]
Dimmy Magalhães, Ricardo H.R. Lima, and Aurora Pozo. 2023. Creating deep neural networks for text classification tasks using grammar genetic programming. Applied Soft Computing 135 (2023), 110009.
[21]
Robert I. McKay, Nguyen Xuan Hoai, Peter Alexander Whigham, Yin Shan, and Michael O'neill. 2010. Grammar-based Genetic programming: A survey. Genetic Programming and Evolvable Machines 11 (2010), 365--396. Issue 3--4.
[22]
Yi Mei, Qi Chen, Andrew Lensen, Bing Xue, and Mengjie Zhang. 2022. Explainable Artificial Intelligence by Genetic Programming: A Survey. IEEE Transactions on Evolutionary Computation (2022), 1--21.
[23]
David J. Montana. 1995. Strongly typed genetic programming. Evolutionary Computation 3 (1995), 199--230. Issue 2.
[24]
Su Nguyen, Yi Mei, and Mengjie Zhang. 2017. Genetic programming for production scheduling: a survey with a unified framework. Complex & Intelligent Systems 3 (2017), 41--66. Issue 1.
[25]
Su Nguyen, Mengjie Zhang, Mark Johnston, and Kay Chen Tan. 2013. A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation 17 (2013), 621--639. Issue 5.
[26]
Peter Nordin. 1994. A compiling genetic programming system that directly manipulates the machine code. Advances in genetic programming 1 (1994), 311--331.
[27]
Michael O'Neill, Miguel Nicolau, and Alexandros Agapitos. 2014. Experiments in program synthesis with grammatical evolution: A focus on Integer Sorting. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation. 1504--1511.
[28]
Michael O'Neill and Conor Ryan. 2001. Grammatical evolution. IEEE Transactions on Evolutionary Computation 5 (2001), 349--358. Issue 4.
[29]
Michael O'Neill and Conor Ryan. 2003. Grammatical Evolution. Vol. 4. Springer US.
[30]
F. Padillo, J. M. Luna, and S. Ventura. 2019. A Grammar-Guided Genetic Programming Algorithm for Associative Classification in Big Data. Cognitive Computation 11 (2019), 331--346. Issue 3.
[31]
Gisele L. Pappa and Alex A. Freitas. 2009. Evolving rule induction algorithms with multi-objective grammar-based genetic programming. Knowledge and Information Systems 19 (2009), 283--309. Issue 3.
[32]
Dominik Sobania and Franz Rothlauf. 2020. Challenges of Program Synthesis with Grammatical Evolution. In Proceedings of the European Conference on Genetic Programming. 211--227.
[33]
P.A. Whigham. 1995. Grammatically-based Genetic Programming. Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, 33--41.
[34]
Fangfang Zhang, Yi Mei, Su Nguyen, Kay Chen Tan, and Mengjie Zhang. 2022. Instance Rotation Based Surrogate in Genetic Programming with Brood Recombination for Dynamic Job Shop Scheduling. IEEE Transactions on Evolutionary Computation (2022), 1--15.
[35]
Fangfang Zhang, Yi Mei, Su Nguyen, Kay Chen Tan, and Mengjie Zhang. 2022. Task Relatedness Based Multitask Genetic Programming for Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation (2022), 1--15.
[36]
Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. 2022. Multitask Multi-objective Genetic Programming for Automated Scheduling Heuristic Learning in Dynamic Flexible Job-Shop Scheduling. IEEE Transactions on Cybernetics (2022), 1--14.
[37]
Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. 2023. Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop Scheduling. IEEE Transactions on Evolutionary Computation (2023), 1--21.
[38]
Fangfang Zhang, Su Nguyen, Yi Mei, and Mengjie Zhang. 2021. Genetic Programming for Production Scheduling. Springer Singapore. XXXIII+338 pages.
Index Terms
- Grammar-guided Linear Genetic Programming for Dynamic Job Shop Scheduling
Recommendations
Graph-based linear genetic programming: a case study of dynamic scheduling
GECCO '22: Proceedings of the Genetic and Evolutionary Computation ConferenceLinear genetic programming (LGP) has been successfully applied to various problems such as classification, symbolic regression and hyper-heuristics for automatic heuristic design. In contrast with the traditional tree-based genetic programming (TGP), LGP ...
An Investigation of Multitask Linear Genetic Programming for Dynamic Job Shop Scheduling
Genetic ProgrammingAbstractDynamic job shop scheduling has a wide range of applications in reality such as order picking in warehouse. Using genetic programming to design scheduling heuristics for dynamic job shop scheduling problems becomes increasingly common. In recent ...
Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem
We developed efficient hybrid genetic algorithms for dynamic job shop scheduling.A new KK heuristic is proposed and it is combined with genetic algorithm.The problem includes new job arrival, machine breakdown and changes in processing time.In ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1667 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 249Total Downloads
- Downloads (Last 12 months)134
- Downloads (Last 6 weeks)7
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in