The flexible job shop scheduling problem (FJSP), which is NP-hard, widely exists in many manufacturing industries. It is very hard to be solved. A multi-swarm collaborative genetic algorithm (MSCGA) based on the collaborative optimization algorithm is proposed for the FJSP. Multi-population structure is used to independently evolve two sub-problems of the FJSP in the MSCGA. Good operators are adopted and designed to ensure this algorithm to achieve a good performance. Some famous FJSP benchmarks are chosen to evaluate the effectiveness of the MSCGA. The adaptability and superiority of the proposed method are demonstrated by comparing with other reported algorithms.
In order to solve the flexible job shop scheduling problem with variable batches, we propose an improved multi-objective optimization algorithm, which combines the idea of inverse scheduling. First, a flexible job shop problem with the variable batches scheduling model is formulated. Second, we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method. Moreover, in order to increase the diversity of the population, two methods are developed. One is the threshold to control the neighborhood updating, and the other is the dynamic clustering algorithm to update the population. Finally, a group of experiments are carried out. The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively, and has effective performance in solving the flexible job shop scheduling problem with variable batches.
Multi-manned assembly line, which is broadly utilized to assemble high volume products such as automobiles and trucks, allows a group of workers to assemble different tasks simultaneously in a multi-manned workstation. This additional characteristic of parallel operators increases the complexity of the traditional NP-hard assembly line balancing problem. Hence, this paper formulates the Type-I multi-manned assembly line balancing problem to minimize the total number of workstations and operators, and develops an efficient migrating birds optimization algorithm embedded into an idle time reduction method. In this algorithm, a new decoding mechanism is proposed which reduces the sequence-dependent idle time by some task assignment rules; three effective neighborhoods are developed to make refinement of existing solutions in the bird improvement phases; and temperature acceptance and competitive mechanism are employed to avoid being trapped in the local optimum. Comparison experiments suggest that the new decoding and improvements are effective and the proposed algorithm outperforms the compared algorithms.
In a typical discrete manufacturing process, a new type of reconfigurable production line is introduced, which aims to help small- and mid-size enterprises to improve machine utilization and reduce production cost. In order to effectively handle the production scheduling problem for the manufacturing system, an improved multi-objective particle swarm optimization algorithm based on Brownian motion (MOPSO-BM) is proposed. Since the existing MOPSO algorithms are easily stuck in the lo-cal optimum, the global search ability of the proposed method is enhanced based on the random motion mechanism of the BM. To further strengthen the global search capacity, a strategy of fitting the inertia weight with the piecewise Gaussian cumulative distribution function (GCDF) is included, which helps to maintain an excellent convergence rate of the algorithm. Based on the commonly used indicators generational distance (GD) and hypervolume (HV), we compare the MOPSO-BM with several other latest algorithms on the benchmark functions, and it shows a better overall performance. Furthermore, for a real reconfigurable production line of smart home appliances, three algorithms, namely non-dominated sorting genetic algorithm-II (NSGA-II), decomposition-based MOPSO (dMOPSO) and MOPSO-BM, are applied to tackle the scheduling problem. It is demonstrated that MOPSO-BM outperforms the others in terms of convergence rate and quality of solutions.
Surrogate models have shown to be effective in assisting evolutionary algorithms (EAs) for solving computationally expensive complex optimization problems. However, the effectiveness of the existing surrogate-assisted evolutionary algorithms still needs to be improved. A data-driven evolutionary sampling optimization (DESO) framework is proposed, where at each generation it randomly employs one of two evolutionary sampling strategies, surrogate screening and surrogate local search based on historical data, to effectively balance global and local search. In DESO, the radial basis function (RBF) is used as the surrogate model in the sampling strategy, and different degrees of the evolutionary process are used to sample candidate points. The sampled points by sampling strategies are evaluated, and then added into the database for the updating surrogate model and population in the next sampling. To get the insight of DESO, extensive experiments and analysis of DESO have been performed. The proposed algorithm presents superior computational efficiency and robustness compared with five state-of-the-art algorithms on benchmark problems from 20 to 200 dimensions. Besides, DESO is applied to an airfoil design problem to show its effectiveness.
It is of great significance to carry out effective scheduling for the carrier-based aircraft flight deck operations. In this paper, the precedence constraints and resource constraints in flight deck operations are analyzed, then the model of the multi-aircraft integrated scheduling problem with transfer times (MAISPTT) is established. A dual population multi-operator genetic algorithm (DPMOGA) is proposed for solving the problem. In the algorithm, the dual population structure and random-key encoding modified by starting/ending time of operations are adopted, and multiple genetic operators are self-adaptively used to obtain better encodings. In order to conduct the mapping from encodings to feasible schedules, serial and parallel scheduling generation scheme-based decoding operators, each of which adopts different justified mechanisms in two separated populations, are introduced. The superiority of the DPMOGA is verified by simulation experiments.
Considering the flexible attitude maneuver and the narrow field of view of agile Earth observation satellite (AEOS) together, a comprehensive task clustering (CTC) is proposed to improve the observation scheduling problem for AEOS (OSPFAS). Since the observation scheduling problem for AEOS with comprehensive task clustering (OSWCTC) is a dynamic combination optimization problem, two optimization objectives, the loss rate (LR) of the image quality and the energy consumption (EC), are proposed to format OSWCTC as a bi-objective optimization model. Harnessing the power of an adaptive large neighborhood search (ALNS) algorithm with a nondominated sorting genetic algorithm II (NSGA-II), a bi-objective optimization algorithm, ALNS+NSGA-II, is developed to solve OSWCTC. Based on the existing instances, the efficiency of ALNS+NSGA-II is analyzed from several aspects, meanwhile, results of extensive computational experiments are presented which disclose that OSPFAS considering CTC produces superior outcomes.
The multi-compartment electric vehicle routing problem (EVRP) with soft time window and multiple charging types (MCEVRP-STW&MCT) is studied, in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process, are employed. A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost, distribution cost, time window penalty cost and charging service cost. To solve the problem, an estimation of the distribution algorithm based on Lévy flight (EDA-LF) is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum. Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm. In addition, when comparing with existing algorithms, the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances. Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.
