The multi-objective dynamic flexible job shop scheduling (MO-DFJSS) problem is crucial in modern manufacturing, impacting productivity and operational costs. Genetic Programming (GP) has emerged as a prominent method for MO-DFJSS due to its ability to evolve real-time responsible and effective scheduling heuristics. However, existing GP approaches often learn multiple heuristics for different regions of the Pareto front, making their management and selection complicated in real-world applications. This paper proposes a novel Pareto set learning GP (PSLGP) framework that addresses this limitation by learning a single, preference-conditioned heuristic that encompasses the entire Pareto front based on user preferences. This simplifies scheduling and allows for real-time adaptation to user-defined priorities. The framework employs a novel preference-conditioned heuristic representation that incorporates user preferences as additional inputs, enabling dynamic heuristic adjustments. To efficiently evaluate fitness without increasing training time, a surrogate model is used to estimate individual performance across different preferences, and three new fitness aggregation strategies are designed to ensure effective heuristic alignment across the Pareto front. Experimental results demonstrate that PSLGP significantly outperforms the state-of-the-art multi-objective GP approach, particularly in less busy MO-DFJSS environments, providing a more adaptable and efficient solution for dynamic scheduling challenges. Further analyses of preference influence, solution distribution, and heuristic structure provide evidence that the proposed PSLGP effectively learns preference-conditioned scheduling heuristics that align user preferences with various regions of the Pareto front.

Dynamic Flexible Job Shop Scheduling (DFJSS) is a critical combinatorial optimisation problem known for its dynamic nature and flexibility of machines. Traditional scheduling methods face limitations in adapting to such dynamic and flexible environments. Recently, there has been a trend in employing reinforcement learning (RL) to train scheduling agents for selecting manual scheduling heuristics at various decision points for DFJSS. However, the effectiveness of RL is constrained by the limited efficacy of the manually designed scheduling heuristics. Additionally, the process of manually designing diverse scheduling heuristics as the actions demands significant expert knowledge. In response, this paper proposes a Niching genetic programming (GP)-assisted RL method that leverages the evolutionary capabilities of GP to help RL solve the DFJSS problem effectively. Specifically, instead of using those manual scheduling heuristics, the RL actions are replaced with scheduling heuristics evolved by the Niching GP to optimise and adapt these heuristics based on real-time feedback from the environment. Experimental results demonstrate the effectiveness of the proposed method in comparison to the widely used manual scheduling heuristics and the baseline deep RL method. Further analyses reveal that the effectiveness of the proposed method is due to the behavioral differences among heuristics learned by the Niching GP, serving as actions for the RL. In addition, the effectiveness of the proposed algorithm benefits from the comparable percentages of contributions made by these learned heuristics throughout the long-term scheduling process.

Real-world multi-objective optimization problems often rely on physics-based simulators or physical experiments to assess solution quality, resulting in significant computational costs. In such scenarios, Gaussian process (GP) surrogate-assisted optimizers have demonstrated exceptional optimization performance. This article focuses on the theoretical convergence analysis of two existing decomposition-based GP-assisted optimizers: ParEGO with the upper confidence bound (ParEGO-UCB) and ExTrEMO. Unlike prior studies that typically assume a single weight vector for scalarization, this work primarily investigates multi-weight vector settings. Specifically, we analyze the regret bound of ParEGO-UCB within a rigorous theoretical framework and prove that, under a multi-weight vector setting, its convergence rate surpasses that of GP-UCB, which independently and sequentially optimizes multiple decomposed subproblems. Building on this foundation, we further explore the convergence properties of ExTrEMO, an expensive multi-objective optimizer designed for multi-source transfer optimization, in the context of multi-weight vector settings. Theoretical findings reveal that ExTrEMO achieves a tighter regret bound in multi-source settings compared to single-source scenarios, highlighting the advantages of leveraging additional sources to enhance optimization efficiency and convergence.

Real-world optimization often demands diverse, high-quality solutions. Quality-Diversity (QD) optimization is a multifaceted approach in evolutionary algorithms that aims to generate a set of solutions that are both high-performing and diverse. QD algorithms have been successfully applied across various domains, providing robust solutions by exploring diverse behavioral niches. However, their application has primarily focused on static problems, with limited exploration in the context of dynamic combinatorial optimization problems. Furthermore, the theoretical understanding of QD algorithms remains underdeveloped, particularly when applied to learning heuristics instead of directly learning solutions in complex and dynamic combinatorial optimization domains, which introduces additional challenges. This paper introduces a novel QD framework for dynamic scheduling problems. We propose a map-building strategy that visualizes the solution space by linking heuristic genotypes to their behaviors, enabling their representation on a QD map. This map facilitates the discovery and maintenance of diverse scheduling heuristics. Additionally, we conduct experiments on both fixed and dynamically changing training instances to demonstrate how the map evolves and how the distribution of solutions unfolds over time. We also discuss potential future research directions that could enhance the learning process and broaden the applicability of QD algorithms to dynamic combinatorial optimization challenges.

Dynamic flexible job shop scheduling is a prominent combinatorial optimisation problem with many real-world applications. Genetic programming has been widely used to automatically evolve effective scheduling heuristics for dynamic flexible job shop scheduling. A limitation of genetic programming is the premature convergence due to the loss of population diversity. To overcome this limitation, this work considers using lexicase selection to improve population diversity, which has achieved success on regression and program synthesis problems. However, it is not trivial to apply lexicase selection to genetic programming for dynamic flexible job shop scheduling, 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 multi-case fitness scheme, which creates multiple cases from a single scheduling simulation. Based on the multi-case fitness, we develop a new genetic programming algorithm with lexicase selection, which uses a single simulation for fitness evaluation, thus achieving a better balance between the number of cases for lexicase selection 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 genetic programming parent selection methods and a state-of-the-art deep reinforcement learning method.

Dynamic flexible job shop scheduling is an important but difficult combinatorial optimisation problem that has numerous real-world applications. Genetic programming has been widely used to evolve scheduling heuristics to solve this problem. Ensemble methods have shown promising performance in many machine learning tasks, but previous attempts to combine genetic programming with ensemble techniques are still limited and require further exploration. This paper proposes a novel ensemble genetic programming method that uses a population consisting of both single individuals and ensembles. The main contributions include: 1) developing a genetic programming method that evolves a population comprising both single individuals and ensembles, allowing breeding between them to explore the search space more effectively; 2) proposing an ensemble construction and selection strategy to form ensembles by selecting diverse and complementary individuals; and 3) designing new crossover and mutation operators to produce offspring from single individuals and ensembles. Experimental results demonstrate that the proposed method outperforms existing traditional and ensemble genetic programming methods in most scenarios. Further analyses find that the success is attributed to the enhanced population diversity and extensive search space exploration achieved by the proposed method.

DynamicWorkflowScheduling inFogComputing (DWSFC) is an important optimisation problem with many real-world applications. The current workflow scheduling problems only consider cloud servers but ignore the roles of mobile devices and edge servers. Some applications need to consider the mobile devices, edge, and cloud servers simultaneously, making them work together to generate an effective schedule. In this article, a new problem model for DWSFC is considered and a new simulator is designed for the new DWSFC problem model. The designed simulator takes the mobile devices, edge, and cloud servers as a whole system, where they all can execute tasks. In the designed simulator, two kinds of decision points are considered, which are the routing decision points and the sequencing decision points. To solve this problem, a newMulti-TreeGeneticProgramming (MTGP) method is developed to automatically evolve scheduling heuristics that can make effective real-time decisions on these decision points. The proposed MTGP method with a multi-tree representation can handle the routing decision points and sequencing decision points simultaneously. The experimental results show that the proposed MTGP can achieve significantly better test performance (reduce the makespan by up to 50%) on all the tested scenarios than existing state-of-the-art methods.

Dynamic flexible job shop scheduling is a challenging combinatorial optimisation problem, that aims to optimise machine resources for producing jobs to meet some goals. There are two important kinds of decisions that the scheduling process needs to make under dynamic environments, i.e., the routing decision for machine assignment and the sequencing decision for operation ordering. Genetic programming hyper-heuristic has been successfully applied for solving the dynamic flexible job shop scheduling problem with the advantage of automat-ically evolving good scheduling heuristics. Parent selection is an important process for genetic programming, intending to select good individuals as parents to generate offspring for the next generation. Traditional genetic programming methods select parents for crossover based on only fitness (e.g., tournament selection). In this paper, a new parent selection (i.e., cluster selection) method is proposed to select parents not only with good fitness but also with different behaviours. The proposed cluster selection is combined with genetic programming hyper-heuristic to study whether considering different behaviours in parent selection will improve the effectiveness of the evolved scheduling heuristics. The experimental results show that increasing the number of unique behaviours in the population cannot help evolve effective scheduling heuristics. Further analysis shows that considering behaviour to select parents does increase the number of unique behaviours in the population. However, it gives individuals with poor fitness more probability to be selected to generate offspring. This might be the reason why the proposed method cannot outperform the baseline method.

Dynamic flexible job shop scheduling has attracted widespread interest from scholars and industries due to its practical value. Genetic programming hyper-heuristic has achieved great success in automatically evolving effective scheduling heuristics to make real-time decisions (i.e., operation ordering and machine assignment) for dynamic flexible job shop scheduling. The design of the training set and fitness evaluation play key roles in improving the generalisation of the evolved scheduling heuristics. The commonly used strategies for improving the generalisation of learned scheduling heuristics include using multiple instances for evaluation at each generation or using a single instance but changing the instance at each new generation of the training process of genetic programming. However, using multiple instances is time-consuming, while changing a single instance at each new generation, potentially promising individuals that happen to underperform in one particular generation might be lost. To address this issue, this paper develops a genetic programming method with a multi-case fitness evaluation strategy, which is named GPMF to evolve the scheduling heuristics with better generalisation ability for the dynamic flexible job shop scheduling problem. The proposed multi-case fitness evaluation strategy divides one instance into multiple cases and uses the average value of the multi-case objectives as the fitness. Experimental results show that the proposed GPMF algorithm is significantly better than the baseline method in all the tested scenarios.

Genetic programming (GP) has achieved great success in evolving effective scheduling rules to make real-time decisions in dynamic flexible job shop scheduling (DFJSS). To improve generalization, a commonly used strategy is to change the training simulation(s) at each generation of the GP process. However, with such a simulation rotation, GP may lose potentially promising individuals that happen to perform poorly in one particular generation. To address this issue, this paper proposed a new multi-tree GP with archive (MTAGP) to evolve the routing and sequencing rules for DFJSS. The archive is used to store the potentially promising individuals of each generation during evolution of genetic programming. The individuals in the archive can then be fully utilized when the simulation is changed in subsequent generations. Through extensive experimental tests, the MTAGP algorithm proposed in this paper is more effective than the multi-tree GP without archive algorithm in a few scenarios. Further experiments were carried out to analyze the use of the archive and some possible guesses were ruled out. We argue that the use of archives does increase the diversity of the population. However, the number of individuals in the archive that ranked in the top five of the new population is small. Therefore, the archive may not be able to greatly improve the performance. In the future, we will investigate better ways to use the archive and better ways to update individuals in the archive.