zhang-2020-surrogate.pdf (1.31 MB)
Download fileSurrogate-Assisted Evolutionary Multitask Genetic Programming for Dynamic Flexible Job Shop Scheduling
journal contribution
posted on 2022-05-04, 09:40 authored by Fangfang ZhangFangfang Zhang, Yi MeiYi Mei, S Nguyen, Mengjie ZhangMengjie Zhang, KC TanDynamic 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.
History
Preferred citation
Zhang, F., Mei, Y., Nguyen, S., Zhang, M. & Tan, K. C. (2021). Surrogate-Assisted Evolutionary Multitask Genetic Programming for Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation, 25(4), 651-665. https://doi.org/10.1109/TEVC.2021.3065707Publisher DOI
Journal title
IEEE Transactions on Evolutionary ComputationVolume
25Issue
4Publication date
2021-08-01Pagination
651-665Publisher
Institute of Electrical and Electronics Engineers (IEEE)Publication status
PublishedISSN
1089-778XeISSN
1941-0026Usage metrics
Categories
Keywords
Task analysisJob shop schedulingDynamic schedulingHeuristic algorithmsProcessor schedulingSequential analysisStatisticsDynamic flexible job shop scheduling (DFJSS)genetic programming (GP)hyperheuristicsmultitask learningsurrogateArtificial Intelligence & Image ProcessingInformation SystemsArtificial Intelligence and Image ProcessingElectrical and Electronic Engineering not elsewhere classified