Adaptive Charting Genetic Programming for Dynamic Flexible Job Shop Scheduling

Genetic programming has been considered as a powerful approach to automated design of production scheduling heuristics in recent years. Flexible and variable representations allow genetic programming to discover very competitive scheduling heuristics to cope with a wide range of dynamic production environments. However, evolving sophisticated heuristics to handle multiple scheduling decisions can greatly increase the search space and poses a great challenge for genetic programming. To tackle this challenge, a new genetic programming algorithm is proposed to incrementally construct the map of explored areas in the search space and adaptively guide the search towards potential heuristics. In the proposed algorithm, growing neural gas and principal component analysis are applied to efficiently generate and update the map of explored areas based on the phenotypic characteristics of evolved heuristics. Based on the obtained map, a surrogate assisted model will help genetic programming determine which heuristics to be explored in the next generation. When applied to evolve scheduling heuristics for dynamic flexible job shop scheduling problems, the proposed algorithm shows superior performance as compared to the standard genetic programming algorithm. The analyses also show that the proposed algorithm can balance its exploration and exploitation better than the existing surrogate-assisted algorithm.