Research On Shop Scheduling Problem Based On Swarm Intelligence Algorithm

In the manufacturing field,there are three important production targets pursued by manufacturing companies: high efficiency,high flexibility and high reliability.Optimized scheduling is an important part of achieving them.With the development and improvement of modern integrated manufacturing systems,people's requirements for intelligent shop scheduling have also increased.The traditional shop scheduling problem is simplified based on the actual production scheduling problem.And the flexible job shop scheduling problem(FJSP)is a more flexible and complex problem extended on the traditional job shop scheduling problem(JSP).Compared with the traditional scheduling problem,FJSP is closer to the actual manufacturing environment and more in line with the modern concept of flexible manufacturing.Shop scheduling problem is NP-hard combinatorial optimization problem,the larger the scale of the problem,the higher the complexity of the problem.Because of its high search efficiency and robustness,swarm intelligence algorithm shows good performance in solving the combinatorial optimization problem of shop scheduling.This paper studies three types of FJSP and uses different algorithms to solve them.The main contents are as follows.(1)The bat algorithm is used to solve the single objective FJSP,which is to minimize the makespan.According to the discrete characteristics of the problem and the weakness of the local search ability of the algorithm,a hybrid genetic bat algorithm is proposed with the assistance of the crossover operation of the genetic algorithm for the optimization.Firstly,machine-based coding is used to complete the mapping of the problem solution space to a search space which can be processed by the algorithm.And in order to improve the quality and diversity of the initial population,three methods are combined to generate the initial population.Then,using dynamic degressive weights assists in searching the solution space.According to the coding method,the hybrid column crossover method is proposed to complete the location update for avoiding the generation of invalid solutions.Finally,the effectiveness of the improvement measures and the performance of the algorithm are verified by multiple sets of comparison experiments.The results prove the effectiveness and superiority of the proposed algorithm when solving the scheduling problem.(2)For the FJSP with multi-objective constraints,the discrete artificial bee colony algorithm based on Pareto solution set is proposed.Because the selection probability calculation method of the classical artificial bee colony algorithm is not suitable for multi-objective problems,the selection probability is redefined to depend on ranking with the Pareto domination concept.At the same time,in order to overcome the disadvantage that the local search of the artificial bee colony algorithm is not suitable for discrete problems,the local search based on mutation operation is proposed,and the crossover operator is used to improve the diversity of the population.Then,the Pareto solution set is trimmed by the harmonic average distance to complete the updating of the Pareto solution set.Finally,the effectiveness of the algorithm in solving the scheduling problem is verified by multiple sets of specific multi-target scheduling data.(3)Aiming at the uncertain FJSP with processing time as the interval number,an improved artificial bee colony algorithm is proposed.Double-layer coding method is adopted to determine the selection of processing machines and the processing sequence of the jobs,directly avoiding the machine conflict problem during processing.Interval possibility is used to select a better solution and the calculation for the selection probability.Considering the different situations of double coding,the location is updated respectively by two different ways.Finally,the effectiveness of the algorithm in solving the uncertain scheduling problem is verified by multiple scheduling instances.