The goal of the Fourth Industrial Revolution is to develop smart factories that ensure flexibility and adaptability in complex production environments, without human intervention. Smart factories are based on three main pillars: integration through digitalization, employment of flexible structures, and the use of artificial intelligence (AI) methods. Genetic programming (GP) is one of the most promising AI approaches used in the automated design of production-scheduling rules. However, promoting diversity and controlling the bloating effect are major challenges to the success of GP algorithms in developing production-scheduling rules that deliver high-quality solutions. Therefore, we introduced a multi-objective technique to increase the diversity among GP individuals while considering the program length as an objective to avoid the bloating effect. The proposed approach employs a new diversity metric to measure the distance between GP individuals and the best rule in the current generation. Subsequently, the non-dominated sorting genetic algorithm II (NSGA-II) was used to select individuals based on three objectives: solution quality, similarity value, and program length. To assess the effectiveness of the proposed approach, we compare the two versions with three GP methods in the literature in terms of automatically generating dispatching rules on 10 benchmark instances of the job-shop scheduling problem. The experimental results show that the proposed distance measure enhances the phenotypic diversity of individuals, resulting in improved fitness values without the need for additional fitness assessments. In addition, the integration of NSGA-II with the GP algorithm facilitates the evolution of superior job shop dispatching rules with high diversity and shorter lengths under the makespan and mean tardiness objectives.

1. [1] H. Lasi, P. Fettke, H.-G. Kemper, T. Feld, and M. Hoffmann, “Industry 4.0,” Bus. Inf. Syst. Eng., Vol.6, No.4, pp. 239-242, doi: 10.1007/s12599-014-0334-4, 2014.
2. [2] S. Salama and A. B. Eltawil, “A Decision Support System Architecture Based on Simulation Optimization for Cyber-Physical Systems,” Procedia Manufacturing, Vol.26, pp. 1147-1158, doi: 10.1016/j.promfg.2018.07.151, 2018.
3. [3] Z. Shi, Y. Xie, W. Xue, Y. Chen, L. Fu, and X. Xu, “Smart factory in Industry 4.0,” Systems Research and Behavioral Science, Vol.37, No.4, pp. 607-617, doi: 10.1002/sres.2704, 2020.
4. [4] J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Computers and Industrial Engineering, Vol.54, No.3, pp. 453-473, doi: 10.1016/j.cie.2007.08.008, 2008.
5. [5] A. Ishigaki and Y. Matsui, “Effective Neighborhood Generation Method in Search Algorithm for Flexible Job Shop Scheduling Problem,” Int. J. Automation Technol., Vol.13, No.3, pp. 389-396, doi: 10.20965/ijat.2019.p0389, 2019.
6. [6] M. L. Pinedo, “Scheduling: Theory, Algorithms, and Systems,” 4th ed., Springer-Verlag, 2012.
7. [7] V. Sels, N. Gheysen, and M. Vanhoucke, “A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions,” Int. J. of Production Research, Vol.50, No.15, pp. 4255-4270, doi: 10.1080/00207543.2011.611539, 2012.
8. [8] J. H. Drake, A. Kheiri, E. Özcan, and E. K. Burke, “Recent advances in selection hyper-heuristics,” European J. of Operational Research, Vol.285, No.2, pp. 405-428, 2020.
9. [9] J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang, “Automated Design of Production Scheduling Heuristics: A Review,” IEEE Trans. on Evolutionary Computation, Vol.20, No.1, pp. 110-124, doi: 10.1109/TEVC.2015.2429314, 2016.
10. [10] S. Nguyen, Y. Mei, and M. Zhang, “Genetic programming for production scheduling: a survey with a unified framework,” Complex & Intelligent Systems, Vol.3, No.1, pp. 41-66, doi: 10.1007/s40747-017-0036-x, 2017.
11. [11] S. Salama, T. Kaihara, N. Fujii, and D. Kokuryo, “Automatic Design of Dispatching Rules with Genetic Programming for Dynamic Job Shop Scheduling,” Proc. of the IFIP Int. Conf. on Advances in Production Management Systems, Vol.591, pp. 399-407, doi: 10.1007/978-3-030-57993-7_45, 2020.
12. [12] M. D. Schmidt and H. Lipson, “Age-Fitness Pareto Optimization,” Genetic Programming Theory and Practice VIII: 12th Annual Conf. on Genetic and Evolutionary Computation Proc., pp. 129-146, doi: 10.1007/978-1-4419-7747-2_8, 2011.
13. [13] Y. Sakakura, N. Taniguchi, Y. Hoshino, and K. Kamei, “Maintaining Individual Diversity by Fuzzy c-Means Selection,” J. Adv. Comput. Intell. Intell. Inform., Vol.11, No.8, pp. 884-890, 2007.
14. [14] E. K. Burke, S. Gustafson, and G. Kendall, “Diversity in genetic programming: an analysis of measures and correlation with fitness,” IEEE Trans. on Evolutionary Computation, Vol.8, No.1, pp. 47-62, doi: 10.1109/TEVC.2003.819263, 2004.
15. [15] C. E. Berbague, N. E. Karabadji, H. Seridi, P. Symeonidis, Y. Manolopoulos, and W. Dhifli, “An overlapping clustering approach for precision, diversity and novelty-aware recommendations,” Expert Systems with Applications, Vol.177, No.4, 114917, 2021.
16. [16] D. Whitley, S. Rana, and R. B. Heckendorn, “The Island Model Genetic Algorithm: On Separability, Population Size and Convergence,” J. of Computing and Information Technology, Vol.7, pp. 33-47, 1998.
17. [17] E. K. Burke, S. M. Gustafson, G. Kendall, and N. Krasnogor, “Advanced Population Diversity Measures in Genetic Programming,” Parallel Problem Solving from Nature – PPSN VII: 7th Int. Conf. on Parallel Problem Solving from Nature Proc., pp. 341-350, doi: 10.1007/3-540-45712-7_33, 2002.
18. [18] S. Luke and L. Panait, “A Comparison of Bloat Control Methods for Genetic Programming,” Evolutionary Computation, Vol.14, No.3, pp. 309-344, doi: 10.1162/evco.2006.14.3.309, 2006.
19. [19] N. Mori, B. McKay, N. X. Hoai, D. Essam, and S. Takeuchi, “A New Method for Simplifying Algebraic Expressions in Genetic Programming called Equivalent Decision Simplification,” SCIS & ISIS, Vol.2008, pp. 1671-1676, doi: 10.14864/softscis.2008.0.1671.0, 2008.
20. [20] E. F. Crane and N. F. McPhee, “The Effects of Size and Depth Limits on Tree Based Genetic Programming,” T. Yu, R. Riolo, and B. Worzel, (Eds.), “Genetic Programming Theory and Practice III,” Springer US, pp. 223-240, doi: 10.1007/0-387-28111-8_15, 2006.
21. [21] E. Alfaro-Cid, J. J. Merelo, F. F. de Vega, A. I. Esparcia-Alcár, and K. Sharman, “Bloat Control Operators and Diversity in Genetic Programming: A Comparative Study,” Evolutionary Computation, Vol.18, No.2, pp. 305-332, doi: 10.1162/evco.2010.18.2.18206, 2010.
22. [22] A. R. Burks and W. F. Punch, “An Efficient Structural Diversity Technique for Genetic Programming,” Proc. of the 2015 Annual Conf. on Genetic and Evolutionary Computation, pp. 991-998, doi: 10.1145/2739480.2754649, 2015.
23. [23] E. D. de Jong, R. A. Watson, and J. B. Pollack, “Reducing bloat and promoting diversity using multi-objective methods,” Proc. of the 3rd Annual Conf. on Genetic and Evolutionary Computation, pp. 11-18, 2001.
24. [24] K. Miyashita, “Job-shop scheduling with genetic programming,” Proc. of the 2nd Annual Conf. on Genetic and Evolutionary Computation, pp. 505-512, 2000.
25. [25] C. D. Geiger, R. Uzsoy, and H. Aytuğ, “Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach,” J. of Scheduling, Vol.9, No.1, pp. 7-34, doi: 10.1007/s10951-006-5591-8, 2006.
26. [26] M. Durasević, D. Jakobović, and K. Knežević, “Adaptive scheduling on unrelated machines with genetic programming,” Applied Soft Computing, Vol.48, pp. 419-430, doi: 10.1016/j.asoc.2016.07.025, 2016.
27. [27] S. Salama, T. Kaihara, N. Fujii, and D. Kokuryo, “A Proposal on Dispatching Rule Generation Mechanism Using GP for Dynamic Job Shop Scheduling with Machine Breakdowns,” Proc. of the Scheduling Symp. 2020, pp. 155-160, 2020.
28. [28] J. Branke, T. Hildebrandt, and B. Scholz-Reiter, “Hyper-heuristic evolution of dispatching rules: A comparison of rule representations,” Evolutionary Computation, Vol.23, No.2, pp. 249-277, doi: 10.1162/EVCO_a_00131, 2015.
29. [29] A. Ekárt and S. Z. Németh, “A Metric for Genetic Programs and Fitness Sharing,” Genetic Programming: European Conf. on Genetic Programming Proc., pp. 259-270, doi: 10.1007/978-3-540-46239-2_19, 2000.
30. [30] D. Jackson, “Phenotypic Diversity in Initial Genetic Programming Populations,” Genetic Programming: European Conf. on Genetic Programming Proc., pp. 98-109, doi: 10.1007/978-3-642-12148-7_9, 2010.
31. [31] S. Gustafson and L. Vanneschi, “Crossover-Based Tree Distance in Genetic Programming,” IEEE Trans. on Evolutionary Computation, Vol.12, No.4, pp. 506-524, doi: 10.1109/TEVC.2008.915993, 2008.
32. [32] J. Kelly, E. Hemberg, and U.-M. O’Reilly, “Improving Genetic Programming with Novel Exploration – Exploitation Control,” Genetic Programming: European Conf. on Genetic Programming Proc., pp. 64-80, doi: 10.1007/978-3-030-16670-0_5, 2019.
33. [33] L. Vanneschi, M. Castelli, and S. Silva, “A survey of semantic methods in genetic programming,” Genet. Program. Evolvable Mach., Vol.15, No.2, pp. 195-214, doi: 10.1007/s10710-013-9210-0, 2014.
34. [34] B. Sareni and L. Krahenbuhl, “Fitness sharing and niching methods revisited,” IEEE Trans. on Evolutionary Computation, Vol.2, No.3, pp. 97-106, doi: 10.1109/4235.735432, 1998.
35. [35] M. Hughes, “Investigating the Effects Diversity Mechanisms Have on Evolutionary Algorithms in Dynamic Environments,” arXiv: 1610.02732, 2021.
36. [36] P. Wong and M. Zhang, “Algebraic simplification of GP programs during evolution,” Proc. of the 8th Annual Conf. on Genetic and Evolutionary Computation, pp. 927-934, doi: 10.1145/1143997.1144156, 2006.
37. [37] Y. Mei, S. Nguyen, B. Xue, and M. Zhang, “An Efficient Feature Selection Algorithm for Evolving Job Shop Scheduling Rules With Genetic Programming,” IEEE Trans. on Emerging Topics in Computational Intelligence, Vol.1, No.5, pp. 339-353, doi: 10.1109/tetci.2017.2743758, 2017.
38. [38] S. Salama, T. Kaihara, N. Fujii, and D. Kokuryo, “A New Representation and Adaptive Feature Selection for Evolving Compact Dispatching Rules for Dynamic Job Shop Scheduling with Genetic Programming,” Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems, Cham, pp. 646-654, doi: 10.1007/978-3-030-85906-0_70, 2021.
39. [39] J. R. Koza, “Genetic programming as a means for programming computers by natural selection,” Stat. Comput., Vol.4, No.2, pp. 87-112, doi: 10.1007/BF00175355, 1994.
40. [40] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. on Evolutionary Computation, Vol.6, No.2, pp. 182-197, doi: 10.1109/4235.996017, 2002.
41. [41] F. Zhang, Y. Mei, and M. Zhang, “Evolving Dispatching Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling via Genetic Programming Hyper-Heuristics,” Proc. of the 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 1366-1373, doi: 10.1109/CEC.2019.8790112, 2019.
42. [42] E. Taillard, “Benchmarks for basic scheduling problems,” European J. of Operational Research, Vol.64, No.2, pp. 278-285, doi: 10.1016/0377-2217(93)90182-M, 1993.