Research On The Dynamic Job Shop Scheduling Problem Based On Particle Swarm Optimization Algorithm

Job shop scheduling is an important factor to effect the efficiency in a manufacturing enterprise. A good production scheduling system can reduce the cost and improve the efficiency, it’s the core competitiveness of enterprise. So more and more scholars are involved in the study of this problem in recent years. The Job Shop Scheduling Problem(JSP) is a typical combinatorial optimization, which is evolved from a series of the production scheduling problem. The Artificial Intelligence algorithm is the mainly way to solve the job shop scheduling problem, although a single algorithm is difficult to get the best solution. In recent years, using hybrid algorithm to solve the job shop scheduling problem becomes a hot term. Particle swarm optimization algorithm(PSO) is one of the most widely used algorithms for the characteristics of simple operation, rapid convergence etc. And it has been successfully applied in combinatorial optimization problems.This paper is intended to study on the improvement of PSO and its application in JSP. The main contents include the following aspects:Firstly, introduced the development and achievement of the JSP. Elaborated the principles of PSO and its application in job shop scheduling problem.Secondly, based on the characteristics of PSO and JSP, a discrete particle swarm optimization algorithm(DPSO) has been proposed, which use the crossover operation of genetic algorithm(GA) to update population. And then the DPSO was improved through introducing local search algorithm and adding additional information reference point, formed into hybrid particle swarm optimization algorithm(GSPSO). The GSPSO can achieve accurate search in local area and increase the probability of search the optimal solution in global area.Thirdly, the GSPSO algorithm was used to solving the static job shop scheduling problem. The convergence speed of the hybrid algorithm was verified by the benchmark job-shop problem, compared with other algorithms it shows the rapidly convergence of the GSPSO. And the hybrid algorithm was used to solve some other job shop scheduling problems too, the simulations give the result that the hybrid algorithm has a good performance in solving the JSP.Lastly, through the research on dynamic job shop scheduling problem, use the rolling window technology and event driven scheduling strategy to analyze the dynamic JSP and take variety dynamic events in to account. Then use the GSPSO algorithm to solve the dynamic job shop scheduling problem(DJSP) and compared with ant colony algorithm solve the same problem, the simulation results shows the hybrid PSO algorithm can make a good performance in dealing with the uncertain dynamic events.