A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking

A flow-shop scheduling problem with blocking has important applications in a variety of industrial systems but is underrepresented in the research literature. In this study, a novel discrete artificial bee colony (ABC) algorithm is presented to solve the above scheduling problem with a makespan criterion by incorporating the ABC with differential evolution (DE). The proposed algorithm (DE-ABC) contains three key operators. One is related to the employed bee operator (i.e. adopting mutation and crossover operators of discrete DE to generate solutions with good quality); the second is concerned with the onlooker bee operator, which modifies the selected solutions using insert or swap operators based on the self-adaptive strategy; and the last is for the local search, that is, the insert-neighbourhood-based local search with a small probability is adopted to improve the algorithm's capability in exploitation. The performance of the proposed DE-ABC algorithm is empirically evaluated by applying it to well-known benchmark problems. The experimental results show that the proposed algorithm is superior to the compared algorithms in minimizing the makespan criterion.     

A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem

To solve the multi-objective flexible job-shop problem (MFJSP), an effective Pareto-based estimation of distribution algorithm (P-EDA) is proposed. The fitness evaluation based on Pareto optimality is employed and a probability model is built with the Pareto superior individuals for estimating the probability distribution of the solution space. In addition, a mechanism to update the probability model is proposed, and the new individuals are generated by sampling the promising searching region based on the probability model. To avoid premature convergence and enhance local exploitation, the population is divided into two sub-populations at certain generations according to a splitting criterion, and different operators are designed for the two sub-populations to generate the promising neighbour individuals. Moreover, multiple strategies are utilised in a combination way to generate the initial solutions, and a local search strategy based on critical path is proposed to enhance the exploitation ability. Furthermore, the influence of parameters is investigated based on the Taguchi method of design of experiment, and a suitable parameter setting is suggested. Finally, numerical simulation based on some well-known benchmark instances and comparisons with some existing algorithms are carried out. The comparative results demonstrate the effectiveness of the proposed P-EDA in solving the MFJSP.     

An Improved Whale Optimization Algorithm for Feature Selection

Whale optimization algorithm (WOA) is a new population-based metaheuristic algorithm. WOA uses shrinking encircling mechanism, spiral rise, and random learning strategies to update whale’s positions. WOA has merit in terms of simple calculation and high computational accuracy, but its convergence speed is slow and it is easy to fall into the local optimal solution. In order to overcome the shortcomings, this paper integrates adaptive neighborhood and hybrid mutation strategies into whale optimization algorithms, designs the average distance from itself to other whales as an adaptive neighborhood radius, and chooses to learn from the optimal solution in the neighborhood instead of random learning strategies. The hybrid mutation strategy is used to enhance the ability of algorithm to jump out of the local optimal solution. A new whale optimization algorithm (HMNWOA) is proposed. The proposed algorithm inherits the global search capability of the original algorithm, enhances the exploitation ability, improves the quality of the population, and thus improves the convergence speed of the algorithm. A feature selection algorithm based on binary HMNWOA is proposed. Twelve standard datasets from UCI repository test the validity of the proposed algorithm for feature selection. The experimental results show that HMNWOA is very competitive compared to the other six popular feature selection methods in improving the classification accuracy and reducing the number of features, and ensures that HMNWOA has strong search ability in the search feature space.     

An artificial bee colony algorithm for the economic lot scheduling problem

In this study, we present an artificial bee colony (ABC) algorithm for the economic lot scheduling problem modelled through the extended basic period (EBP) approach. We allow both power-of-two (PoT) and non-power-of-two multipliers in the solution representation. We develop mutation strategies to generate neighbouring food sources for the ABC algorithm and these strategies are also used to develop two different variable neighbourhood search algorithms to further enhance the solution quality. Our algorithm maintains both feasible and infeasible solutions in the population through the use of some sophisticated constraint handling methods. Experimental results show that the proposed algorithm succeeds to find the all the best-known EBP solutions for the high utilisation 10-item benchmark problems and improves the best known solutions for two of the six low utilisation 10-item benchmark problems. In addition, we develop a new problem instance with 50 items and run it at different utilisation levels ranging from 50 to 99% to see the effectiveness of the proposed algorithm on large instances. We show that the proposed ABC algorithm with mixed solution representation outperforms the ABC that is restricted only to PoT multipliers at almost all utilisation levels of the large instance.     

Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy,particle swarm optimisation,and genetic algorithm

Determining the locations of departments or machines in a shop floor is classified as a facility layout problem. This article studies unequal-area stochastic facility layout problems where the shapes of departments are fixed during the iteration of an algorithm and the product demands are stochastic with a known variance and expected value. These problems are non-deterministic polynomial-time hard and very complex, thus meta-heuristic algorithms and evolution strategies are needed to solve them. In this paper, an improved covariance matrix adaptation evolution strategy (CMA ES) was developed and its results were compared with those of two improved meta-heuristic algorithms (i.e. improved particle swarm optimisation [PSO] and genetic algorithm [GA]). In the three proposed algorithms, the swapping method and two local search techniques which altered the positions of departments were used to avoid local optima and to improve the quality of solutions for the problems. A real case and two problem instances were introduced to test the proposed algorithms. The results showed that the proposed CMA ES has found better layouts in contrast to the proposed PSO and GA.     

Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem

This article presents an effective estimation of distribution algorithm, named P-EDA, to solve the blocking flow-shop scheduling problem (BFSP) with the makespan criterion. In the P-EDA, a Nawaz–Enscore–Ham (NEH)-based heuristic and the random method are combined to generate the initial population. Based on several superior individuals provided by a modified linear rank selection, a probabilistic model is constructed to describe the probabilistic distribution of the promising solution space. The path relinking technique is incorporated into EDA to avoid blindness of the search and improve the convergence property. A modified referenced local search is designed to enhance the local exploitation. Moreover, a diversity-maintaining scheme is introduced into EDA to avoid deterioration of the population. Finally, the parameters of the proposed P-EDA are calibrated using a design of experiments approach. Simulation results and comparisons with some well-performing algorithms demonstrate the effectiveness of the P-EDA for solving BFSP.     

A hybrid approach combining modified artificial bee colony and cuckoo search algorithms for multi-objective cloud manufacturing service composition

This paper proposes a multi-objective hybrid artificial bee colony (MOHABC) algorithm for service composition and optimal selection (SCOS) in cloud manufacturing, in which both the quality of service and the energy consumption are considered from the perspectives of economy and environment that are two pillars of sustainable manufacturing. The MOHABC uses the concept of Pareto dominance to direct the searching of a bee swarm, and maintains non-dominated solution found in an external archive. In order to achieve good distribution of solutions along the Pareto front, cuckoo search with Levy flight is introduced in the employed bee search to maintain diversity of population. Furthermore, to ensure the balance of exploitation and exploration capabilities for MOHABC, the comprehensive learning strategy is designed in the onlooker search so that every bee learns from the external archive elite, itself and other onlookers. Experiments are carried out to verify the effect of the improvement strategies and parameters’ impacts on the proposed algorithm and comparative study of the MOHABC with typical multi-objective algorithms for SCOS problems are addressed. The results show that the proposed approach obtains very promising solutions that significantly surpass the other considered algorithms.     

混合花朵授粉算法在作业车间调度中的应用

对最大完工时间最短的作业车间调度问题进行了研究,总结了当前求解作业车间调度问题的研究现状,提出一种花朵授粉算法与遗传算法的混合算法。混合算法以花朵授粉算法为基础,重新定义其全局搜索和局部搜索迭代公式,在同化操作过程中融入遗传算法的选择、优先交叉和变异操作,进一步增强算法的勘探能力。通过26个经典的基准算例仿真实验,并与近5年的其他算法比较,结果表明所提算法在求解作业车间调度问题具有一定优势。     

基于分类优化贝叶斯结构算法的篦冷机参数状态分析及其算法收敛性分析

针对种群算法建立贝叶斯结构存在参数多、易陷入局部最优的问题,提出一种改进贝叶斯结构学习算法。该算法将候选结构分为优劣解集,利用师生交流机制优化优解集保留精英个体,利用变异机制优化劣解集来增加结构多样性,从而加快算法收敛速度,并在准确率和运行时间上达到平衡。最后不仅利用马尔科夫链证明该算法是全局收敛的,而且通过仿真实验验证了所提出算法的性能。将该算法应用到水泥篦冷机的实际数据中,构建水泥篦冷机工艺参数的贝叶斯网络结构,并完成篦冷机参数状态分析。     

A weight-based multiobjective immune algorithm: WBMOIA

A novel immune algorithm is suggested for finding Pareto-optimal solutions to multiobjective optimization problems based on opt-aiNET, the artificial immune system algorithm for multi-modal optimization. In the proposed algorithm, a randomly weighted sum of multiple objectives is used as a fitness function, and a local search algorithm is incorporated to facilitate the exploitation of the search space. Specifically, a new truncation algorithm with similar individuals (TASI) is proposed to preserve the diversity of the population. Also, a new selection operator is presented to create the new population based on TASI. Simulation results on seven standard problems (ZDT2, ZDT6, DEB, VNT, BNH, OSY and KIT) show that the proposed algorithm is able to find a much better spread of solutions and better convergence near the true Pareto-optimal front compared to the vector immune algorithm and the elitist non-dominated sorting genetic system.     

A problem space algorithm for single machine weighted tardiness problems

We propose a problem space genetic algorithm to solve single machine total weighted tardiness scheduling problems. The proposed algorithm utilizes global and time-dependent local dominance rules to improve the neighborhood structure of the search space. They are also a powerful exploitation (intensifying) tool since the global optimum is one of the local optimum solutions. Furthermore, the problem space search method significantly enhances the exploration (diversification) capability of the genetic algorithm. In summary, we can improve both solution quality and robustness over the other local search algorithms reported in the literature.     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm

The flow shop scheduling problem with blocking has important applications in a variety of industrial systems but is under-represented in the research literature. In this paper, a modified fruit fly optimisation (MFFO) algorithm is proposed to solve the above scheduling problem for makespan minimisation. The MFFO algorithm mainly contains three key operators. One is related to the initialisation scheme in which a problem-specific heuristic is adopted to generate an initial fruit fly swarm location with high quality. The second is concerned with the smell-based search in which a neighbourhood strategy is designed to generate a new location. To further enhance the exploitation of the proposed algorithm considered, a speed-up insert-neighbourhood-based local search is applied with a probability. Finally, the last is for the vision-based search in which an update criterion is proposed to induce the fruit fly into a better searching space. The simulation experimental results demonstrated the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. Moreover, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

基于改进混合遗传细菌觅食算法的贝叶斯结构学习算法

针对利用启发式学习算法学习贝叶斯网络时容易陷入局部最优和寻优效率低的问题,提出一种改进的混合遗传细菌觅食优化算法的贝叶斯网络结构学习算法。该算法首先通过遗传算法求得较优种群并作为细菌觅食算法的初始种群;然后利用交叉和变异策略改进细菌觅食算法的复制行为,增加种群多样性,扩大搜索空间;最后通过改进细菌觅食算法的迁移行为的初始化操作更新种群,防止精英个体的丢失。通过种群的迭代搜索最终获得最优的贝叶斯网络结构。实验仿真结果表明,与其他算法相比,该算法的收敛精度和效率有所提升。     

A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem

Different from the classical job shop scheduling, the dual-resource constrained flexible job-shop scheduling problem (DRCFJSP) should deal with job sequence, machine assignment and worker assignment all together. In this paper, a knowledge-guided fruit fly optimisation algorithm (KGFOA) with a new encoding scheme is proposed to solve the DRCFJSP with makespan minimisation criterion. In the KGFOA, two types of permutation-based search operators are used to perform the smell-based search for job sequence and resource (machine and worker) assignment, respectively. To enhance the search capability, a knowledge-guided search stage is incorporated into the KGFOA with two new search operators particularly designed for adjusting the operation sequence and the resource assignment, respectively. Due to the combination of the knowledge-guided search and the smell-based search, global exploration and local exploitation can be balanced. Besides, the effect of parameter setting of the KGFOA is investigated and numerical tests are carried out using two sets of instances. The comparative results show that the KGFOA is more effective than the existing algorithms in solving the DRCFJSP.     

A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems

Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of Estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP.     

求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard问题,其求解算法多为启发式算法。该文侧重于构造布局求解算法中定位函数(规则)的优化,将模拟退火算法的思想融入到遗传算法中,提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。     

A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking

Batch processing machines (BPMs) have important applications in a variety of industrial systems. This paper considers the problem of scheduling two BPMs in a flow shop with arbitrary release times and blocking such that the makespan is minimised. The problem is formulated as a mixed integer programming model. Subsequently, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In the algorithm, individuals in the population are first represented as discrete job sequences, and mutation and crossover operators are applied based on the representation. Second, after using the first-fit rule to form batches, a novel least idle/blocking time heuristic is developed to schedule the batches in the flow shop. Furthermore, an effective local search technique is embedded in the algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a genetic algorithm and a simulated annealing algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.     

An extended continuous estimation of distribution algorithm for solving the permutation flow-shop scheduling problem

This article proposes an extended continuous estimation of distribution algorithm (ECEDA) to solve the permutation flow-shop scheduling problem (PFSP). In ECEDA, to make a continuous estimation of distribution algorithm (EDA) suitable for the PFSP, the largest order value rule is applied to convert continuous vectors to discrete job permutations. A probabilistic model based on a mixed Gaussian and Cauchy distribution is built to maintain the exploration ability of the EDA. Two effective local search methods, i.e. revolver-based variable neighbourhood search and Hénon chaotic-based local search, are designed and incorporated into the EDA to enhance the local exploitation. The parameters of the proposed ECEDA are calibrated by means of a design of experiments approach. Simulation results and comparisons based on some benchmark instances show the efficiency of the proposed algorithm for solving the PFSP.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.