Research On Improved Ant Colony Algorithm In Job-Shop Scheduling Application

Job-shop scheduling problem (JSP) is the simplified model of the actual production scheduling problem. It's meaningful that studying the JSP of production could control the actual product cost, improve equipment utilization, etc. JSP is a combinatorial optimization problem which belonging to NP-hard problems. Ant colony optimization algorithm (ACO), a new kind of optimization algorithm rising in recent years, has been used in solving combinatorial optimization problems by more and more people.This paper analyzed the characteristics of JSP, and did a comprehensive overview to the optimal method of the scheduling problems; introduced the origin, the principle and the basic model of the ACO, analyzed its strengths and weaknesses, and overviewed of its research status; and finally proposed an improved ant colony algorithm applying to solve the job shop scheduling problem.The innovations in this paper are listing as following. We improved the algorithm to deal with the shortcomings of ACO such as slow convergence and vulnerable to local optimization. The improvements are adding local adjustment factors to improve the quality of the constructed solutions by ants after using ACO to build the solution of JSP and before updating the pheromones at each iteration. Local adjustment factors include fine-tuning the operations order of the block on the critical path and cross-breeding the solutions to generate new ones. Through analyzing benchmark of JSP and comparing with other algorithms, we verified the excellent performance of the algorithm.