EUVIMEDEUVIMED entdecken
Crossref

Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop Scheduling

Meng Xu, Yi Mei, Fangfang Zhang, Mengjie Zhang

IEEE Transactions on Evolutionary Computation · 2024-10 · 28 (5) · 1235-1249

DOI: 10.1109/tevc.2023.3244607 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2024-10. Verfasst von Meng Xu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 51-mal zitiert (Crossref) und nennt 73 Literaturangaben. Gefördert von: Marsden Fund of New Zealand Government, MBIE SSIF Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Dynamic flexible job shop scheduling (JSS) is a prominent combinatorial optimization problem with many real-world applications. Genetic programming (GP) has been widely used to automatically evolve effective scheduling heuristics for dynamic flexible JSS (DFJSS). A limitation of GP is the premature convergence due to the loss of population diversity. To overcome this limitation, this work considers using lexicase selection (LS) to improve population diversity, which has achieved success on regression and program synthesis problems. However, it is not trivial to apply LS to GP for DFJSS, since a fitness case (training scheduling simulation) is often large-scale, making the fitness evaluation very time-consuming. To address this issue, we propose a new multicase fitness scheme, which creates multiple cases from a single scheduling simulation. Based on the multicase fitness, we develop a new GP algorithm with LS, which uses a single simulation for fitness evaluation, thus, achieving a better balance between the number of cases for LS and evaluation efficiency. The experiments on a wide range of dynamic scheduling scenarios show that the proposed algorithm can achieve better population diversity and final performance than the current GP parent selection methods and a state-of-the-art deep reinforcement learning method.

Förderung

  • Marsden Fund of New Zealand Government
  • MBIE SSIF Fund

Zitieren

APA

Xu, M., Mei, Y., Zhang, F., & Zhang, M. (2024). Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation, 28(5), 1235-1249. https://doi.org/10.1109/tevc.2023.3244607

Vancouver

Xu M, Mei Y, Zhang F, Zhang M. Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation. 2024;28(5):1235-1249. doi:10.1109/tevc.2023.3244607

BibTeX
@article{Xu2024,
  author = {Xu, Meng and Mei, Yi and Zhang, Fangfang and Zhang, Mengjie},
  title = {Genetic Programming With Lexicase Selection for Large-Scale Dynamic Flexible Job Shop Scheduling},
  journal = {IEEE Transactions on Evolutionary Computation},
  year = {2024},
  volume = {28},
  number = {5},
  pages = {1235--1249},
  doi = {10.1109/tevc.2023.3244607}
}
Kostenlos starten →