Genetic Algorithm-Ant Colony Algorithm In Job-Shop Scheduling Research

With the rapid development of market economy, the old production mode cannot satisfy the requirements of modern production, every enterprise has been improving production and operations management solutions in order to enhance their competitive advantage. In actual production process, enterprise needs reasonable production scheduling arrangements to enhance the production efficiency. So shop scheduling problem is of great theoretical and practical value, and thus people pay more and more attention to it. Shop scheduling problem is to solve how to allocate resources in correct time order to complete various production tasks in order to reach the intended objective optimization. Job-Shop scheduling problem is a simplified model of many practical shop scheduling problems, is a typical NP-hard problem.Based on genetic algorithm and ant colony algorithm, this paper designs a new genetic algorithm-ant colony algorithm for solving the Job-Shop scheduling problem. For Job-Shop scheduling problem character, in this paper we use the encoding method based on job number sequence and try to dynamically integrate the two algorithms to solve the Job-Shop scheduling problem. As the encoding method based on job number sequence is not suitable for cross-breeding, we design a new single breeding method, and in reproduction and variation operations, use the dynamic control mechanism and local search mechanism to avoid inefficient, useless breeding and variation, quickly generate good chromosomes; once genetic algorithm become redundant and inefficient, then transfer to ant colony algorithm immediately, choose the best chromosomes group and converts them to the initial distribution pheromone for ant colony algorithm, use ant colony algorithm's distributed, parallel, positive feedback ability to efficiently solve shop scheduling problem;when ant colony algorithm performance reduced, use algorithms callback strategy, transfer part of the current optimal values to initial population for genetic algorithm, use genetic algorithm to re-search in this optimal set;if the two algorithms can produce a new optimal solution in callback operation, the callback operation will not stop, until the two algorithms are completely degraded and have no progress, the whole algorithm will end and output the optimal solution. Algorithm callback strategy ensures that the genetic algorithm-ant colony can fully search in the solution space.Finally, GA-ACA is applied to realize a shop scheduling simulation system, the classic instance of Job-Shop problem is used to assess the efficiency of the algorithm, and the algorithm is applied to solve Job-Shop scheduling problem, results show that the convergence of GA-ACA is more efficient, faster and the new algorithm is practical and efficient in solving Job-Shop scheduling problem.