Research On Hybrid Bat Algorithm And Its Application In Scheduling Management

Scheduling optimization problems are prevalent.The bat algorithm provides a new idea and a new method for solving complex scheduling and optimization problems.Bat Algorithm is a new metaheuristic optimization method that simulates the echolocation behavior of bats,with simple structure,few parameters,and high robustness.At present,the bat algorithm combines the advantages of existing metaheuristic algorithms and the characteristics of acoustic echolocation and has received wide attention from scholars at domestic and abroad and has been applied in different industrial fields.Although this algorithm can solve optimization problems as well as engineering and management problems and has a broad application prospect,the algorithm itself suffers from defects such as easy to fall into local optimum and low accuracy of late search,which greatly limit the global search capability and application scope of the bat algorithm.Therefore,to address the weak theoretical foundation,the imbalance between local search and global search of the bat algorithm can lead to slow convergence of the algorithm and other problems.In this dissertation,based on the bat algorithm,we improve the diversity of bat populations and the local search ability as well as the global search ability of the algorithm.An improved hybrid bat algorithm is proposed.This algorithm designs a scheduling rule to initialize the roosts.Moreover,the search direction,step size,loudness and pulse firing rate of the algorithm are optimized by using population grouping,back propagation algorithm based on MSE and conjugate gradient method.Meanwhile,a local search strategy with multiple neighborhoods and a global search capability of the bat algorithm using Lévy Flight are proposed to improve the bat algorithm.For each of these three improvement strategies,they are combined with the original bat algorithm.Three different types of bat algorithms are generated.And they are applied to the scheduling problem to verify the feasibility and effectiveness of these three algorithms.The main research work of this dissertation is as follows.(1)In order to improve the diversity of the initial bat population,a discrete bat algorithm based on k-means clustering factor and neighborhood structure is proposed.The algorithm generates the initial population from the scheduling model and reclassifies the predation range of bats.A new dynamic predation mechanism and migration strategy based on the neighborhood structure are proposed,and the k-means similarity operator is improved to group bats into populations based on the highest similarity.Meanwhile,an elite learning strategy is introduced to improve the local search ability of the discrete bat algorithm and prevent premature convergence of the algorithm.Simulation results in solving the three-stage assembly flowshop scheduling problem show that,firstly,DBA outperforms TS,VNS and the two heuristic algorithms on the three different dimensional problems of number of products,number of machines,and groups tested.Secondly,the introduction of lower bound and scheduling models can improve its overall performance.Finally,the improvement of these features,such as population grouping,dynamic control parameters,and elite strategies,can effectively improve the local search ability of DBA.(2)To improve the local search capability of the bat algorithm,an improved bat optimization algorithm based on variable neighborhood search and two learning strategies is proposed.The algorithm is designed with a search-based bat population based on a backpropagation algorithm with mean square error MSE and a capture-based bat population based on conjugate gradient.These two populations with different search capabilities aim to solve the scheduling optimization problem where the convergence and diversity of bat algorithms are difficult to be balanced.At the same time,the information of the populations is fully exploited to design a new selection mechanism used to update the speed and position of the bat algorithm,leading to an effective solution to the problem of how to make a trade-off between search and exploration in solving the optimal problem.Moreover,the Gaussian and elite learning methods are used to help the bat population to jump out of the local optimum.Further,based on the three neighborhood structures of insert operator,the local search methods VND3 BA and VND2 BA with variable neighborhood search are proposed to make IMBA avoid premature convergence in the search process.Meanwhile,distributed computing is introduced to combine with the three-stage assembly pipeline scheduling problem to solve the three-stage distributed assembly replacement pipeline shop scheduling optimization problem.The simulation results show that IMBA can minimize the completion time of this problem.The algorithm not only obtains the lowest relative percentage deviation value,but also the smallest average RPD value,which fully proves that IMBA is a good performance,more stable and more robust algorithm.(3)To improve the global search capability of the algorithm,a hybrid multiobjective bat algorithm based on Lévy flight is proposed.Based on the bat population classification,the search direction and step size of the algorithm are updated,and the weights and biases of the network are adjusted,which extends the search range and enhances the ability to solve feasible solutions.Secondly,the back propagation based on the mean square error and conjugate gradient method is used to improve and optimize the loudness and pulse firing rate of the bat algorithm,which can effectively solve the problems of local optimum and early convergence and can effectively improve the convergence accuracy and convergence speed of the algorithm.Finally,the introduction of Lévy flight makes it combined with the bat algorithm,and the alternating long and short features can effectively find the global optimal solution.The resource scheduling problem of cloud computing is also solved with the minimum completion time,throughput,cost and the most stable imbalance as the objective function.Simulation experiments demonstrate that MOBA can achieve the search for better target regions more effectively and reduce the completion time of task clouds in cloud computing compared with other multi-objective algorithms.It significantly reduces the cost and energy consumption of the cloud computing system under the premise of ensuring the load balance of network nodes,thus realizing a balanced and reasonable use of resources,which leads to a fast and good sustainable development.This shows that MOBA can well balance the local search and global search of the algorithm and can be used as an effective algorithm for global optimization.(4)Three improvement strategies are incorporated and finally a hybrid bat algorithm is proposed.To validate the performance of the hybrid bat algorithm,it is applied to more complex three-stage distributed hybrid flow shop scheduling problems with sequence-dependent setup times and function optimization problems.In particular,the three-stage distributed hybrid flow shop scheduling problem consists of three subproblems,such as assigning work to plants,determining the sequence of work in each plant,and selecting machines for each process at each stage such that the firststage setup SDST is process-dependent,and the objective function is to minimize the average flow time and the maximum delay time.By comparing the population size of bats,the dimensionality of the problem,different inertia weights and iteration thresholds,the parameter values suitable for the problem are selected and the LOV rule is used to transform the individuals in the IHBA from real vectors to artifact ordering.Simulation experiments demonstrate that IHBA,an algorithm combining three improved strategies,has better solution performance,better convergence speed and accuracy than DBA,IMBA and MOBA in the function optimization problem.Also,in solving the three-stage distributed hybrid flowshop scheduling problem with SDST,IHBA performs better than IMBA with less fluctuation considering the relative range of the payable dates and the delay factor,which shows that the range of the payable dates can affect the performance of the algorithm,and the performance becomes relatively worse as its range increases.Moreover,changes in the delay factor change the time interval of the payable dates.In terms of processes and different numbers of parallel machines in the first stage,the results of the average error percentage of IHBA are smaller than those of IMBA,and the performance of process fluctuation and number of jobs is better than that of IMBA.This shows that the IHBA algorithm proposed in this dissertation is a global optimization algorithm that can solve the complex hybrid flow shop scheduling problem.