Evolutionary multiobjective optimization (EMO) has been a subject of intensive study in the past two decades, owing to its research challenges and practical values. With the progress and development of multiobjective evolutionary algorithms (MOEAs), recent research efforts have shifted to addressing large-scale EMO, which refers to applying evolutionary algorithms to solve multiobjective optimization problems with 100 or more decision variables. In this study, we delve into the design of eight large-scale MOEAs and evaluate their performance under different problem scales and computational resource. Based on the experimental results, we identify suitable algorithms in different scenarios. We also present observations and findings on the relationships between algorithm design concepts and performance.

This paper addresses the economic emission dispatch (EED) problem where the goal is to allocate the power output of power generation units to satisfy power demand and minimize the cost and emissions simultaneously. We propose a multiobjective differential evolution algorithm and a reinforcement learning technique to adaptively control the parameters of differential evolution. Moreover, the proposed approach utilizes mating restriction and preferences in mating selection to improve search effectiveness and a dynamically controlled mutation to increase the exploration ability. The proposed ideas and algorithm were examined using four EED test cases. Experimental results showed positive effects of our proposed methods and the competitive performance of our algorithm.

In this paper, we extend a previous algorithm mL-SHADE by running the evolutionary process through multiple populations and adding dynamic control of mutation intensity and hyper-parameters. The whole population is partitioned into subpopulations by a random clustering method. Mutation intensity and hyper-parameters are adjusted based on the consumption of fitness function evaluations. Performance of the proposed algorithm is verified by ten benchmark functions in the CEC2020 Competition on Single Objective Bound Constrained optimization. The results show the competitiveness of the proposed algorithm.

Crossover is one of the most important parts of an evolutionary algorithm (EA) for solving optimization problems. Many crossover operators have been proposed for solving the capacitated vehicle routing problem (CVRP), a classical NP-hard problem in the field of operations research. This paper aims to improve the search ability of the cycle crossover (CX). The longest cycle selection and the nearest neighbor heuristic are utilized to improve the performance. Experimental results show that the proposed heuristic longest cycle crossover (HLCX) outperforms the original CX and four other operators. Additionally, we apply a search reduction strategy in the local refinement procedure to reduce the computation time at a little cost of solution quality.

In this paper we address single objective real parameter optimization by using differential evolution (DE). L-SHADE is a well-known DE with success history-based adaptation and linear population size reduction. We propose a modified L-SHADE (mL-SHADE), in which three modifications are made: (1) removal of the terminal value, (2) addition of polynomial mutation, and (3) proposal of a memory perturbation mechanism. Performance of the proposed mL-SHADE is verified by using ten benchmark functions in the CEC2019 100-Digit Challenge. The results show that mL-SHADE achieves a higher score than seven state-of-the-art adaptive evolutionary algorithms.

Recently, the green vehicle routing problem (GVRP) starts to attract the attention of researchers due to the awareness of the environmental impact of transportation. The GRVP is an extension of the classical VRP by taking minimization of travel distance as well as carbon emissions as the objectives. In this paper, we solved the GVRP by a multiobjective evolutionary algorithm to find the set of Pareto optimal solutions. We found that the tradeoff between travel distance and carbon emissions is small with a load-distance emission model and a parameter setting in the literature. The tradeoff becomes significant only when the emissions of an empty vehicle and of a full-load vehicle differ a lot. Whether the GVRP should be treated as a multiobjective optimization problem (MOP) or not needs more investigation in the future.

Differential evolution (DE) is a variant of the evolutionary algorithm and has good performance in solving continuous optimization problems. Two important parameters, F and CR, control the behaviors of the mutation and crossover operators in DE. Setting their values is critical, but the tuning process could be difficult and time-consuming. In the last decade, many adaptive DE have been proposed with various mechanisms to adjust the parameter values during the evolutionary process. Although these studies conducted numerical experiments and showed promising performance of the proposed algorithms, very few studies investigated and compared how the parameter values are adjusted by these algorithms. In this study, we compared six different types of adaptive DEs and observed their behaviors visually. Several interesting observations are made.

Many-objective optimization deals with problems with more than three objectives. The rapid growth of non-dominated solutions with the increase of the number of objectives weakens the search ability of Pareto-dominance-based multiobjective evolutionary algorithms. MO-NSGA-II strengthens its dominance-based predecessor, NSGA-II, by guiding the search process with reference points. In this paper, we further improve MO-NSGA-II by enhancing its mating selection mechanism with a hierarchical selection and a neighborhood concept based on the reference points. Experimental results confirm that the proposed ideas lead to better solution quality.

Due to the proliferation of smart mobile devices and the developments in wireless communication, mobile ad hoc networks (MANETs) are gaining more and more attention in recent years. Routing in MANETs is a challenge, especially when the network contains a large number of nodes. The clustering technique is a popular method to organize the nodes in MANETs. It divides the network into several clusters and assigns a cluster head to each cluster for intra- and inter-cluster communication. Clustering is NP-hard and needs to consider multiple objectives. In this paper we propose a Pareto-based ant colony optimization (ACO) algorithm to deal with this multiobjective optimization problem. A new encoding scheme is proposed to reduce the size of search space, and a new decoding scheme is proposed to generate high-quality solutions effectively. Experimental results show that our approach is better than several benchmark approaches.

In this paper, we propose a novel approach based on particle swarm optimization (PSO) for solving the minimum energy broadcast (MEB) problem, which has been proven to be NP-complete. Wireless sensor networks (WSNs) have attracted large intention in recent years due to its powerful ability. One crucial issue in WSN is energy saving because of the limited battery resource. The MEB problem is one of the important scenarios in WSN, where a node needs to broadcast packets to all other nodes in the network. The objective is to minimize power consumption of all nodes in the network. Here we take advantage of fast and guided convergence characteristics of PSO to solve the MEB problem. For applying PSO to the MEB problem, we use the power degree to define the particle position. We go a step further to analyze one well-known local search mechanism: r-shrink and propose an improved version. The experimental results show that the proposed approach is able to compete and even outperform state-of-the-art works.

Hyper-heuristics solve problems by manipulating low-level domain-specific heuristics. The aim is to raise the level of generality of the algorithm to solve problems in different domains. In this paper we propose a hyper-heuristic based on Variable Neighborhood Search (VNS), which consists of two main steps: shaking and local search. Shaking disturbs solutions, and then local search seeks for the local optima. In our algorithm, we propose a mechanism to adjust the computational budget of local search periodically based on the search status. We also use a dynamically-sized population to store good solutions during the search process. Performance of the proposed algorithm is compared with four benchmark algorithms by four kinds of problems, Max-SAT, bin packing, flow shop scheduling, and personnel scheduling. Our algorithm finds the best solutions for around 90% of the tested instances.

This paper addresses the vehicle routing problem with time windows (VRPTW). The task is to assign customers to multiple vehicles and determine the visiting sequences of customers for the vehicles without violating the vehicle capacity constraint and customer service time window constraints. Two common objectives of VRPTW are to minimize the number of vehicles and the total traveling distance. Most of previous studies assumed that the number of vehicles is more important than the total distance. Hence, they solved the VRPTW by minimizing the number of vehicles first and then minimizing the total distance under the minimal number of vehicles. Recently, researchers started to solve the VRPTW without this assumption and tried to minimize both objectives simultaneously through searching for the Pareto optimal set of solutions. Following this perspective, we use a multiobjective evolutionary algorithm to solve the VRPTW. We propose enhanced crossover and mutation operators by incorporating the domain knowledge. Performance of the proposed algorithm is verified on a widely used benchmark problem set. Comparing with seven existing algorithms, our algorithm shows competitive performance and contributes many new best known Pareto optimal solutions.

In this paper we propose a multiobjective evolutionary algorithm based on MOEA/D for solving multiobjective optimization problems. MOEA/D decomposes a multiobjective optimization problem into many single-objective subproblems. The objective of each subproblem is a weighted aggregation of the original objectives. Using evenly distributed weight vectors on subproblems, solutions to subproblems form a set of well-spread approximated Pareto optimal solutions to the original problem. In MOEA/D, each individual in the population represents the current best solution to one subproblem. Mating selection is carried out in a uniform and static manner. Each individual/subproblem is selected/solved once at each generation, and the mating pool of each individual is determined and fixed based on the distance between weight vectors on the objective space. We propose an adaptive mating selection mechanism for MOEA/D. It classifies subproblems into solved ones and unsolved ones and selects only individuals of unsolved subproblems. Besides, it dynamically adjusts the mating pools of individuals according to their distance on the decision space. The proposed algorithm, MOEA/D-AMS, is compared with two versions of MOEA/D using nine continuous functions. The experimental results confirm the benefits of the adaptive mating selection mechanism.

In real-world applications, the optimization problems usually include some conflicting objectives and subject to many constraints. Much research has been done in the fields of multiobjective optimization and constrained optimization, but little focused on both topics simultaneously. In this study we present a hybrid constraint handling mechanism, which combines the ε-comparison method and penalty method. Unlike original s-comparison method, we set an individual ε-value to each constraint and control it by the amount of violation. The penalty method deals with the region where constraint violation exceeds the ε-value and guides the search toward the ε-feasible region. The proposed algorithm is based on a well-known multiobjective evolutionary algorithm, NSGA-II, and introduces the operators in differential evolution (DE). A modified DE strategy, DE/better-to-best_feasible/l, is applied. The better individual is selected by tournament selection, and the best individual is selected from an archive. Performance of the proposed algorithm is compared with NSGA-II and an improved version with a self-adaptive fitness function. The proposed algorithm shows competitive results on sixteen public constrained multiobjective optimization problem instances.

Classification rule mining, addressed a lot in machine learning and statistics communities, is an important task to extract knowledge from data. Most existing approaches do not particularly deal with data instances matched by more than one rule, which results in restricted performance. We present a two-phase multiobjective evolutionary algorithm which first aims at searching decent rules and then takes the rule interaction into account to produce the final rule sets. The algorithm incorporates the concept of Pareto dominance to deal with trade-off relations in both phases. Through computational experiments, the proposed algorithm shows competitive to the state-of-the-art. We also study the effect of a niching mechanism.

This paper addresses a multiobjective scheduling problem in the permutation flow shop. The objectives are to minimize makespan and total flow time. The proposed approach is based on the framework of memetic algorithm, which is known as a hybrid of genetic algorithm and local search. The local search procedure is an iterative process repeating neighbor generation, neighbor evaluation, and neighbor selection. We take a problem-specific heuristic for neighbor generation and propose several strategies for neighbor evaluation and neighbor selection. Archive injection (adding non-dominated solutions to the population) is another issue under investigation. We examine the effects of the proposed strategies through experiments using forty widely used problem instances with different scales. We also evaluate the proposed approach by comparing it with other twenty-six ones in terms of three performance metrics. Our approach outperforms all benchmarks and updates a large portion of the sets of best known non-dominated solutions for large-scale instances.

Dispatching rules are widely used for scheduling of wafer fabrication facilities, and simulation is a popular tool for evaluation of rules. A main weakness of simulation is the long computation time. In this paper, we aim at simplifying the models of fabrication facilities to reduce simulation time and meanwhile keep the ability of evaluating rules correctly. We propose a metric to assess how well a simplified model evaluates rules and formulate the model simplification problem as a multiobjective optimization problem. We also develop an evolutionary algorithm to solve the formulated problem. Experimental results show that simplified models generated by the proposed algorithm can save half of simulation time and select high-performance rules.

The multiobjective flowshop problem with makespan and total flow time as objectives is addressed. A genetic local search algorithm is proposed with the ability to allocate the computational resources through the dynamic population size and local search intensity. The proposed method is compared with existing algorithms for flowshop scheduling with a public benchmark problem set. The experimental results show that the proposed method is capable of discovering solutions with better quality and diversity. The proposed method yields the best known nondominated solutions for the commonly studied permutation flowshop benchmarks, and the set of best known solutions is useful for the evaluation of performance of future studies.

The identical parallel batch machine scheduling problem is addressed in this paper. Incompatible job families and dynamic job arrivals are considered, and the objective is to minimize total weighted tardiness. A memetic algorithm is proposed to assign the batches to machines and to determine their processing sequences. The proposed approach is shown to outperform an existing approach in terms of solution quality and computational efficiency through comprehensive experiments.

In this paper, we solve two problems in a 300-mm wafer fabrication facility (fab). Firstly, for the lot scheduling problem, we propose a multi-objective genetic programming based rule generator (MOGPRG) to evolve useful dispatching rules, which can provide near-optimal lot schedules concerning multiple objectives. Secondly, the overhead hoist transports (OHT) routing problem is considered. As the modern automated material handling system (AMHS) is capable of doing tool-to-tool direct delivery, the congestion of OHTs may happen more often than the past. To deal with the traffic congestion in AMHS, a dynamic routing method is proposed to find the near-shortest and less-congested path for the OHT to travel along. It can reduce the traffic congestion and achieve fast lot delivery by adapting to the dynamic traffic environment. The proposed MOGPRG is integrated with the dynamic routing method to improve two fab performance metrics: mean cycle time and tardy rate. Experimental results show the effectiveness of the proposed MOGPRG and dynamic routing method.

A job shop scheduling problem with total tardiness and the maximum tardiness as objectives is addressed. We solve it by a rule-coded genetic algorithm. Characteristics of three existing fitness assignment mechanisms are identified and then combined through the proposed cyclic fitness assignment mechanism. Experiments are conducted on a public benchmark problem set, and the results show that the proposed algorithm outperforms the existing ones.

This paper addresses the job shop scheduling problem with the due date-based objectives including the tardy rate, mean tardiness, and the maximum tardiness. The focused approach is dispatching rules. Sixteen dispatching rules are selected from the literature and used as the benchmarks. Their features and design concepts are also discussed. Then a dispatching rule is proposed with the goal as achieving good and balanced performance when more than one objective is concerned at the same time. The experimental results verified its superiority, especially on the tardy rate and mean tardiness

This paper addresses the lot scheduling problem in the semiconductor wafer fabrication facilities. We provide a simulation study to examine the performance of sixteen existing dispatching rules on the tardy rate, mean tardiness, and the maximum tardiness. A public and representative test bed, the MIMAC (measurement and improvement of manufacturing capacities) test bed is used. The best rules with respect to each objective are identified through the experiments, and some findings are provided to be guidelines for designing new dispatching rules.

In this paper, we propose a modeling tool named Queueing Colored Petri nets (QCPN) for performance evaluation and scheduling for wafer fabrication. The main idea of this tool is to combine colored timed Petri nets with the queueing systems, and it aims to make simulation over the model more efficient. Due to the wide acceptance of priority rules in the wafer manufacturing industry, we also proposed a mechanism to realize priority rules in the QCPN models. Since it is known that no single rule can dominate in any circumstance, we proposed a genetic algorithm (GA) to search for the optimal combination of a number of priority rules based on the status and performance measures of the fab. Our approach can be considered as taking the advantage of the lot execution sequence generated by priority rules to guide the search. This approach can reduce the solution space and help us find the good solution more quickly. In addition, the QCPN-based GA scheduler can greatly reduce the computation time so that this GA scheduler can meet the need for a rapidly changing environment. Note to Practitioners-Performance evaluation and scheduling are two functions required by fab managers and engineers. This paper proposed a tool which consists of a simulator and a scheduler. By connecting to the Manufacturing Execution System (MES) and providing the scheduling rules, we can see how the fab runs virtually with the simulator. General information such as throughput and average cycle time and specific information like lot activity history can be obtained. This can be used for decision making, delivery prediction, bottleneck seeking, and testing of newly developed heurisitcs. The implementation cost is only on data communication between the MES and the simulator and the incorporation of rule modules. The scheduler, which takes the simulator as the performance evaluation module, can generate the suitable scheduling rule based on the current fab status, preference of performance criteria, and rule candidates. There is almost no extra cost after the simulator is connected to the MES. The scheduler can be easily made faster by common parallelization techniques.

To solve job shop scheduling problems, the priority rule is one of the most popular approach. It has the appeal because of simplicity, efficiency and effectiveness. However, the paradigm conventionally used to apply priority rules has a certain flaw. In this paper, we first point out this flaw and then propose a paradigm to remove it. A rule is also developed to exploit the potential of the new paradigm. The performance of the proposed approach is verified by several simulation experiments. The experimental results are quite satisfactory.

This paper addresses the FMS scheduling problem. The objective concerned here is maximizing the meet-due-date rate. The authors propose two rules for job sequencing and job dispatching, two common subtasks in solving this problem. These two rules are designed based on the critical ratio values of jobs. We also propose a mechanism to obtain better performance than the stand-alone scheduling process via genetic algorithms. With the nature of design of the proposed job sequencing rule, the genetic algorithm is designed not only to improve the schedule quality but also to save computation time. All the proposed rules and idea are carefully examined through several different scenarios.

In this paper, we use a graphical and mathematical modeling tool colored-timed Petri nets (CTPN) to model the testing flow in the wafer probe center. With this CTPN model, we can simulate the production processes, and keep track of the equipment status and the lot conditions efficiently and precisely. In the dispatching phase, we present the lot-based and the equipment-based selection schemes. Each of these two schemes has its own advantages, but also some drawbacks. Therefore, we propose a new approach pair generation mechanism and adaptive lot/equipment matching strategy, which can promise a dispatching strategy that can be more optimal in the sense that both lot-based and equipment-based viewpoints are taken into account simultaneously. In this paper, we further adopt an efficient algorithm auction algorithm to help us to find out the optimal solution to the internally generated lot/equipment matching problem. Besides, some adaptive factors are also applied. Lastly in the scheduling phase, we apply the genetic algorithm (GA) based approach to obtain a near-optimal solution to our scheduling problem. From our experiment results, the developed CTPN based genetic algorithm yields a more efficient solution than several other schedulers.

In this paper, we propose architecture to simulate wafer probe. We use a modeling tool named CTPN (colored-timed Petri nets) to model all testing flow. With CTPN model, we can predict the delivery date of any specific product under some scheduling policies efficiently and precisely. In the scheduling phase, we combine two popular methods to contract high-quality schedules. One is to select machines for lots and the other is to select lots for machines. In each method, we use the GA-based approach to search for the optimal combination of a number of heuristic rules. This CTPN-based GA scheduler and helps us to find the good solution so as to meet the requirements in the complicated environment.

To provide good transportation services for passengers in modern buildings, a good elevator group control system (EGCS) is inevitably necessary. The viewpoint of designing the EGCS is very important. The passenger-based viewpoint proposed provides a new way to think about this system. The capacity constraint following consideration for the passengers is utilized to make the performance better. Details of elevator dynamics are modeled to meet the requirements. A traffic database is constructed in order to rebuild the system environment containing information of passengers so that it can be made as close to the real environment as possible. The rescheduling ability is achieved by a new mechanism-HCPM refinement, which is a priority maker for hall calls. The advantages of our EGCS are shown through extensive simulation results. We make a comparison between our EGCS and the previous one, which shows that our results are quite satisfactory and superior.