[2020] Guided Subtree Selection for Genetic Operators in Genetic Programming for Dynamic Flexible Job Shop Scheduling.pdf (605.79 kB)

Guided Subtree Selection for Genetic Operators in Genetic Programming for Dynamic Flexible Job Shop Scheduling

Download (605.79 kB)
conference contribution
posted on 29.10.2020, 01:00 by Fangfang Zhang, Yi Mei, S Nguyen, Mengjie Zhang
© 2020, Springer Nature Switzerland AG. Dynamic flexible job shop scheduling (DFJSS) has been widely studied in both academia and industry. Both machine assignment and operation sequencing decisions need to be made simultaneously as an operation can be processed by a set of machines in DFJSS. Using scheduling heuristics to solve the DFJSS problems becomes an effective way due to its efficiency and simplicity. Genetic programming (GP) has been successfully applied to evolve scheduling heuristics for job shop scheduling automatically. However, the subtrees of the selected parents are randomly chosen in traditional GP for crossover and mutation, which may not be sufficiently effective, especially in a huge search space. This paper proposes new strategies to guide the subtree selection rather than picking them randomly. To be specific, the occurrences of features are used to measure the importance of each subtree of the selected parents. The probability to select a subtree is based on its importance and the type of genetic operators. This paper examines the proposed algorithm on six DFJSS scenarios. The results show that the proposed GP algorithm with the guided subtree selection for crossover can converge faster and achieve significantly better performance than its counterpart in half of the scenarios while no worse in all other scenarios without increasing the computational time.

History

Preferred citation

Zhang, F., Mei, Y., Nguyen, S. & Zhang, M. (2020, January). Guided Subtree Selection for Genetic Operators in Genetic Programming for Dynamic Flexible Job Shop Scheduling. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (12101 LNCS pp. 262-278). Springer International Publishing. https://doi.org/10.1007/978-3-030-44094-7_17

Title of proceedings

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

12101 LNCS

Publication or Presentation Year

01/01/2020

Pagination

262-278

Publisher

Springer International Publishing

Publication status

Published

ISSN

0302-9743

eISSN

1611-3349

Exports

Logo branding

Categories

Exports