Abstract The extensive use of Internet of Things devices leads to the generation of vast amounts of high-frequency time-series data. Analysing these data provides valuable insights for business decision-making. However, to provide timely decisions, we should be able to analyse time-series streaming data on the fly. While numerous advanced analytical techniques have been developed to rapidly identify behaviour profiles that highlight prominent patterns and enable anomaly detection in time-series data, these methods are mainly tailored to static datasets rather than dynamic data streams. In addition, existing methods for incrementally detecting and visualising patterns and anomalies in multi-variate time-series streaming data still have limitations. This paper proposes a swarm intelligence-based visual analytics approach and algorithm to learn behaviour profiles incrementally, automatically determining the appropriate number of profiles from the data stream. Each profile is a network of data prototypes representing the data distributions. A new visualisation method is developed to visualise behaviour profiles that can reveal cyclic patterns and anomalies without requiring a dimensionality reduction step. Experiments with real-world time-series datasets show that the proposed approach can capture, cluster and visualise key patterns and anomalies, providing actionable insights from the data.

Scheduling is an important function in dynamic and complex production systems. Effective scheduling strategies help production systems utilise resources efficiently and improve delivery performance. Due to the production system's complexity and dynamic changes, designing such scheduling strategies is challenging. Recently, advanced machine learning and optimisation methods such as genetic programming (GP) have shown promise in designing sophisticated scheduling strategies. These methods' success relies on accurate data-driven simulation models for evaluating automatically-generated scheduling strategies. However, building a simulation model that accurately predicts complex production system behaviours requires a lot of historical operational data, which may not always be available, especially for new production systems or those adaptive to the market. To overcome this limitation, this study develops the first online GP method called OGP for dynamic production scheduling problems that allows GP to learn and optimise scheduling decisions on the fly without an exact model for fitness evaluations. The experiments with dynamic flexible job shops show that OGP outperforms existing scheduling strategies in the literature when both scheduling and routing decisions are considered. When used as an automated heuristic design method, OGP can generate competitive rules compared to the state-of-the-art GP methods in terms of test performance and rule sizes.

This paper introduces a novel approach, evolutionary multi-objective optimisation for fairness-aware self-adjusting memory classifiers, designed to enhance fairness in machine learning algorithms applied to data stream classification. With the growing concern over discrimination in algorithmic decision-making, particularly in dynamic data stream environments, there is a need for methods that ensure fair treatment of individuals across sensitive attributes like race or gender. The proposed approach addresses this challenge by integrating the strengths of the self-adjusting memory K-Nearest-Neighbour algorithm with evolutionary multi-objective optimisation. This combination allows the new approach to efficiently manage concept drift in streaming data and leverage the flexibility of evolutionary multi-objective optimisation to maximise accuracy and minimise discrimination simultaneously. We demonstrate the effectiveness of the proposed approach through extensive experiments on various datasets, comparing its performance against several baseline methods in terms of accuracy and fairness metrics. Our results show that the proposed approach maintains competitive accuracy and significantly reduces discrimination, highlighting its potential as a robust solution for fairness-aware data stream classification. Further analyses also confirm the effectiveness of the strategies to trigger evolutionary multi-objective optimisation and adapt classifiers in the proposed approach.

Resource constrained job scheduling is a hard combinatorial optimisation problem that originates in the mining industry. Off-the-shelf solvers cannot solve this problem satisfactorily in reasonable time-frames, while other solution methods such as evolutionary computation methods and matheuristics cannot guarantee optimality and require low-level customisation and specialised heuristics to be effective. This paper addresses this gap by proposing a genetic programming algorithm to discover efficient search strategies of constraint programming for resource-constrained job scheduling. In the proposed algorithm, evolved programs represent variable selectors to be used in the search process of constraint programming, and their fitness is determined by the quality of solutions obtained by constraint programming for training instances. The novelties of this algorithm are (1) a new representation of variable selectors, (2) a new fitness evaluation scheme, and (3) a pre-selection mechanism. Tests with a large set of random and benchmark instances show that the evolved variable selectors can significantly improve the efficiency of constraining programming. Compared to highly customised metaheuristics and hybrid algorithms, evolved variable selectors can help constraint programming identify quality solutions faster and proving optimality is possible if sufficiently large run-times are allowed. The evolved variable selectors are especially helpful when solving instances with large numbers of machines.

Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning-based variable ordering methods with conventional domain-based approaches through tie-breaking.

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.

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.

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.

Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.

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.

Evolving production scheduling heuristics is a challenging task because of the dynamic and complex production environments and the interdependency of multiple scheduling decisions. Different genetic programming (GP) methods have been developed for this task and achieved very encouraging results. However, these methods usually have trouble in discovering powerful and compact heuristics, especially for difficult problems. Moreover, there is no systematic approach for the decision makers to intervene and embed their knowledge and preferences in the evolutionary process. This article develops a novel people-centric evolutionary system for dynamic production scheduling. The two key components of the system are a new mapping technique to incrementally monitor the evolutionary process and a new adaptive surrogate model to improve the efficiency of GP. The experimental results with dynamic flexible job shop scheduling show that the proposed system outperforms the existing algorithms for evolving scheduling heuristics in terms of scheduling performance and heuristic sizes. The new system also allows the decision makers to interact on the fly and guide the evolution toward the desired solutions.

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.

Operational researchers and decision modelers have aspired to optimization technologies with a self-adaptive mechanism to cope with new problem formulations. Self-adaptive mechanisms not only free users from low-level and complex development tasks to enhance optimization efficiency but also allow them to focus on addressing high-level real-world operational requirements. In recent years, there has been a growing interest in applying machine learning and artificial intelligence techniques to improve self-adaptive mechanisms. However, learning to optimize hard combinatorial optimization problems remains a challenging task. This article proposes a new genetic programming approach to evolve efficient variable selectors to enhance the search mechanism in constraint programming. Starting with a set of training instances for a specific combinatorial optimization problem, the proposed approach evaluates variable selectors and evolves them to be more efficient over a number of generations. The novelties of our proposed approach are threefold: 1) a new representation of variable selectors; 2) a new mechanism for fitness evaluations; and 3) a preselection technique. We examine performance of the proposed approach on different job-shop scheduling problems, and the results show that variable selectors can be evolved efficiently. In particular, there are substantial reductions in the computational effort required for the search component of the constraint solver as well as increased chances of finding the optimal solutions. Further analyses also confirm the efficacy of our approach in respect to scalability, generalization, and interpretability of the evolved variable selectors.

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.

Smart cities endeavor to deliver safe and sustainable infrastructure services that enable individuals, organizations, and communities alike to be productive, healthy, informed, and actively involved in rapid urbanization. The widespread installation of closed-circuit television cameras and continuously generated video streams are a strategic data source that can contribute toward safety and sustainability through efficient surveillance of smart city assets and resources. Recent advances in deep learning methods are able to detect and localize salient objects in a video stream. However, a number of practical issues remain unaddressed, such as suboptimality, latency, predictive accuracy, and most importantly the contextualization of all detected salient objects for informed decisions that aligns with ethical surveillance. In this article, we propose a Generative Latent Space (GenLS) approach that overcomes these challenges, specifically in road surveillance. We demonstrate an adaptation of this approach for a prominent use-case in road surveillance, License Plate Detection. GenLS was evaluated for accuracy, robustness, computational cost, and cogency, using a state-of-the-art benchmark dataset on road traffic. Results from these experiments and the corresponding ablation study validate GenLS and confirm its suitability for real-time smart city road surveillance.

Resource constrained job scheduling is a challenging combinatorial optimisation with many real-world applications. A number of exact methods and meta-heuristics have been proposed in the literature to solve this problem, but often encounter scalability issues. This paper investigates an automated heuristic design approach to deal with this problem. The aim of this approach is to generate heuristics that can quickly construct good solutions, which can be applied directly or used to initialise other meta-heuristics. A new adaptive genetic programming algorithm is proposed to coevolve a large set of reusable heuristics to solve the resource constrained job scheduling problem. There are three different aspects to the novelty behind our proposed algorithm: (a) a new phenotypic representation of heuristics, (b) an efficient mapping technique to monitor the evolutionary process, and (c) an adaptive fitness function to guide the search towards a diverse and competitive population. The experimental results show that evolved heuristics show promise and are able to outperform some existing meta-heuristics for large-scale instances. Analyses also show that the algorithm can be further improved if appropriate parameters are selected.

Growing big data has posed a great challenge for machine learning algorithms. To cope with big data, the algorithm has to be both efficient and accurate. Although evolutionary computation has been successfully applied to many complex machine learning tasks, its ability to handle big data is limited. In this paper, we proposed a dynamic self-organising swarm algorithm to learn an effective set of prototypes for big high-dimensional datasets in an unsupervised manner. The novelties of this new algorithm are the energy-based fitness function, the adaptive topological neighbourhood, the growing/shrinking capability, and the efficient learning scheme. Experiments with well-known datasets show that the proposed algorithm can maintain a very compact set of prototypes and achieve competitive predictive performance as compared to other algorithms in the literature. The analyses also show that prototypes generated by the proposed algorithms have a stronger separatability compared to those from other prototype generation algorithms.

Designing effective dispatching rules for production systems is a difficult and time-consuming task if it is done manually. In the last decade, the growth of computing power, advanced machine learning, and optimisation techniques has made the automated design of dispatching rules possible and automatically discovered rules are competitive or outperform existing rules developed by researchers. Genetic programming is one of the most popular approaches to discovering dispatching rules in the literature, especially for complex production systems. However, the large heuristic search space may restrict genetic programming from finding near optimal dispatching rules. This article develops a new hybrid genetic programming algorithm for dynamic job shop scheduling based on a new representation, a new local search heuristic, and efficient fitness evaluators. Experiments show that the new method is effective regarding the quality of evolved rules. Moreover, evolved rules are also significantly smaller and contain more relevant attributes.

The technological landscape of intelligent transport systems (ITS) has been radically transformed by the emergence of the big data streams generated by the Internet of Things (IoT), smart sensors, surveillance feeds, social media, as well as growing infrastructure needs. It is timely and pertinent that ITS harness the potential of an artificial intelligence (AI) to develop the big data-driven smart traffic management solutions for effective decision-making. The existing AI techniques that function in isolation exhibit clear limitations in developing a comprehensive platform due to the dynamicity of big data streams, high-frequency unlabeled data generation from the heterogeneous data sources, and volatility of traffic conditions. In this paper, we propose an expansive smart traffic management platform (STMP) based on the unsupervised online incremental machine learning, deep learning, and deep reinforcement learning to address these limitations. The STMP integrates the heterogeneous big data streams, such as the IoT, smart sensors, and social media, to detect concept drifts, distinguish between the recurrent and non-recurrent traffic events, and impact propagation, traffic flow forecasting, commuter sentiment analysis, and optimized traffic control decisions. The platform is successfully demonstrated on 190 million records of smart sensor network traffic data generated by 545,851 commuters and corresponding social media data on the arterial road network of Victoria, Australia.

This study considers a resource constrained job scheduling problem. Jobs need to be scheduled on different machines satisfying a due time. If delayed, the jobs incur a penalty which is measured as a weighted tardiness. Furthermore, the jobs use up some proportion of an available resource and hence there are limits on multiple jobs executing at the same time. Due to complex constraints and a large number of decision variables, the existing solution methods, based on meta-heuristics and mathematical programming, are very time-consuming and mainly suitable for small-scale problem instances. We investigate a genetic programming approach to automatically design reusable scheduling heuristics for this problem. A new representation and evaluation mechanisms are developed to provide the evolved heuristics with the ability to effectively construct and refine schedules. The experiments show that the proposed approach is more efficient than other genetic programming algorithms previously developed for evolving scheduling heuristics. In addition, we find that the obtained heuristics can be effectively reused to solve unseen and large-scale instances and often find higher quality solutions compared to algorithms already known in the literature in significantly reduced time-frames.

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.

Automated heuristic design for job shop scheduling has been an interesting and challenging research topic in the last decade. Various machine learning and optimising techniques, usually referred to as hyper-heuristics, have been applied to facilitate the design task. Two main approaches are either to utilise a general structure for dispatching rules and optimise its parameters or to simultaneously search for suitable structures and their parameters. Each approach has its own advantages and disadvantages. In this paper, we focus on the first approach and develop new representations that are flexible enough to represent diverse rules and powerful enough to cope with complex shop conditions. Particle swarm optimisation is used in the proposed hyper-heuristic to find optimal rules based on the representations. The results suggest that the new representations are effective for different shop conditions and obtained rules are very competitive as compared to those evolved by genetic programming. Analyses also show that the proposed hyper-heuristic is significantly faster than genetic programming based hyper-heuristic.

Most production scheduling studies involve comparing the performances of different scheduling methods. Since each scheduling method focuses on a special way to optimise scheduling decisions and is restricted to certain assumptions, fair comparisons of these methods are not straightforward. In this paper, we aim at comparing major scheduling methods in the literature using an experimental environment which provides flexibility such that all methods can interact easily with the environment to obtain required information and execute scheduling decisions. The comparisons help us gain more insights about the advantages and disadvantages of each method in terms of efficiency and effectiveness.

Automated design of dispatching rules for production systems has been an interesting research topic over the last several years. Machine learning, especially genetic programming (GP), has been a powerful approach to dealing with this design problem. However, intensive computational requirements, accuracy and interpretability are still its limitations. This paper aims at developing a new surrogate assisted GP to help improving the quality of the evolved rules without significant computational costs. The experiments have verified the effectiveness and efficiency of the proposed algorithms as compared to those in the literature. Furthermore, new simplification and visualisation approaches have also been developed to improve the interpretability of the evolved rules. These approaches have shown great potentials and proved to be a critical part of the automated design system.

Evolutionary scheduling and combinatorial optimisation is an active research area and attracts the attentions of many researchers from computer science and operations research. Many advances have been made in this field and its scope in terms of techniques and applications has been continuously extended. In this position paper, we provide an overall picture of some key challenges in the field, discuss potential future research directions, and give our position in the field. We focus on three major issues that are encountered in practice, namely dynamic changes, multiple interdependent decisions, and multiple objectives. Our view is that the researchers should step out of our comfort zone to deal with messy and complicated issues in real-world applications.

Effectively utilising available resources is an important task of a reservation system to help service providers improve their profits and customer satisfaction. Reservation with slack is an interesting and challenging combinatorial optimization problem with many potential applications in practice. However, this problem has not received enough attentions in the literature. This study proposes a new mixed integer linear programming model for reservation with slack and develops a new hybrid genetic algorithm to deal with this problem. The results show that the proposed method is very competitive as compared to the exact optimisation method and the composite dispatching rule in terms of effectiveness and efficiency. While exact method can only solve very small instances with no more than 20 activities, the proposed algorithm can handle very large scale instances with hundreds of activities in a short running time. Analyses are also provided in this paper to examine the influence of decoding methods, local search heuristics and diversification on the performance of the proposed algorithm.

Genetic Programming (GP) has been successfully used to automatically design dispatching rules in job shop scheduling. The goal of GP is to evolve a priority function that will be used to order the waiting jobs at each decision point, and decide the next job to be processed. To this end, the proper terminals (i.e. job shop features) have to be decided. When evolving the priority function, various job shop features can be included in the terminal set. However, not all the features are helpful, and some features are irrelevant to the rule. Including irrelevant features into the terminal set enlarges the search space, and makes it harder to achieve promising areas. Thus, it is important to identify the important features and remove the irrelevant ones to improve the GP-evolved rules. This paper proposes a domain-knowledge-free feature ranking and selection approach. As a result, the terminal set is significantly reduced and only the most important features are selected. The experimental results show that using only the selected features can lead to significantly better GP-evolved rules on both training and unseen test instances.

Feature selection is an essential step in classification tasks with a large number of features, such as in gene expression data. Recent research has shown that particle swarm optimisation (PSO) is a promising approach to feature selection. However, it also has potential limitation to get stuck into local optima, especially for gene selection problems with a huge search space. Therefore, we developed a PSO algorithm (PSO-LSRG) with a fast “local search” combined with a gbest resetting mechanism as a way to improve the performance of PSO for feature selection. Furthermore, since many existing PSO-based feature selection approaches on the gene expression data have feature selection bias, i.e. no unseen test data is used, 2 sets of experiments on 10 gene expression datasets were designed: with and without feature selection bias. As compared to standard PSO, PSO with gbest resetting only, and PSO with local search only, PSO-LSRG obtained a substantial dimensionality reduction and a significant improvement on the classification performance in both sets of experiments. PSO-LSRG outperforms the other three algorithms when feature selection bias exists. When there is no feature selection bias, PSO-LSRG selects the smallest number of features in all cases, but the classification performance is slightly worse in a few cases, which may be caused by the overfitting problem. This shows that feature selection bias should be avoided when designing a feature selection algorithm to ensure its generalisation ability on unseen data.

Hyper-heuristics have recently emerged as a powerful approach to automate the design of heuristics for a number of different problems. Production scheduling is a particularly popular application area for which a number of different hyper-heuristics have been developed and are shown to be effective, efficient, easy to implement, and reusable in different shop conditions. In particular, they seem to be a promising way to tackle highly dynamic and stochastic scheduling problems, an aspect that is specifically emphasized in this survey. Despite their success and the substantial number of papers in this area, there is currently no systematic discussion of the design choices and critical issues involved in the process of developing such approaches. This paper strives to fill this gap by summarizing the state-of-the-art approaches, suggesting a taxonomy, and providing the interested researchers and practitioners with guidelines for the design of hyper-heuristics in production scheduling. This paper also identifies challenges and open questions and highlights various directions for future work.

Genetic programming based hyper-heuristics have been an suitable approach to designing powerful dispatching rules for dynamic job shop scheduling. However, most current methods only focus on a single objective while practical problems almost always involve multiple conflicting objectives. Some efforts have been made to design non-dominated dispatching rules but using genetic programming to deal with multiple objectives is still very challenging because of the large search space and the stochastic characteristics of job shops. This paper investigates different strategies to utilise computational budgets when evolving dispatching rules with genetic programming. The results suggest that using local search heuristics can enhance the quality of evolved dispatching rules. Moreover, the results show that there are some differences in evolving rules for single objectives and for multiple objectives and that it is difficult to efficiently estimate the Pareto dominance of rules.

Order acceptance and scheduling is an interesting and chal- lenging scheduling problem in which two decisions need to be handled simultaneously. While the exact methods are not efficient and sometimes impractical, existing meta-heuristics proposed in the literature still have troubles dealing with large problem instances. In this paper, a dispatching rule based genetic algorithm is proposed to combine the advan- tages of existing dispatching rules/heuristics, genetic algo- rithm and local search. The results indicates that the pro- posed methods are effective and efficient when compared to a number of existing heuristics with a wide range of problem instances.

Dispatching rules have been commonly used in practice for making sequencing and scheduling decisions. Due to specific characteristics of each manufacturing system, there is no universal dispatching rule that can dominate in all situations. Therefore, it is important to design specialized dispatching rules to enhance the scheduling performance for each manufacturing environment. Evolutionary computation approaches such as tree-based genetic programming (TGP) and gene expression programming (GEP) have been proposed to facilitate the design task through automatic design of dispatching rules. However, these methods are still limited by their high computational cost and low exploitation ability. To overcome this problem, we develop a new approach to automatic programming via iterated local search (APRILS) for dynamic job shop scheduling. The key idea of APRILS is to perform multiple local searches started with programs modified from the best obtained programs so far. The experiments show that APRILS outperforms TGP and GEP in most simulation scenarios in terms of effectiveness and efficiency. The analysis also shows that programs generated by APRILS are more compact than those obtained by genetic programming. An investigation of the behavior of APRILS suggests that the good performance of APRILS comes from the balance between exploration and exploitation in its search mechanism.

Allocating jobs to heterogeneous machines in grid systems is an important task in computational grid to effectively utilise computational resources. Particle swarm optimisation (PSO) has been recently applied to grid computation scheduling (GCS) problems and shown very promising results as compared to other meta-heuristics in the literature. However, PSO with the traditional position updating mechanism still has problem coping with the discrete nature of GCS. This paper proposed a new updating mechanism for discrete PSO that directly utilise discrete solutions from personal and global best particles. A new local search heuristic has also been proposed to refine solutions found by PSO. The results show that the hybrid PSO is more effective than other existing PSO methods in the literature when tested on two benchmark datasets. The hybrid method is also very efficient, which makes it suitable to deal with large-scale problem instances.

Order acceptance and scheduling (OAS) is a hard optimisation problem in which both acceptance decisions and scheduling decisions must be considered simultaneously. Designing effective solution methods or heuristics for OAS is not a trivial task, especially to deal with different problem configurations and sizes. This paper proposes a new heuristic framework called forward construction heuristic (FCH) for OAS and develops a new sequential genetic programming (SGPOAS) method for automatic design of FCHs. The key idea of the new GP method is to learn priority rules directly from optimal scheduling decisions at different decision moments and evolve a set of rules for FCHs instead of a single rule as shown in previous studies. The results show that evolved FCHs are significantly better than evolved single priority rules. The evolved FCHs are also competitive with the existing meta-heuristics in the literature and very effective for large problem instances.

Due-date assignment plays an important role in scheduling systems and strongly influences the delivery performance of job shops. Because of the stochastic and dynamic nature of job shops, the development of general due-date assignment models (DDAMs) is complicated. In this study, two genetic programming (GP) methods are proposed to evolve DDAMs for job shop environments. The experimental results show that the evolved DDAMs can make more accurate estimates than other existing dynamic DDAMs with promising reusability. In addition, the evolved operation-based DDAMs show better performance than the evolved DDAMs employing aggregate information of jobs and machines.

A scheduling policy strongly influences the performance of a manufacturing system. However, the design of an effective scheduling policy is complicated and time consuming due to the complexity of each scheduling decision, as well as the interactions among these decisions. This paper develops four new multi-objective genetic programming-based hyperheuristic (MO-GPHH) methods for automatic design of scheduling policies, including dispatching rules and due-date assignment rules in job shop environments. In addition to using three existing search strategies, nondominated sorting genetic algorithm II, strength Pareto evolutionary algorithm 2, and harmonic distance-based multi-objective evolutionary algorithm, to develop new MO-GPHH methods, a new approach called diversified multi-objective cooperative evolution (DMOCC) is also proposed. The novelty of these MO-GPHH methods is that they are able to handle multiple scheduling decisions simultaneously. The experimental results show that the evolved Pareto fronts represent effective scheduling policies that can dominate scheduling policies from combinations of existing dispatching rules with dynamic/regression-based due-date assignment rules. The evolved scheduling policies also show dominating performance on unseen simulation scenarios with different shop settings. In addition, the uniformity of the scheduling policies obtained from the proposed method of DMOCC is better than those evolved by other evolutionary approaches.

This paper focuses on order acceptance and scheduling (OAS) problem, where both acceptance and sequencing decisions have to be handled simultaneously. Because of its complexity, designing effective heuristics or meta-heuristics for OAS is challenging. This paper will investigate how genetic programming (GP) can be used to deal with OAS. The goal of this paper is to develop new GP frameworks to evolve high-performance scheduling rules/heuristics for OAS. The new frameworks are developed based on two key aspects: (1) separating acceptance and sequencing decisions, and (2) enhancing the quality of scheduling rules by embedding heuristic search mechanisms. The experimental results show that separating decisions is not trivial and can easily lead to overfitting issues. Meanwhile, embedding heuristic ideas into the scheduling rules can help search for better solutions for OAS.

Designing effective dispatching rules is an important factor for many manufacturing systems. However, this time-consuming process has been performed manually for a very long time. Recently, some machine learning approaches have been proposed to support this task. In this paper, we investigate the use of genetic programming for automatically discovering new dispatching rules for the single objective job shop scheduling problem (JSP). Different representations of the dispatching rules in the literature are newly proposed in this paper and are compared and analysed. Experimental results show that the representation that integrates system and machine attributes can improve the quality of the evolved rules. Analysis of the evolved rules also provides useful knowledge about how these rules can effectively solve JSP.

A scheduling policy (SP) strongly influences the performance of a manufacturing system. However, the design of an effective SP is complicated and time-consuming due to the complexity of each scheduling decision as well as the interactions between these decisions. This paper proposes novel multi-objective genetic programming based hyper-heuristic methods for automatic design of SPs including dispatching rules (DRs) and due-date assignment rules (DDARs) in job shop environments. The experimental results show that the evolved Pareto front contains effective SPs that can dominate various SPs from combinations of existing DRs with dynamic and regression-based DDARs. The evolved SPs also show promising performance on unseen simulation scenarios with different shop settings. On the other hand, the proposed Diversified Multi-Objective Cooperative Coevolution (DMOCC) method can effectively evolve Pareto fronts of SPs compared to NSGA-II and SPEA2 while the uniformity of SPs obtained by DMOCC is better than those evolved by NSGA-II and SPEA2.

Genetic programming based hyper-heuristics (GPHH) have become popular over the last few years. Most of these proposed GPHH methods have focused on heuristic generation. This study investigates a new application of genetic programming (GP) in the field of hyper-heuristics and proposes a method called GPAM, which employs GP to evolve adaptive mechanisms (AM) to solve hard optimisation problems. The advantage of this method over other heuristic selection methods is the ability of evolved adaptive mechanisms to contain complicated combinations of heuristics and utilise problem solving states for heuristic selection. The method is tested on three problem domains and the results show that GPAM is very competitive when compared with existing hyper-heuristics. An analysis is also provided to gain more understanding of the proposed method.