Surrogate-Assisted Evolutionary Multitask Genetic Programming for Dynamic Flexible Job Shop Scheduling
Open accessThe DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
Dynamic flexible job shop scheduling (JSS) is an important combinatorial optimization problem with complex routing and sequencing decisions under dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully applied to evolve scheduling heuristics for JSS. However, its training process is time consuming, and it faces the retraining problem once the characteristics of job shop scenarios vary. It is known that multitask learning is a promising paradigm for solving multiple tasks simultaneously by sharing knowledge among the tasks. To improve the training efficiency and effectiveness, this article proposes a novel surrogate-assisted evolutionary multitask algorithm via GP to share useful knowledge between different scheduling tasks. Specifically, we employ the phenotypic characterization for measuring the behaviors of scheduling rules and building a surrogate for each task accordingly. The built surrogates are used not only to improve the efficiency of solving each single task but also for knowledge transfer in multitask learning with a large number of promising individuals. The results show that the proposed algorithm can significantly improve the quality of scheduling heuristics for all scenarios. In addition, the proposed algorithm manages to solve multiple tasks collaboratively in terms of the evolved scheduling heuristics for different tasks in a multitask scenario.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Handbook of Genetic Algorithms
Davis, L. D. (1991) · Cumulative Index of Computer Aided Architectural Design · Cited by 7,330
Glover, F., & Laguna, M. (1997) · Cited by 5,679
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001 · cited 1×
“Approximate solu-tion optimisation methods such as simulated annealing [11], tabu search [12] and genetic algorithms [13], which aim to find a near-optimal solution, have been widely applied to JSS.”
MethodSurrogate-assisted evolutionary computation: Recent advances and future challenges
Jin, Y. (2011) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2011.05.001 · Cited by 1,514 · cited 1×
“Surrogate models [26], [27], [28] have been widely used to reduce the computational cost in evolutionary computation.”
MethodMultifactorial Evolution: Toward Evolutionary Multitasking
Gupta, A., Ong, Y.-S., & Feng, L. (2016) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2015.2458037 · Cited by 993 · cited 7×
“The paradigm of evolutionary multitasking was given in [32], [33] for solving multiple tasks simultaneously.”
BackgroundMethodInfluentialOn the Job-Shop Scheduling Problem
Manne, A. S. (1960) · Operations Research · doi:10.1287/opre.8.2.219 · Cited by 666
Multifactorial Evolutionary Algorithm With Online Transfer Parameter Estimation: MFEA-II
Bali, K. K., Ong, Y.-S., Gupta, A., & Tan, P. S. (2020) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2019.2906927 · Cited by 437 · cited 1×
“In addition, the data generated in the evolutionary process was successfully used to measure the relatedness between tasks to guide the knowledge transfer between tasks in an online fashion [64], [65], [66].”
MethodGlover, F., & Laguna, M. (1998) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4613-0303-9_33 · Cited by 428
Exploring Hyper-heuristic Methodologies with Genetic Programming
Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Ozcan, E., & Woodward, J. R. (2009) · Intelligent Systems Reference Library · doi:10.1007/978-3-642-01799-5_6 · Cited by 304 · cited 1×
“GP, as a hyper-heuristic method [44], has been successfully applied to evolve scheduling heuristics for different types of JSS [45], [46], [47].”
MethodGeneralized Multitasking for Evolutionary Optimization of Expensive Problems
Ding, J., Yang, C., Jin, Y., & Chai, T. (2019) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2017.2785351 · Cited by 277 · cited 3×
“Moreover, it is not easy to apply existing approaches [40], [41], [42], [43] in DFJSS with GPHH directly.”
BackgroundMethodZhang, F., Mei, Y., Nguyen, S., & Zhang, M. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3024849 · Cited by 264 · cited 1×
“Genetic programming (GP) [18], as a hyper-heuristic approach (GPHH), has been successfully applied to evolve scheduling heuristics automatically for JSS [7], [19], [20], [21].”
MethodSelf-citationAn Evolutionary Multitasking-Based Feature Selection Method for High-Dimensional Classification
Chen, K., Xue, B., Zhang, M., & Zhou, F. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3042243 · Cited by 263
Self-citationEvolutionary Multitasking: A Computer Science View of Cognitive Multitasking
Ong, Y.-S., & Gupta, A. (2016) · Cognitive Computation · doi:10.1007/s12559-016-9395-7 · Cited by 250 · cited 1×
“The relatedness between tasks is an important prerequisite for the effectiveness of multitasking algorithm, and measuring the relatedness between tasks is still an open question [62].”
BackgroundToward Adaptive Knowledge Transfer in Multifactorial Evolutionary Computation
Zhou, L., Feng, L., Tan, K. C., Zhong, J., Zhu, Z., Liu, K., & Chen, C. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2974100 · Cited by 249 · cited 1×
“Evolutionary multitasking has been successfully applied to solve different problems such as continuous numeric optimisation [33], [34], [35], symbolic regression [36] and job shop scheduling [37], [38].”
MethodSelf-citationRapid Modeling and Discovery of Priority Dispatching Rules: An Autonomous Learning Approach
Geiger, C. D., Uzsoy, R., & Aytuğ, H. (2006) · Journal of Scheduling · doi:10.1007/s10951-006-5591-8 · Cited by 217 · cited 2×
“J ob shop scheduling (JSS) [1] has been widely studied in both academia and industry such as manufacturing processes [2] and grid computing [3] due to its practical applications.”
BackgroundKoza, J. R., & Poli, R. (2006) · Search Methodologies · doi:10.1007/0-387-28356-0_5 · Cited by 216
An Adaptive Archive-Based Evolutionary Framework for Many-Task Optimization
Chen, Y., Zhong, J., Feng, L., & Zhang, J. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2916051 · Cited by 205 · cited 1×
“In addition, the data generated in the evolutionary process was successfully used to measure the relatedness between tasks to guide the knowledge transfer between tasks in an online fashion [64], [65], [66].”
MethodCognizant Multitasking in Multiobjective Multifactorial Evolution: MO-MFEA-II
Bali, K. K., Gupta, A., Ong, Y.-S., & Tan, P. S. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2981733 · Cited by 198 · cited 1×
“In addition, the data generated in the evolutionary process was successfully used to measure the relatedness between tasks to guide the knowledge transfer between tasks in an online fashion [64], [65], [66].”
MethodOn Using Surrogates with Genetic Programming
Hildebrandt, T., & Branke, J. (2015) · Evolutionary Computation · doi:10.1162/evco_a_00133 · Cited by 196 · cited 10×
“The algorithm in [29] that uses KNN to build surrogate only, named SMTGP in this paper, is applied in a multitasking framework.”
BackgroundMethodResultInfluentialUsing clinical simulation to study how to improve quality and safety in healthcare
Lamé, G., & Dixon-Woods, M. (2020) · BMJ Simulation and Technology Enhanced Learning · doi:10.1136/bmjstel-2018-000370 · Cited by 180 · cited 1×
“DFJSS is widely studied with simulation [22] which is a promising technique to examine complicated real-world applications such as healthcare [23] and manufacturing [24].”
BackgroundMultifactorial Genetic Programming for Symbolic Regression Problems
Zhong, J., Feng, L., Cai, W., & Ong, Y.-S. (2020) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2018.2853719 · Cited by 163 · cited 4×
“It has been applied to different fields, such as continuous numeric optimisation [33], [34], [54], and regression problems [36].”
MethodInfluentialMin, A. T. W., Ong, Y.-S., Gupta, A., & Goh, C.-K. (2017) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2017.2783441 · Cited by 154 · cited 3×
“Moreover, it is not easy to apply existing approaches [40], [41], [42], [43] in DFJSS with GPHH directly.”
BackgroundMethodMultifactorial optimization via explicit multipopulation evolutionary framework
Li, G., Lin, Q., & Gao, W. (2019) · Information Sciences · doi:10.1016/j.ins.2019.10.066 · Cited by 120 · cited 2×
“It has been applied to different fields, such as continuous numeric optimisation [33], [34], [54], and regression problems [36].”
MethodHuang, S., Zhong, J., & Yu, W. (2019) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2019.2945775 · Cited by 101 · cited 5×
“In [41], surrogate models are built based on historical search information for each task to reduce the number of fitness evaluations in multitasking problems.”
BackgroundMethodInfluentialZhang, F., Mei, Y., Nguyen, S., & Zhang, M. (2021) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2021.3056143 · Cited by 96
Self-citationSolving the Job-Shop Scheduling Problem in the Industry 4.0 Era
Leusin, M. E., Frazzon, E. M., Maldonado, M. U., Kück, M., & Freitag, M. (2018) · Technologies · doi:10.3390/technologies6040107 · Cited by 92 · cited 1×
“This is because the characteristics of DFJSS such as the machine resources and order quantity may vary, which is common in practical applications [25].”
BackgroundZhang, F., Mei, Y., & Zhang, M. (2019) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3321707.3321790 · Cited by 70 · cited 5×
“To estimate the steady-state performance, the first 1000 jobs are considered as warm-up jobs and discarded in the objective calculations [7].”
BackgroundMethodInfluentialSelf-citationTransfer learning in genetic programming
Dinh, T. T. H., Chu, T. H., & Nguyen, Q. U. (2015) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2015.7257018 · Cited by 63 · cited 2×
“Otherwise, the transferred individuals will be eliminated subsequently during the evolutionary process, and lose the role of knowledge transfer [58].”
BackgroundCurse and Blessing of Uncertainty in Evolutionary Algorithm Using Approximation
Ong, Y.-S., Zhou, Z., & Lim, D. (2006) · doi:10.1109/cec.2006.1688677 · Cited by 60 · cited 1×
“Surrogate models [26], [27], [28] have been widely used to reduce the computational cost in evolutionary computation.”
MethodGenetic Programming for Evolving Due-Date Assignment Models in Job Shop Environments
Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013) · Evolutionary Computation · doi:10.1162/evco_a_00105 · Cited by 42 · cited 1×
“Genetic programming (GP) [18], as a hyper-heuristic approach (GPHH), has been successfully applied to evolve scheduling heuristics automatically for JSS [7], [19], [20], [21].”
MethodSelf-citationSurrogate-Assisted Genetic Programming for Dynamic Flexible Job Shop Scheduling
Zhang, F., Mei, Y., & Zhang, M. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-03991-2_69 · Cited by 38 · cited 4×
“The other is to use a simplified simulation model (e.g., with smaller number of jobs and machines) as the surrogate [30], [24], [31].”
BackgroundMethodInfluentialSelf-citationPeople-Centric Evolutionary System for Dynamic Production Scheduling
Nguyen, S., Zhang, M., Alahakoon, D., & Tan, K. C. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2936001 · Cited by 36 · cited 1×
“This paper extends the idea in [60], [61] to calculate the phenotypic characterisation for an individual in DFJSS by concatenating the phenotypic characterisations of routing and sequencing rules.”
MethodSelf-citationSurrogate-Assisted Multi-Tasking Memetic Algorithm
Liu, D., Huang, S., & Zhong, J. (2018) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2018.8477830 · Cited by 32 · cited 5×
“Moreover, it is not easy to apply existing approaches [40], [41], [42], [43] in DFJSS with GPHH directly.”
BackgroundMethodInfluentialVisualizing the Evolution of Computer Programs for Genetic Programming [Research Frontier]
Nguyen, S., Zhang, M., Alahakoon, D., & Tan, K. C. (2018) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2018.2866731 · Cited by 31 · cited 1×
“This paper extends the idea in [60], [61] to calculate the phenotypic characterisation for an individual in DFJSS by concatenating the phenotypic characterisations of routing and sequencing rules.”
MethodSelf-citationZhang, F., Mei, Y., Nguyen, S., & Zhang, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-43680-3_14 · Cited by 30
Self-citationA hybrid discrete particle swarm optimisation method for grid computation scheduling
Nguyen, S., & Zhang, M. (2014) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2014.6900658 · Cited by 9 · cited 2×
“J ob shop scheduling (JSS) [1] has been widely studied in both academia and industry such as manufacturing processes [2] and grid computing [3] due to its practical applications.”
BackgroundSelf-citation
Cited by
Dynamic Auxiliary Task-Based Evolutionary Multitasking for Constrained Multiobjective Optimization
Qiao, K., Yu, K., Qu, B., Liang, J., Song, H., Yue, C., Lin, H., & Tan, K. C. (2023) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2022.3175065 · Cited by 253
Self-citationKumar, M., Dubey, K., Singh, S., Kumar Samriya, J., & Gill, S. S. (2023) · Concurrency and Computation: Practice and Experience · doi:10.1002/cpe.7469 · Cited by 26
“Several meta-heuristic techniques 23–26 have been applied in diverse domains such as industry, academic, research, and business to solve the NP-complete problem, 2728 combinatorial optimization, 29 pattern recognition, 30 anti-collision problems, 31 and robot motion.”
Method
Metadata
- Authors
- Zhang, F., Mei, Y., Nguyen, S., Zhang, M., & Tan, K. C.
- Venue
- IEEE Transactions on Evolutionary Computation
- Published
- 2021-08
- Volume
- 25
- Issue
- 4
- Pages
- 651-665
- ISSN
- 1089-778X (ISSN-L)
- 1941-0026
- OpenAlex
- W3136165312
- Cited by
- 233
- References
- 36
- FWCI
- 21.81
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.