Research And Implementation Based On Hybrid Ant Colony Algorithms For Job-Shop Scheduling Problems

Job-Shop Problem is the concentrate model of many actual Job-Shop schedule problems, and it is a typical Nondeterministic Polynomial-time hard problem, so it is reported that it can't get the best outcome through polynomial. Ant colony algorithm (ACA), which has been widely noticed during recent years and used to solove combinatorial optimization problems by more and more people, is a kind of optimization algorithm. In order to solve the Job-Shop problem better, some good algorithms are combined. In this paper, a Hybrid Ant Colony Algorithm Based on Neighborhood Serach and an Adaptive Genetic Algorithm and Ant Colony Algorithm (AGA-ACA) are respectively proposed for JSP.To overcome the disadvantages of prematurity and slow convergence in ant colony algorithm, a hybrid ant colony algorithm based on neighborhood search is designed. A variable neighborhood search mutation operator which has not only the usual variability, but also the local search function with steps 2 and 3 is applied to optimize search results. The simulation results of some classical type LA problems indicate that the algorithm has a faster speed for optimum value searching and a better global optimal searching capability, and at the same time, the diversification of soluions is increased, and the probability falling into the local extreme values can be reduced.Based on analyising adaptive genetic algorithm and ant colony algorithm, Job-Shop problem is soloved by combining the two ones. Firstly, using adaptive genetic algorithm to generate some excellent chromosome, converting them into initial pheromone distribution for ant colony algorithm, and then using ant colony algorithm to search for the best answer of JSP. Then determining the best combination time of adaptive genetic algorithm and ant colony algorithm to avoid early or late termination of the adaptive genetic algorithm. Finally, the results in soloving eleven classical scheduling problems indicate that AGA-ACA has better whole onstringency and utilizes the advantages of the two algorithms and overcomes their disadvantages, and it is discovered that the bigger the problem is concerned, the better the algorithm performs.