research-article

A two-stage genetic programming hyper-heuristic approach with feature selection for dynamic flexible job shop scheduling

Authors:

Fangfang Zhang,

Mengjie ZhangAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 347 - 355

https://doi.org/10.1145/3321707.3321790

Published: 13 July 2019 Publication History

Abstract

Dynamic flexible job shop scheduling (DFJSS) is an important and a challenging combinatorial optimisation problem. Genetic programming hyper-heuristic (GPHH) has been widely used for automatically evolving the routing and sequencing rules for DFJSS. The terminal set is the key to the success of GPHH. There are a wide range of features in DFJSS that reflect different characteristics of the job shop state. However, the importance of a feature can vary from one scenario to another, and some features may be redundant or irrelevant under the considered scenario. Feature selection is a promising strategy to remove the unimportant features and reduce the search space of GPHH. However, no work has considered feature selection in GPHH for DFJSS so far. In addition, it is necessary to do feature selection for the two terminal sets simultaneously. In this paper, we propose a new two-stage GPHH approach with feature selection for evolving routing and sequencing rules for DFJSS. The experimental studies show that the best solutions achieved by the proposed approach are better than that of the baseline method in most scenarios. Furthermore, the rules evolved by the proposed approach involve a smaller number of unique features, which are easier to interpret.

References

[1]

Ehsan Ahmadi, Mostafa Zandieh, Mojtaba Farrokh, and Seyed Mohammad Emami. 2016. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Computers & OR 73 (2016), 56--66.

Digital Library

[2]

Jürgen Branke, Torsten Hildebrandt, and Bernd Scholz-Reiter. 2015. Hyper-heuristic Evolution of dispatching rules: a comparison of rule representations. Evolutionary Computation 23, 2 (2015), 249--277.

Digital Library

[3]

Juergen Branke, Su Nguyen, Christoph W Pickardt, and Mengjie Zhang. 2016. Automated design of production scheduling heuristics: A review. IEEE Transactions on Evolutionary Computation 20, 1 (2016), 110--124.

Digital Library

[4]

Carlos A. Brizuela and Nobuo Sannomiya. 1999. A diversity study in genetic algorithms for job shop scheduling problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), 13--17 July 1999, Orlando, Florida, USA. 75--82.

Digital Library

[5]

Edmund K Burke, Mathew R Hyde, Graham Kendall, Gabriela Ochoa, Ender Ozcan, and John R Woodward. 2009. Exploring hyper-heuristic methodologies with genetic programming. In Computational Intelligence. Springer, 177--201.

[6]

Haoxun Chen, Chengbin Chu, and J-M Proth. 1998. An improvement of the Lagrangean relaxation approach for job shop scheduling: a dynamic programming method. IEEE Transactions on Robotics and Automation 14, 5 (1998), 786--795.

[7]

Qi Chen, Mengjie Zhang, and Bing Xue. 2017. Feature selection to improve generalization of genetic programming for high-dimensional symbolic regression. IEEE Transactions on Evolutionary Computation 21, 5 (2017), 792--806.

Digital Library

[8]

Manoranjan Dash and Huan Liu. 1997. Feature selection for classification. Intelligent data analysis 1, 3 (1997), 131--156.

Digital Library

[9]

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 12th Annual Conference on Genetic and Evolutionary Computation. ACM, 257--264.

Digital Library

[10]

Rachel Hunt, Mark Johnston, and Mengjie Zhang. 2014. Evolving "less-myopic" scheduling rules for dynamic job shop scheduling with genetic programming. In Genetic and Evolutionary Computation Conference, GECCO '14, Vancouver, BC, Canada, July 12--16, 2014. 927--934.

Digital Library

[11]

Rachel Hunt, Mark Johnston, and Mengjie Zhang. 2014. Evolving machinespecific dispatching rules for a two-machine job shop using genetic programming. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, July 6--11, 2014. 618--625.

[12]

John R Koza. 1994. Genetic programming as a means for programming computers by natural selection. Statistics and Computing 4, 2 (1994), 87--112.

[13]

Andrew Lensen, Bing Xue, and Mengjie Zhang. 2016. Particle swarm optimisation representations for simultaneous clustering and feature selection. In Computational Intelligence (SSCI), 2016 IEEE Symposium Series on. IEEE, 1--8.

[14]

Bart L Maccarthy and Jiyin Liu. 1993. Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. The International Journal of Production Research 31, 1 (1993), 59--79.

[15]

Yi Mei, Su Nguyen, Bing Xue, and Mengjie Zhang. 2017. An efficient feature selection algorithm for evolving job shop scheduling rules with genetic programming. IEEE Transactions on Emerging Topics in Computational Intelligence 1, 5 (2017), 339--353.

[16]

Yi Mei, Su Nguyen, and Mengjie Zhang. 2017. Evolving time-invariant dispatching rules in job shop scheduling with genetic programming. In European Conference on Genetic Programming. Springer, 147--163.

[17]

Yi Mei, Mengjie Zhang, and Su Nyugen. 2016. Feature selection in evolving job shop dispatching rules with genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, 365--372.

Digital Library

[18]

Su Nguyen, Yi Mei, and Mengjie Zhang. 2017. Genetic programming for production scheduling: a survey with a unified framework. Complex & Intelligent Systems 3, 1 (2017), 41--66.

[19]

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, 5 (2013), 621--639.

Digital Library

[20]

Su Nguyen, Mengjie Zhang, and Kay Chen Tan. 2017. Surrogate-assisted genetic programming with simplified models for automated design of dispatching rules. IEEE Transactions on Cybernetics 47, 9 (2017), 2951--2965.

[21]

John Park, Yi Mei, Su Nguyen, Gang Chen, and Mengjie Zhang. 2018. Investigating a machine breakdown genetic programming approach for dynamic job shop scheduling. In Genetic Programming - 21st European Conference, EuroGP 2018, Parma, Italy, April 4--6, 2018, Proceedings. 253--270.

[22]

Alain Pétrowski. 1996. A Clearing Procedure as a Niching Method for Genetic Algorithms. In Proceedings of 1996 IEEE International Conference on Evolutionary Computation, Nayoya University, Japan, May 20--22, 1996. 798--803.

[23]

Christoph W Pickardt, Torsten Hildebrandt, Jürgen Branke, Jens Heger, and Bernd Scholz-Reiter. 2013. Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems. International Journal of Production Economics 145, 1 (2013), 67--77.

[24]

Alper Kursat Uysal. 2016. An improved global feature selection scheme for text classification. Expert systems with Applications 43 (2016), 82--92.

Digital Library

[25]

Harvey M Wagner. 1959. An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly 6, 2 (1959), 131--140.

[26]

Bing Xue, Mengjie Zhang, and Will N Browne. 2013. Particle swarm optimization for feature selection in classification: A multi-objective approach. IEEE Transactions on Cybernetics 43, 6 (2013), 1656--1671.

[27]

Bing Xue, Mengjie Zhang, Will N Browne, and Xin Yao. 2016. A survey on evolutionary computation approaches to feature selection. IEEE Transactions on Evolutionary Computation 20, 4 (2016), 606--626.

Digital Library

[28]

Daniel Yska, Yi Mei, and Mengjie Zhang. 2018. Genetic Programming Hyper-Heuristic with Cooperative Coevolution for Dynamic Flexible Job Shop Scheduling. In European Conference on Genetic Programming. Springer, 306--321.

[29]

Fangfang Zhang, Yi Mei, and Mengjie Zhang. 2018. Genetic programming with multi-tree representation for dynamic flexible job shop scheduling. In AI 2018: Advances in Artificial Intelligence - 31st Australasian Joint Conference, Wellington, New Zealand, December 11--14, 2018, Proceedings. 472--484.

[30]

Fangfang Zhang, Yi Mei, and Mengjie Zhang. 2018. Surrogate-assisted genetic programming for dynamic flexible job shop scheduling. In AI 2018: Advances in Artificial Intelligence - 31st Australasian Joint Conference, Wellington, New Zealand, December 11--14, 2018, Proceedings. 766--772.

[31]

Xiaofeng Zhu, Heung-Il Suk, Li Wang, Seong-Whan Lee, Dinggang Shen, Alzheimer's Disease Neuroimaging Initiative, et al. 2017. A novel relational regularization feature selection method for joint regression and classification in AD diagnosis. Medical image analysis 38 (2017), 205--214.

Cited By

Xu BXu KFei BHuang DTao LWang Y(2024)Automatic Design of Energy-Efficient Dispatching Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling Based on Dual Feature Weight SetsMathematics10.3390/math1210146312:10(1463)Online publication date: 9-May-2024
https://doi.org/10.3390/math12101463
Đurasević MJakobović D(2024)Heuristic Ensemble Construction Methods of Automatically Designed Dispatching Rules for the Unrelated Machines EnvironmentAxioms10.3390/axioms1301003713:1(37)Online publication date: 5-Jan-2024
https://doi.org/10.3390/axioms13010037
Đurasević MJakobović DPicek SMariot L(2024)Assessing the Ability of Genetic Programming for Feature Selection in Constructing Dispatching Rules for Unrelated Machine EnvironmentsAlgorithms10.3390/a1702006717:2(67)Online publication date: 4-Feb-2024
https://doi.org/10.3390/a17020067
Show More Cited By

Index Terms

A two-stage genetic programming hyper-heuristic approach with feature selection for dynamic flexible job shop scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
      1. Planning under uncertainty

Recommendations

A preliminary approach to evolutionary multitasking for dynamic flexible job shop scheduling via genetic programming
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Genetic programming, as a hyper-heuristic approach, has been successfully used to evolve scheduling heuristics for job shop scheduling. However, the environments of job shops vary in configurations, and the scheduling heuristic for each job shop is ...
Feature Selection in Evolving Job Shop Dispatching Rules with Genetic Programming
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

Genetic Programming (GP) has been successfully used to automatically design dispatching rules in job shop scheduling. The goal of GP is to evolve a priority function that will be used to order the waiting jobs at each decision point, and decide the next ...
Feature construction in genetic programming hyper-heuristic for dynamic flexible job shop scheduling
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Genetic Programming Hyper-Heuristic (GPHH) has shown success in evolving dispatching rules for dynamic Flexible Job Shop Scheduling (FJSS). In this paper, we focus on feature construction to improve the effectiveness and efficiency of GPHH, and propose ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

July 2019

1545 pages

ISBN:9781450361118

DOI:10.1145/3321707

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Copyright © 2019 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 ACM 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
403
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)20

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xu BXu KFei BHuang DTao LWang Y(2024)Automatic Design of Energy-Efficient Dispatching Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling Based on Dual Feature Weight SetsMathematics10.3390/math1210146312:10(1463)Online publication date: 9-May-2024
https://doi.org/10.3390/math12101463
Đurasević MJakobović D(2024)Heuristic Ensemble Construction Methods of Automatically Designed Dispatching Rules for the Unrelated Machines EnvironmentAxioms10.3390/axioms1301003713:1(37)Online publication date: 5-Jan-2024
https://doi.org/10.3390/axioms13010037
Đurasević MJakobović DPicek SMariot L(2024)Assessing the Ability of Genetic Programming for Feature Selection in Constructing Dispatching Rules for Unrelated Machine EnvironmentsAlgorithms10.3390/a1702006717:2(67)Online publication date: 4-Feb-2024
https://doi.org/10.3390/a17020067
Nguyen SThiruvady DSun YZhang MLi XHandl J(2024)Genetic-based Constraint Programming for Resource Constrained Job SchedulingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654046(942-951)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654046
Zhang FMei YNguyen SZhang M(2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3255246
Xu MMei YZhang FZhang M(2024)Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324460728:5(1235-1249)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3244607
Chen JJia YBi YChen W(2024)Generate a Single Heuristic for Multiple Dynamic Flexible Job Shop Scheduling Tasks by Genetic Programming2024 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC60901.2024.10611762(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/CEC60901.2024.10611762
Yu RLadwig RXu XZhu PHanson PXie YJia X(2024)Evolution-Based Feature Selection for Predicting Dissolved Oxygen Concentrations in LakesParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_25(398-415)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70085-9_25
Oueslati IHammami MNouaouri IAzzouz ASaid LAllaoui H(2024)A Honey Bee Mating Optimization HyperHeuristic for Patient Admission Scheduling ProblemMetaheuristics and Nature Inspired Computing10.1007/978-3-031-69257-4_7(89-104)Online publication date: 15-Sep-2024
https://doi.org/10.1007/978-3-031-69257-4_7
\DJurasević MGil-Gala FJakobović D(2023)Constructing ensembles of dispatching rules for multi-objective tasks in the unrelated machines environmentIntegrated Computer-Aided Engineering10.3233/ICA-23070430:3(275-292)Online publication date: 10-May-2023
https://doi.org/10.3233/ICA-230704
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents