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.

Cloud-Fog computing has emerged as an essential paradigm to support the growing demand for real-time data processing driven by the Internet of Things. By integrating the extensive computing capabilities of cloud data centres with the low-latency benefits of fog nodes, this architecture increases resource utilisation and improves quality of service. However, the dynamic and heterogeneous nature of cloud fog environments poses significant workflow scheduling challenges, especially when optimising multiple trade-offs such as latency, cost, energy consumption, and resource utilisation. This paper investigates the many-objective dynamic workflow scheduling problem under deadline constraints in container-based cloud-fog computing environments (MDWS-CoCF). Unlike existing studies that primarily focus on horizontal scaling, this work considers both vertical and horizontal scaling of containers, allowing for real-time adjustments of container configurations based on task-specific requirements. To address this complex problem, we first develop a dynamic workflow scheduling simulator that models real-world scenarios, including a variety of task categories and container scalability. Based on this simulator, we propose a Cooperative Coevolution Genetic Programming (CCGP) approach that evolves specialised heuristics for task selection, resource allocation, and container deployment to facilitate adaptive and efficient scheduling in MDWS-CoCF. Extensive simulations using real-world data traces show that the proposed CCGP approach significantly outperforms existing baseline algorithms, achieving superior performance as measured by the HyperVolume and Inverted Generational Distance metrics. The results show that the evolved heuristics are robust and effective under different dynamic scenarios, ensuring balanced optimisation of many objectives.

This paper studies the Dynamic Electric Dial-A-Ride Problem (DEDARP), which is a combinatorial optimisation problem that has applications in real-world ridesharing services with electric vehicles. In addition to the challenges from classical scheduling and route planning, we consider here the extra challenge of making real-time dispatching decisions in dynamic environments with new requests arriving over time and selecting proper times for the vehicles to recharge. To solve DEDARP effectively, we propose a Genetic Programming Hyper-Heuristic (GPHH) that evolves heuristics/policies to dispatch vehicles in real time. We have developed a simulation process that generates a solution for any given instance by two policies, one for vehicle allocation and the other for request allocation, and design fitness evaluations based on the simulation. Moreover, we propose a multi-tree GP to evolve these two policies simultaneously, which makes use of advanced terminals to comprehensively represent the state. Experimental results on a wide range of instances show that GPHH can evolve effective policies that make significantly better real-time dispatching decisions than human-designed policies based on prior knowledge.

Energy-Efficient dynamic flexible job shop scheduling (E-DFJSS) is a valuable real-world combinational optimisation problem. As an important variant of DFJSS, E-DFJSS aims to optimise trade-off between production effectiveness and energy consumption. Genetic Programming (GP) has been successfully used to learn dispatching rules in E-DFJSS. Nevertheless, different users have different preferences on the trade-off between production effectiveness and energy consumption, the studies of preference-based multi-objective optimisation algorithms are limited. These existing related preference-based methods face the issue of premature convergence in the early stage when solving E-DFJSS, which results in insufficient diversity. To address these challenges, we develop a preference-based multi-objective GP approach for E-DFJSS. A fusion r-dominance and achievement scalarising function dominance criterion is embedded into the proposed algorithm to solve E-DFJSS. Experimental results on training and test on three scenarios with four preferences show that the proposed method could improve the effectiveness of learned scheduling heuristics by balancing diversity and convergence of evolutionary progress.

Alzheimer’s disease (AD) is a progressive neurological disorder and a major contributor to dementia cases across the world. Timely and accurate diagnosis is crucial for effective clinical management and therapeutic intervention. This paper presents a genetic programming (GP) method with a multi-tree representation designed to effectively integrate multimodal neuroimaging data while preserving spatial information for AD classification. Unlike existing GP approaches that focus on single-modality data, our GP approach directly uses the images from multiple imaging sources as inputs into the evolutionary process. A new GP representation is designed to handle multimodal data effectively, enabling feature extraction and classification. Experiments on the commonly used public database of Alzheimer’s disease neuroimaging initiative (ADNI) show that the proposed method performs effectively in diagnosing AD. These findings suggest that multi-tree GP has the potential to serve as a powerful and interpretable tool for neuroimaging-based AD diagnosis, offering a promising approach to improve AD detection and clinical decision-making.

Genetic programming (GP) has been popularly used to learn scheduling rules for dynamic flexible job shop scheduling. These scheduling rules serve as priority functions to prioritise candidate machines or operations at decision points. In the implementation level, a high prioritised machine and operation can be the ones with the highest or lowest priority value calculated with a scheduling rule in the decision making process. In theory, GP can adaptively evolve scheduling rules to accommodate different priority settings. However, research exploring the possible hidden differences during the evolutionary process remains limited. To fill this gap, this paper presents a comprehensive investigation into scheduling rules learned by GP under varying priority settings. The results show that while GP achieves similar performance in most investigated scenarios with different priority settings, GP-low where candidates with the lowest priority values are selected, can learn effective scheduling rules faster. Specifically, GP-low can learn smaller sequencing rules. Furthermore, visualisations of the scheduling rules illustrate how GP adaptively adjusts node positions to evolve effective rules. The study also highlights an inherent bias in initialised scheduling rules, which tend to prefer candidates with lower priority values in the examined scenarios. Moreover, GP-low exhibits a broader distribution of priority values. These findings can provide deeper insights into GP’s adaptive learning mechanisms and offer valuable guidance for decision-making of using scheduling rules.

Linear genetic programming (LGP) has been successfully applied to dynamic job shop scheduling (DJSS) to automatically evolve dispatching rules. Flow control operations are crucial in concisely describing complex knowledge of dispatching rules, such as different dispatching rules in different conditions. However, existing LGP methods for DJSS have not fully considered the use of flow control operations. They simply included flow control operations in their primitive set, which inevitably leads to a huge number of redundant and obscure solutions in LGP search spaces. To move one step toward evolving effective and interpretable dispatching rules, this paper explicitly considers the characteristics of flow control operations via grammar-guided linear genetic programming and focuses on IF operations as a starting point. Specifically, this paper designs a new set of normalized terminals to improve the interpretability of IF operations and proposes three restrictions by grammar rules on the usage of IF operations: specifying the available inputs, the maximum number, and the possible locations of IF operations. The experiment results verify that the proposed method can achieve significantly better test performance than state-of-the-art LGP methods and improves interpretability by IF-included dispatching rules. Further investigation confirms that the explicit introduction of IF operations helps effectively evolve different dispatching rules according to their decision situations.

Searching for symbolic models plays an important role in a wide range of domains such as neural architecture search and automatic program synthesis. Genetic programming is a promising stochastic method for searching effective symbolic models within an acceptable time. The genetic programming performance is closely related to the hardness of the fitness landscape. A better fitness landscape with less local optima normally implies that it is easier to search for better solutions. In recent years, there have been many studies enhancing genetic programming performance by forming better fitness landscapes. However, the better design of the fitness landscape highly relies on specific domain knowledge and consumes a lot of expert effort. This paper proposes a fitness landscape optimization method to automatically design better fitness landscapes for genetic programming search than the manually designed ones. We optimize the landscapes by optimizing the neighborhood structures of symbolic solutions. We verify the effectiveness of the proposed method in both supervised learning and combinatorial optimization problems. The results show that the proposed method significantly reduces the hardness of fitness landscapes. By simply searching against the automatically optimized fitness landscapes, a genetic programming method can have a very competitive performance with state-of-the-art methods.

Dynamic flexible job shop scheduling (DFJSS) aims to achieve the optimal efficiency for production planning in the face of dynamic events. In practice, deep Q-network (DQN) algorithms have been intensively studied for solving various DFJSS problems. However, these algorithms often cause moving targets for the given job-shop state. This will inevitably lead to unstable training and severe deterioration of the performance. In this paper, we propose a training algorithm based on genetic algorithm to efficiently and effectively address this critical issue. Specifically, a state feature extraction method is first developed, which can effectively represent different job shop scenarios. Furthermore, a genetic encoding strategy is designed, which can reduce the encoding length to enhance search ability. In addition, an evaluation strategy is proposed to calculate a fixed target for each job-shop state, which can avoid the parameter update of target networks. With the designs, the DQNs could be stably trained, thus their performance is greatly improved. Extensive experiments demonstrate that the proposed algorithm outperforms the state-of-the-art peer competitors in terms of both effectiveness and generalizability to multiple scheduling scenarios with different scales. In addition, the ablation study also reveals that the proposed algorithm can outperform the DQN algorithms with different updating frequencies of target networks.

Dynamic flexible job shop scheduling (DFJSS) is an important combinatorial optimisation problem that aims to optimise machine resources to improve production efficiency. Multi-tree genetic programming (MTGP) has been widely used to learn the routing rule and the sequencing rule for DFJSS simultaneously. Unlike traditional genetic programming that only operates crossover on a single tree, MTGP has various cases to conduct crossover since a genetic programming individual consists of more than one tree. Different crossover operators may affect the performance of MTGP for DFJSS. However, the investigation into different crossover operators in MTGP for DFJSS is rare. Specifically, it is not clear what influence will have on MTGP if involving both the routing rule and the sequencing rule for crossover. To this end, this paper provides a comprehensive investigation of four possible crossover cases between multiple scheduling heuristics with MTGP for DFJSS. The four operators are designed according to the number of trees/rules that crossover operator works on, and whether swapping full trees between parents. The results show that although the compared algorithms have comparable results in most scenarios, MTGP with both rules for crossover and the swapping strategy is ranked as the best one. Further analyses show that the sizes of learned rules are highly related to the crossover operators, and crossover involving more rules can increase the rule sizes, and vice versa. In addition, the population diversity and the number of unique features in the learned rules of MTGP with both rules for crossover are increased to learn effective rules.

Multitask genetic programming methods have been applied to various domains, such as classification, regression, and combinatorial optimization problems. Most existing multitask genetic programming methods are designed based on tree-based structures, which are not good at reusing building blocks since each sub-tree passes its outputs to only one parent. It may limit the design and performance of knowledge sharing in multitask optimization. Different from tree-based genetic programming, building blocks in linear genetic programming can be easily reused by more than one parent. Besides, existing multitask genetic programming methods always allocate each individual to a specific task and have to duplicate genetic materials from task to task in knowledge transfer, which is inefficient and often produces redundancy. Contrarily, it is natural for a linear genetic programming individual to produce multiple distinct outputs, which enables each linear genetic programming individual to solve multiple tasks simultaneously. With this in mind, we propose a new multitask linear genetic programming method that transfers knowledge via multi-output individuals (i.e., shared individuals among tasks). By integrating different solutions into one multi-output individual, the proposed method efficiently reuses common knowledge among tasks and maintains distinct behaviors for each task. The empirical results show that the proposed method has a significantly better test performance than state-of-the-art multitask genetic programming methods. Further analyses verify that the new knowledge transfer mechanism can adjust the transfer rate automatically and thus improves its effectiveness.

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.

Job shop scheduling (JSS) is a process of optimizing the use of limited resources to improve the production efficiency. JSS has a wide range of applications, such as order picking in the warehouse and vaccine delivery scheduling under a pandemic. In real-world applications, the production environment is often complex due to dynamic events, such as job arrivals over time and machine breakdown. Scheduling heuristics, e.g., dispatching rules, have been popularly used to prioritize the candidates such as machines in manufacturing to make good schedules efficiently. Genetic programming (GP), has shown its superiority in learning scheduling heuristics for JSS automatically due to its flexible representation. This survey first provides comprehensive discussions of recent designs of GP algorithms on different types of JSS. In addition, we notice that in the recent years, a range of machine learning techniques, such as feature selection and multitask learning, have been adapted to improve the effectiveness and efficiency of scheduling heuristic design with GP. However, there is no survey to discuss the strengths and weaknesses of these recent approaches. To fill this gap, this article provides a comprehensive survey on GP and machine learning techniques on automatic scheduling heuristic design for JSS. In addition, current issues and challenges are discussed to identify promising areas for automatic scheduling heuristic design in the future.

Multi-cloud is a promising paradigm due to its advantages such as avoiding vendor lock-in and optimising costs. This article focuses on dynamic flexible workflow scheduling with minimum total monetary cost in multi-clouds, considering multiple categories of services for each cloud with different configurations and billing methods. Existing studies generally ignore the characteristics and states of each individual cloud when making schedules, which may be ineffective regarding cost savings and quality of service. To address this issue, we propose to introduce a cloud selection decision on top of the existing task selection and resource selection decisions to help us select appropriate resource for task in an overall cost-effective cloud. To automatically learn the task, cloud and resource selection rules simultaneously, we propose a new genetic programming with multi-tree representation based on a customised discrete event-driven dynamic workflow scheduling simulator. Simulation results based on two real-world data traces show that the proposed algorithm performs significantly better than the state-of-the-art algorithms in terms of reducing the rental costs and deadline deviation, and improving the success rate. The results also show that the superiority of the proposed algorithm lies in the ability to select an appropriate cloud resource for a task.

Dynamic flexible job shop scheduling (DFJSS) is a critical and challenging combinatorial optimisation problem. Genetic programming (GP) has been widely used to learn scheduling heuristics for DFJSS automatically. Ideally, we prefer to have effective and small scheduling heuristics which tend to be easy to be interpreted. However, the effectiveness and the sizes of scheduling heuristics are conflicting, and reducing the rule sizes tends to worsen the effectiveness of scheduling heuristics. This is a typical multi-objective optimisation problem. However, the existing studies in multi-objective DFJSS consider the effectiveness-related objectives only such as minimising max-flowtime and mean-flowtime rather than interpretability-related objectives such as rule size. To fill this gap, this paper aims to propose an interpretability-aware multi-objective GP to learn a well-distributed Pareto-front of scheduling heuristics for DFJSS. This paper first adopts a multi-objective GP algorithm with α-dominance and archive from a routing problem to DFJSS. Then, we propose to use traditional dominance relation based Pareto front for α and archive updating and an objective normalisation based α-dominance sorting strategy to further improve the performance of the adopted multi-objective GP. The results show that the proposed algorithm can obtain significantly better performance than the state-of-the-art multi-objective GP algorithms in different DFJSS scenarios.

Dispatching rules are commonly used to make instant decisions in dynamic scheduling problems. Linear genetic programming (LGP) is one of the effective methods to design dispatching rules automatically. However, the effectiveness and efficiency of LGP methods are limited due to the large search space. Exploring the entire search space of programs is inefficient for LGP since a large number of programs might contain redundant blocks and might be inconsistent with domain knowledge, which would further limit the effectiveness of the produced LGP models. To improve the performance of LGP in dynamic job shop scheduling problems, this paper proposes a grammar-guided LGP to make LGP focus more on promising programs. Our dynamic job shop scheduling simulation results show that the proposed grammar-guided LGP has better training efficiency than basic LGP, and can produce solutions with good explanations. Further analyses show that grammar-guided LGP significantly improves the overall test effectiveness when the number of LGP registers increases.

Of great value to modern municipalities is the task of emergency medical response in the community. Resource allocation is vital to ensure minimal response times, which we may perform via human experts or automate by maximising ambulance coverage. To combat black-box modelling, we propose a modularised Genetic Programming Hyper Heuristic framework to learn the five key decisions of Emergency Medical Dispatch (EMD) within a reactive decision-making process. We minimise the representational distance between our work and reality by working with our local ambulance service to design a set of heuristics approximating their current decision-making processes and a set of synthetic datasets influenced by existing patterns in practice. Through our modularised framework, we learn each decision independently to identify those most valuable to EMD and learn all five decisions simultaneously, improving performance by 69% on the largest novel dataset. We analyse the decision-making logic behind several learned rules to further improve our understanding of EMD. For example, we find that emergency urgency is not necessarily considered when dispatching idle ambulances in favour of maximising fleet availability.

Genetic programming (GP) has been successfully introduced to learn scheduling heuristics for dynamic flexible job shop scheduling (DFJSS) automatically. However, the evaluations of GP individuals are normally time-consuming, especially with long DFJSS simulations. Taking k-nearest neighbour with phenotypic characterisations of GP individuals as a surrogate approach, has been successfully used to preselect GP offspring to the next generation for effectiveness improvement. However, this approach is not straightforward to improve the training efficiency, which is normally the primary goal of surrogate. In addition, there is no study on which GP individuals (samples) are good for building surrogate models. To this end, first, this paper proposes a surrogate-assisted GP algorithm to reduce the training time of learning scheduling heuristics for DFJSS. Second, this paper further proposes an effective sampling strategy for surrogate-assisted GP. The results show that our proposed algorithm can achieve comparable performance with only about a third of training time of traditional GP. With the same training time, the proposed algorithm can significantly improve the quality of learned scheduling heuristics in all examined scenarios. Furthermore, the evolved scheduling heuristics by the proposed sample-aware surrogate-assisted GP are more interpretable with smaller rule sizes than traditional GP.

Evolutionary multitask multiobjective learning has been widely used for handling more than one multiobjective task simultaneously. However, it is rarely used in dynamic combinatorial optimization problems, which have valuable practical applications such as dynamic flexible job-shop scheduling (DFJSS) in manufacturing. Genetic programming (GP), as a popular hyperheuristic approach, has been used to learn scheduling heuristics for generating schedules for multitask single-objective DFJSS only. Searching in the heuristic space with GP is more difficult than in the solution space, since a small change on heuristics can lead to ineffective or even infeasible solutions. Multiobjective DFJSS is more challenging than single DFJSS, since a scheduling heuristic needs to cope with multiple objectives. To tackle this challenge, we first propose a multipopulation-based multitask multiobjective GP algorithm to preserve the quality of the learned scheduling heuristics for each task. Furthermore, we develop a multitask multiobjective GP algorithm with a task-oriented knowledge-sharing strategy to further improve the effectiveness of learning scheduling heuristics for DFJSS. The results show that the designed multipopulation-based GP algorithms, especially the one with the task-oriented knowledge-sharing strategy, can achieve good performance for all the examined tasks by maintaining the quality and diversity of individuals for corresponding tasks well. The learned Pareto fronts also show that the GP algorithm with task-oriented knowledge-sharing strategy can learn competitive scheduling heuristics for DFJSS on both of the objectives.

Genetic programming (GP) has achieved great success for learning scheduling heuristics in dynamic job-shop scheduling (JSS). In theory, generating a large number of offspring for GP, known as brood recombination, can improve its heuristic generation ability. However, it is time consuming to evaluate extra individuals. Phenotypic characterization-based surrogates with K-nearest neighbors have been successfully used for GP to preselect only promising individuals for real fitness evaluations in dynamic JSS. However, sample individuals used by surrogate are from only the current generation, since the fitness of individuals across generations is not comparable due to the rotation of training instances. The surrogate cannot accurately estimate the fitness of an offspring that is far away from all the limited sample individuals at the current generation. This article proposes an effective instance-rotation-based surrogate to address the above issue. Specifically, the surrogate uses the samples extracted from individuals across multiple generations with different instances. More importantly, we propose a fitness mapping strategy to make the fitness evaluated by different instances comparable. The results show that the GP with brood recombination and the proposed surrogate can significantly improve the quality of scheduling heuristics. The results also reveal that the proposed algorithm has successfully reduced the number of omitted promising offspring due to the higher accuracy of the surrogate. The samples in the new surrogate spread better in the phenotypic space, and the nearest neighbor tends to be closer to the predicted offspring. This makes the estimated fitness more accurate.

Multitask learning has been successfully used in handling multiple related tasks simultaneously. In reality, there are often many tasks to be solved together, and the relatedness between them is unknown in advance. In this article, we focus on the multitask genetic programming (GP) for the dynamic flexible job shop scheduling (DFJSS) problems, and address two challenges. The first is how to measure the relatedness between tasks accurately. The second is how to select task pairs to transfer knowledge during the multitask learning process. To measure the relatedness between DFJSS tasks, we propose a new relatedness metric based on the behavior distributions of the variable-length GP individuals. In addition, for more effective knowledge transfer, we develop an adaptive strategy to choose the most suitable assisted task for the target task based on the relatedness information between tasks. The findings show that in all of the multitask scenarios studied, the proposed algorithm can substantially increase the effectiveness of the learned scheduling heuristics for all the desired tasks. The effectiveness of the proposed algorithm has also been verified by the analysis of task relatedness and structures of the evolved scheduling heuristics, and the discussions of population diversity and knowledge transfer.

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.

Assigning ambulances to emergencies in real-time, ensuring both that patients receive adequate care and that the fleet remains capable of responding to any potential new emergency, is a critical component of any ambulance service. Thus far, most techniques to manage this problem are as convoluted as the problem itself. As such, many real-world medical services resort to using the naive closest-idle rule, whereby the nearest available vehicles are dispatched to serve each new call. This paper explores the feasibility of using a genetic programming hyper heuristic (GPHH) in order to generate intelligible rules of thumb to select which vehicles should attend any given emergency. Such rules, either manually or automatically designed, are evaluated within a novel solution construction procedure which constructs solutions to the ambulance dispatching problem given the parameters of the simulation environment. Experimental results suggest that GPHH is a promising technique to use when approaching the ambulance dispatching problem. Further, a GPHH-evolved rule's interpretability allows for detailed semantic analysis into which features of the environment are valuable to the decision making process, allowing for human dispatching agents to make more informed decisions in practice.

Dynamic flexible job shop scheduling (DF JSS) is a complex and challenging combinatorial optimisation problem. In DF JSS, job operations have to be processed on a set of machines, and thus machine assignment and operation sequencing decisions need to be made simultaneously in dynamic situations. Genetic programming (GP), as a hyper-heuristic approach, has been widely used to learn scheduling heuristics for DF JSS automati-cally. However, the traditional GP parent selection method based on fitness value only may not be sufficiently effective, since not all the subtrees of a GP individual are meaningful and can contribute to the goodness of the individual. This paper proposes a new GP algorithm with a novel fitness function by incorporating the subtree importance into the parent selection method. Specifically, the subtree importance is measured by the correlation coefficient between the behaviour of subtrees and the GP individual. The proposed algorithm is expected to improve the effectiveness of GP by capturing more useful subtrees for producing offspring to the next generation. This paper uses nine DF JSS scenarios to examine the effectiveness of the proposed algorithm. The results show that the proposed algorithm achieves slightly better performance in some of the scenarios while no worse in all other scenarios. Further analyses, including the effect of the designed fitness function and sizes of the learned scheduling heuristics, are also conducted.

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.

Dynamic flexible job shop scheduling is an important combinatorial optimisation problem that covers valuable practical applications such as order picking in warehouses and service allocation in cloud computing. Machine assignment and operation sequencing are two key decisions to be considered simultaneously in dynamic flexible job shop scheduling. Genetic programming has been successfully and widely used to learn scheduling heuristics, including a routing rule for machine assignment and a sequencing rule for operation sequencing simultaneously. There are mainly two types of learning strategies to evolve scheduling heuristics, i.e., learning one rule by fixing the other rule, and learning the routing rule and the sequencing rule simultaneously. However, there is no guidance on which learning strategy to use in specific cases. To fill this gap, this paper provides a comprehensive study of learning strategies on scheduling heuristics of genetic programming in dynamic flexible job shop scheduling by comparing five learning strategies, including two strategies that are extended from the existing studies. The results show that learning two rules simultaneously, either using cooperative coevolution or multi-tree representation, is more effective than only learning one type of rule. Cooperative coevolution is recommended if an algorithm aims to handle a problem by dividing it into small sub-problems, and focuses on the characteristics of routing rule and sequencing rule. Genetic programming with multi-tree representation that treats the routing rule and the sequencing rule as an individual, is preferred to reduce the complexities of algorithms.

Linear genetic programming (LGP) has been successfully applied to various problems such as classification, symbolic regression and hyper-heuristics for automatic heuristic design. In contrast with the traditional tree-based genetic programming (TGP), LGP uses a sequence of instructions to represent an individual (program), and the data is carried by registers. A common issue of LGP is that LGP is susceptible to introns (i.e., instructions with no effect to the program output), which limits the effectiveness of traditional genetic operators. To address these issues, we propose a new graph-based LGP system. Specifically, graph-based LGP uses graph-based crossover and graph-based mutation to produce offspring. The graph-based crossover operator firstly converts each LGP parent to a directed acyclic graph (DAG), and then swaps the sub-graphs between the DAGs. The graph-based mutation selectively modify the connections in DAGs based on the height of sub graphs. To verify the effectiveness of the new graph-based genetic operators, we take the dynamic job shop scheduling as a case study, which has shown to be a challenging problem for LGP. The experimental results show that the LGP with the new graph-based genetic operators can obtain better scheduling heuristics than the LGP with the traditional operators and TGP.

Evolutionary multitask learning has achieved great success due to its ability to handle multiple tasks simultaneously. However, it is rarely used in the hyperheuristic domain, which aims at generating a heuristic for a class of problems rather than solving one specific problem. The existing multitask hyperheuristic studies only focus on heuristic selection, which is not applicable to heuristic generation. To fill the gap, we propose a novel multitask generative hyperheuristic approach based on genetic programming (GP) in this article. Specifically, we introduce the idea in evolutionary multitask learning to GP hyperheuristics with a suitable evolutionary framework and individual selection pressure. In addition, an origin-based offspring reservation strategy is developed to maintain the quality of individuals for each task. To verify the effectiveness of the proposed approach, comprehensive empirical studies have been conducted on the homogeneous and heterogeneous multitask dynamic flexible job shop scheduling. The results show that the proposed algorithm can significantly improve the quality of scheduling heuristics for each task in all the examined scenarios. In addition, the evolved scheduling heuristics verify the mutual help among the tasks in a multitask scenario.

Dynamic flexible job shop scheduling (JSS) has received widespread attention from academia and industry due to its practical application value. It requires complex routing and sequencing decisions under unpredicted dynamic events. Genetic programming (GP), as a hyperheuristic approach, has been successfully applied to evolve scheduling heuristics for JSS due to its flexible representation. However, the simulation-based evaluation is computationally expensive since there are many calculations based on individuals for making decisions in the simulation. To improve training efficiency, this article proposes a novel multifidelity-based surrogate-assisted GP. Specifically, multifidelity-based surrogate models are first designed by simplifying the problem expected to be solved. In addition, this article proposes an effective collaboration mechanism with knowledge transfer for utilizing the advantages of multifidelity-based surrogate models to solve the desired problems. This article examines the proposed algorithm in six different scenarios. The results show that the proposed algorithm can dramatically reduce the computational cost of GP without sacrificing the performance in all scenarios. With the same training time, the proposed algorithm can achieve significantly better performance than its counterparts in most scenarios while no worse in others.

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.

Dynamic flexible job-shop scheduling (DFJSS) is a challenging combinational optimization problem that takes the dynamic environment into account. Genetic programming hyperheuristics (GPHH) have been widely used to evolve scheduling heuristics for job-shop scheduling. A proper selection of the terminal set is a critical factor for the success of GPHH. However, there is a wide range of features that can capture different characteristics of the job-shop state. Moreover, the importance of a feature is unclear from one scenario to another. The irrelevant and redundant features may lead to performance limitations. Feature selection is an important task to select relevant and complementary features. However, little work has considered feature selection in GPHH for DFJSS. In this article, a novel two-stage GPHH framework with feature selection is designed to evolve scheduling heuristics only with the selected features for DFJSS automatically. Meanwhile, individual adaptation strategies are proposed to utilize the information of both the selected features and the investigated individuals during the feature selection process. The results show that the proposed algorithm can successfully achieve more interpretable scheduling heuristics with fewer unique features and smaller sizes. In addition, the proposed algorithm can reach comparable scheduling heuristic quality with much shorter training time.

Dynamic flexible job shop scheduling (JSS) is a challenging combinatorial optimization problem due to its complex environment. In this problem, machine assignment and operation sequencing decisions need to be made simultaneously under the dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully used to evolve scheduling heuristics for dynamic flexible JSS. However, in traditional GP, recombination between parents may disrupt the beneficial building blocks by choosing the crossover points randomly. This article proposes a recombinative mechanism to provide guidance for GP to realize effective and adaptive recombination for parents to produce offspring. Specifically, we define a novel measure for the importance of each subtree of an individual, and the importance information is utilized to decide the crossover points. The proposed recombinative guidance mechanism attempts to improve the quality of offspring by preserving the promising building blocks of one parent and incorporating good building blocks from the other. The proposed algorithm is examined on six scenarios with different configurations. The results show that the proposed algorithm significantly outperforms the state-of-the-art algorithms on most tested scenarios, in terms of both final test performance and convergence speed. In addition, the rules obtained by the proposed algorithm have good interpretability.

Dynamic flexible job shop scheduling (JSS) is an important combinatorial optimization problem with complex routing and sequencing decisions under dynamic environments. Genetic programming (GP), as a hyperheuristic approach, has been successfully applied to evolve scheduling heuristics for JSS. However, its training process is time consuming, and it faces the retraining problem once the characteristics of job shop scenarios vary. It is known that multitask learning is a promising paradigm for solving multiple tasks simultaneously by sharing knowledge among the tasks. To improve the training efficiency and effectiveness, this article proposes a novel surrogate-assisted evolutionary multitask algorithm via GP to share useful knowledge between different scheduling tasks. Specifically, we employ the phenotypic characterization for measuring the behaviors of scheduling rules and building a surrogate for each task accordingly. The built surrogates are used not only to improve the efficiency of solving each single task but also for knowledge transfer in multitask learning with a large number of promising individuals. The results show that the proposed algorithm can significantly improve the quality of scheduling heuristics for all scenarios. In addition, the proposed algorithm manages to solve multiple tasks collaboratively in terms of the evolved scheduling heuristics for different tasks in a multitask scenario.

Dynamic flexible job shop scheduling (DFJSS) considers making machine assignment and operation sequencing decisions simultaneously with dynamic events. Genetic programming hyper-heuristics (GPHH) have been successfully applied to evolving dispatching rules for DFJSS. However, existing studies mainly focus on evolving deterministic dispatching rules, which calculate priority values for the candidate machines or jobs and select the one with the best priority. Inspired by the effectiveness of training stochastic policies in reinforcement learning, and the fact that a dispatching rule in DFJSS is similar to a policy in reinforcement learning, we investigate the effectiveness of evolving stochastic dispatching rules for DFJSS in this paper. Instead of using the "winner-takes-all" mechanism, we define a range of probability distributions based on the priority values of the candidates to be used by the stochastic dispatching rules. These distributions introduce varying degrees of randomness. We empirically compare the effectiveness of GPHH in evolving the stochastic dispatching rules with different probability distributions, as well as evolving the deterministic dispatching rules. The results show that the evolved deterministic rules perform the best. We argue that this is because unlike the traditional reinforcement learning methods, the current GPHH does not store the quality (value function) of any particular state and action during the simulation, and thus cannot fully take advantage of the feedback given by the simulation. In the future, we will investigate better ways to make better use of the information during the simulation in GPHH to further improve its effectiveness.

Dynamic flexible job shop scheduling (DFJSS) is one of the well-known combinational optimisation problems, which aims to handle machine assignment (routing) and operation sequencing (sequencing) simultaneously in dynamic environment. Genetic programming, as a hyper-heuristic method, has been successfully applied to evolve the routing and sequencing rules for DFJSS, and achieved promising results. In the actual production process, it is necessary to get a balance between several objectives instead of simply focusing only one objective. No existing study considered solving multi-objective DFJSS using genetic programming. In order to capture multi-objective nature of job shop scheduling and provide different trade-offs between conflicting objectives, in this paper, two well-known multi-objective optimisation frameworks, i.e. non-dominated sorting genetic algorithm II (NSGA-II) and strength Pareto evolutionary algorithm 2 (SPEA2), are incorporated into the genetic programming hyper-heuristic method to solve the multi-objective DFJSS problem. Experimental results show that the strategy of NSGA-II incorporated into genetic programming hyper-heuristic performs better than SPEA2-based GPHH, as well as the weighted sum approaches, in the perspective of both training performance and generalisation.

Dynamic flexible job shop scheduling (DFJSS) is an important and a challenging combinatorial optimisation problem. Genetic programming hyper-heuristic (GPHH) has been widely used for automatically evolving the routing and sequencing rules for DFJSS. The terminal set is the key to the success of GPHH. There are a wide range of features in DFJSS that reflect different characteristics of the job shop state. However, the importance of a feature can vary from one scenario to another, and some features may be redundant or irrelevant under the considered scenario. Feature selection is a promising strategy to remove the unimportant features and reduce the search space of GPHH. However, no work has considered feature selection in GPHH for DFJSS so far. In addition, it is necessary to do feature selection for the two terminal sets simultaneously. In this paper, we propose a new two-stage GPHH approach with feature selection for evolving routing and sequencing rules for DFJSS. The experimental studies show that the best solutions achieved by the proposed approach are better than that of the baseline method in most scenarios. Furthermore, the rules evolved by the proposed approach involve a smaller number of unique features, which are easier to interpret.