Swarm Intelligence Optimization Algorithm And Its Application In Flow Shop Scheduling Problem

The scheduling problem mainly studies the allocation of resources,sets corresponding optimization objectives for different tasks,and finally finds the optimal or approximate optimal solution.Scheduling problem exists widely in social production and life,especially in all kinds of manufacturing enterprises.Well-designed production scheduling scheme helps to improve production efficiency and help enterprises to take an active position in the fierce competition of market.From the perspective of scheduling solutions,traditional operations research algorithms and heuristic rules face great difficulties in solving large-scale scheduling problems.They have high requirements on the constraints of the problem,and sometimes it is difficult to obtain satisfactory solutions.Swarm intelligence optimization algorithm is a kind of metaheuristic algorithm that has been widely concerned in recent years.When applying it to solve scheduling problems,generally a better model can be established without strong constraints,so as to obtain satisfactory scheduling solutions.Swarm intelligence optimization algorithm provides a new and effective method to solve the scheduling problem.This thesis takes the flow-shop scheduling problem and the swarm intelligence optimization algorithm as the research object.On the basis of in-depth research and analysis of the scheduling problem,several improved swarm intelligence optimization algorithms are proposed to solve the problem.The main research contents of this paper are as follows:To solve the permutation flow shop scheduling problem(PFSP),a hybrid ant colony optimization algorithm(HACO)was proposed.The HACO algorithm has made many effective improvements to the ant colony algorithm.Rajendran algorithm is used for the population initialization in the initialization phase to ensure the quality of the initial population.In the state transition phase,heuristic information based on short job priority is used.In the pheromone renewal phase,an exponential function is proposed as the pheromone concentration evaporation coefficient,which is adjusted adaptively with the search.In the local search phase,a local search algorithm based on integer sequence set is proposed to further improve the quality of high-quality solutions.In terms of the reception criterion of the optimal solution,the criterion of simulated annealing algorithm is added to judge the reception of the newly generated solution,which increases the diversity of the solution and effectively avoids the algorithm falling into local optimization.Finally,the comparison experiment proves the effectiveness of the HACO algorithm in solving the permutation flow shop scheduling problem.Aiming at the blocking flow shop scheduling problem(BFSSP),a dynamic multipopulation ant colony optimization algorithm(DMACO)was proposed on the basis of the study on the inter-population coevolution algorithm.DMACO algorithm divides ant colony into three types: one elite colony,several searching colonies and one variable colony.In the initial phase of the algorithm only elite colony and search colonies participate in the search of solution,when the iteration reach a certain number,a variation colony is dynamic generated by the worst individuals of searching colonies and elite colony.variation colony first to initialization and then participate in the optimization,variation colony can help algorithm jump out of the original search space to another search,increasing the diversity of solution.In terms of population communication,in the initial phase of the algorithm,the high-quality solutions are exchanged among multiple searching colonies in accordance with certain rules.After a certain number of iterations,an optimal solution is selected from all searching colonies and transmitted to the elite colony,which the elite colony transmits a poor solution to the corresponding searching colony.After the generation of the variation population,the optimal solution found after each iteration is compared with the optimal solution of the elite colony.If the optimal solution is passed to the elite population,the elite population will pass a poor solution to the mutant colony.After each iteration of the elite colony,a local search algorithm is performed to an optimal solution and a suboptimal solution to further improve the quality of the solution.Finally,the comparative experiment proves the superiority of DMACO algorithm to solve the blocking flow-shop scheduling problem.To solve the blocking flow shop scheduling problem(BFSSP)with maximum completion time(i.e.makespan)criterion,an improved biogeography-based optimization algorithm(IBBO)was proposed.The vector coding method is used in the IBBO algorithm based on the arrangement of the job to conveniently represent the sequence of the job as the solution of the problem.In the population initialization phase,NEH rule and random method are used for population initialization to ensure the quality of the initial solution and improve the diversity of the initial population.In the migration phase,the migration rate is improved,and a migration operation based on insert rule is proposed.In the mutation phase,the mutation rate is improved,and a mutation operation based on swap rule is proposed.In the local search phase,a local search algorithm based on insertion neighborhood is used for the optimal solution generated by each iteration to further enhance the optimization ability of the algorithm.The IBBO algorithm also preserves the superior solutions of the previous generation by designing elite strategies.Finally,the computational results show the effectiveness of the proposed IBBO algorithm in solving the blocking flow shop scheduling with maximum completion time criterion.An discrete biogeography-based optimization algorithm(DBBO)is proposed for solving the flow shop scheduling problem with intermediate buffers to minimize the Total flow time(TFT).for solving the TFT(Total Flow Time)problem.In the initial phase,two heuristic rules that NEH and NEH_WPT are used to generate the initial population,which effectively improves the quality of the initial population.In the migration phase,cosine migration model is used,and a migration algorithm is proposed based on two-point.At the mutation phase,a mutation model was proposed that combined the individual fitness value with the maximum fitness value of the population,and a mutation algorithm was proposed based on the inverse rule.In the local search phase,a new local search algorithm(IS algorithm)based on the alternation of insert and swap is proposed,which can not only effectively avoid the algorithm falling into the local optimal,but also accelerate the search process of the algorithm.Finally,in the experimental analysis phase,a parameter selection experiment was designed to select the appropriate algorithm parameters,and the comparison experiment with other algorithms effectively proved the superiority of DBBO algorithm in solving the flow shop scheduling problem with intermediate buffers with the TFT criterion.