Biogeography-based Optimization And Its Application In Dynamic Shop Scheduling

The shop scheduling,which is the core technology in the manufacturing system,plays an essential role in the manufacturing industry.The management efficiency of the enterprise and the competitiveness of manufacturing enterprises are improved by feasible and efficient scheduling methods.Most of the scheduling problems are the complex NP-hard problem.The traditional methods are difficult to satisfy the requirements of enterprise in the real manufacturing systems with the increasement of problem size.Therefore,the research of the scheduling theory and effective scheduling scheme is a focus in the research field.Biogeography-based Optimization(BBO),which is a new swarm intelligence optimization algorithm,is inspired by the biogeography theory.The BBO algorithm has drawn various attentions as the unique operational mechanism,relatively few parameters and the excellent ability of exploitation.In this paper,the advantages and disadvantages of the BBO algorithm are analyzed through theory and experiment.For the different shop scheduling problems,the BBO algorithm is modified to balance the abilities of exploration and exploitation.The main research contents of this paper are as follows.(1)On the numeric optimization problem,the standard BBO algorithm has poor exploration ability and over-dependence on the coordinate system.A two-stage differential biogeography-based optimization algorithm(TDBBO)is proposed in this paper.First,the two-stage migration model is designed to control the diversity of population in the early evolution stage and the convergence speed is acceleated in the later evolution stage.Second,an improved migration operator is employed to enhance the rotation invariance of the algorithm.Third,the Gaussian mutation operator is introduced to escape the local optimal solution effectively.Finally,the greedy selection strategy is employed to accelerate the convergence speed.Furthermore,the Markov model is used to analyze the convergence performance of the TDBBO algorithm.Experimental results on the CEC2017 benchmark demonstrate that the efficiency and performance of TDBBO for solving numeric optimization problem.(2)The hybrid biogeography-based optimization with variable neighborhood search mechanism(HBV)is designed for solving the no-wait flow shop problem(NWFSP)with the objective of minimizing makespan.In the HBV algorithm,the MNEH and NN mechanisms are employed to generate initial population.Therefore,the path relink and the block-based self-improved strategy are embedded into the migration operator to accelerate the convergence speed of the HBV algorithm.Meanwhile,the mutation operator,which is based on the iterative greedy algorithm(IG),is designed to extend the potential search domain.Finally,the variable neighborhood search strategy based on the block neighborhood structure and insertion neighborhood structure is applied to perform the local search around the best candidate.Furthermore,the Markov model is employed to analyze the global convergence performance of the HBV algorithm.Simulation results and statistical analysis show that the efficiency and effectiveness of HBV algorithm for NWFSP.(3)The oppositional metropolis biogeography-based optimization(OMBBO)is designed for the classic job shop scheduling problem(JSSP).First,the JSSP problem domain is transformed into a continuous problem domain by the smallest position value(SPV),and the active scheduling decoding rule is employed to reduce search space.Second,the chaotic theory and the oppositional learning strategy are employed to initialize the population.The improved migration operator and the Gaussian mutation operator are introduced to enhance the exploration of the standard BBO algorithm.Furthermore,the acceptance criterion,which is based on simulated annealing,is designed to control the diversity of population.Finally,a critical neighborhood based variable neighborhood search is employed to search around the global optimal solution.The simulation results show that the performance of OMBBO algorithm is significantly better than the performance of classic JSSP algorithm.