Ant Colony Algorithm And Its Application Research In Shop Scheduling Problem

Ant Colony Algorithm(ACA) is a new type of heuristic optimization algorithm which bases positive feedback mechanism with pheromone.Comparing with the traditional methods,ACA has two major characteristics(distributed computing and positive feedback).ACA has a wide range of application in combinatorial optimization and it also has achieved good results in these fields. ACA does well in solving large-scale and combinatorial optimization problems,if we use ACA to solve shop scheduling problem,on one hand,we can take full use of the advantage of it's global search capability,and raise the probability of search for the global optimal solution in larger solutions space;On the other hand,we can use the advantages to optimize solving time and improve the efficiency.Based on referring to other literatures of home and abroad,this thesis has a depth research and experimental analysis in basic theory and methods of ACA.The main contents are as follows:The basic theory and application of ACA are systematically and thoroughly introduced in this thesis.By analyzing the classical methods,the thesis points out their special applying areas and shortcomings.Some improved algorithms are introduced.A kind of general improvement in ACA is presented in this thesis.Simulation tests with standard TSP data show that the improved algorithm is feasible and efficiency.The basic theory and application of Job-Shop Scheduling Problem(JSSP) and Flow-Shop Scheduling Problem(FSSP) are systematically and thoroughly introduced in this thesis.Finally,this thesis shows the superiority of improved ACA by simulation tests with general data,and comparing the test results with other algorithms.The results show it has achieved good results in operating efficiency and solution quality.