The Application In Job Shop Sheduling Problem Based On Genetic Algorithm And Ant Colony Optimization Algorithm

With the increasing keen market competition,each enterprise looks for better solutions to production and operation management aiming at improve the core competitive advantage.The key to the management of production and operation management is to achieve the optimal solutions.Therefore,the study of Job Shop Schedule problem is the great significance.Job Shop Problem is to solve the problem that making prearrange is optimization by assigning resources to finish different manufacture tasks according to time early or late. Job Shop Problem is the concentrate model of many actual job shop shedule problems, and it is a typical Nondeterministic Polynomial-time hard problem. The problem has many complex characteristics, such as constraints, nonlinearity, uncertainty and large scale, so it is reported that it can't get the best outcome through polynomial.In recent years, meta-heuristics algorithm and heuristics algorithm are two kinds of algorithm for Job Shop Problem. However, they are all have shortages in different facet: Although meta-heuristics algorithm spends long runtime in getting better answer, the answer is still not stable; heuristics algorithm can get strong life-force answer in much shorter time,but there is rare better answer.In order to solve the Job Shop Problem betterly,we combine some algorithms which is good at in solving some problems.The genetic algorithem has the ability of global searching qucikly and randomly,but it is inadequate in feeding back system information.It always makes a lot of redundancy account while it gets some degree,which makes the efficiency of solving problem falling.Ant colony optimization algorithm gets the best route by cumulating information and updating the information on the path,it has the distributed and collateral ability in global searching,but the speed of it becomes slowly because the information is pinch at first.In this thesis, aim at strong point of genetic algorithm and Ant colony optimization algorithm, we proposes to combine genetic algorithm with Ant colony optimization algorithm to solve Job Shop Problem.The idea of dynamic combining genetic algorithm with Ant colony optimization algorithm:At first using genetic algorithm gets some excellent populations quickly and roundly before the best point,which is the time that genetic algorithm and Ant colony optimization algorithm get together.Choose some good populations and translating them to the earlier information distribution of Ant colony optimization algorithm from the populations which is achieved by genetic algorithm.Using the Ant colony optimization algorithm to get the best answer of Job Shop Problem by the algorithm characteristics of positive feedback and high efficiency after the best point.Finally we make emulational experiment for some classic type FT problem and type LA problem of Job Shop Problem.The outcome idicates that GA-ACO has better constringency and better whole constringency. GA-ACO gets the best population and better constringency speed in less iterative number.