A Mixed Algorithm For The JOB-SHOP Problem

Job Shop Scheduling Problem(JSP) is one of the most difficult combinatorial optimization problems, which allocates resources in order to perform a number of tasks, such as tasks collocating and ordinal restriction. To realize modern manufacture and promote production efficiency, research on effective production scheduling methods and optimization techniques and its application are the fundamental and essential problems. As early as in the 1950's much research have been done and the main solving methods are heuristic algorithms, which based on priority, that's arranging operations from the special subsets of unordered operations.As the exact methods are only suitable for small scale problems and the constructive methods perform poorly and lack flexibilities as well. This dissertation proposes a Hybrid Algorithm to solve JSP. The main research work is listed as follows: Firstly, the dissertation reviews historical developments on JSP domestically and internationally, introduces existing methods solving JSP. Secondly, based on the description of basic concepts, theory and fundamental procedure, the dissertation puts forward the hybrid GA which combines Tabu Search (TS) and GA and Ant Colony when considering the disadvantages of the standard GA on JSP (e.g. pre-mature and low convergence speed). Finally, analyzed the excellence and flaws of genetic algorithm and tabu search algorithms. Genetic algorithm can find the global optimization with the problem, but the ability of local search weak, need more time to Job-Shop system. Tabu search algorithm convergence fast, the ability of local search strong. But its astringency is concerned with initial value. Ant colony algorithm (ACA for short) is proposed for Job-shop scheduling problem. A probability priority is introduced for the initial distribution of ants. Moreover, quality and robustness of solutions are improved by the nature of feedback and parallel paradigm of ACA to remain the virtues and weaken the flaws of Genetic Algorithm and Tabu Search, the Genetic/Tabu Search Mixture Algorithm for reactive optimization in Job-Shop problem was presented. By repetitious test, discovering the optimization result gained by directly selected the classic solution of Genetic algorithms as the original solution of tabu search almost equal the optimization result gained by using every unit of the finally era as the original solution of tabu search, but the time was consumedly shorten, so This algorithm firstly uses genetic algorithms to get the initial value of tabu search, the nuses tabu search algorithms to get the optimal solution. As the Ant Colony Algorithm for hybrid Genetic Algorithm with random rapid global search capability, but use of the feedback was powerless to do anything, to solve a range of inaction are often a great deal of redundancy iteration, and exact solutions of low efficiency, Ant Colony Algorithm through pheromones, and the cumulative update on the convergence of the optimal path, with a distributed parallel global search capability, but the initial lack of pheromones, solve slowly, Genetic Algorithm and Ant Colony algorithms are mixed, and integration algorithm using genetic algorithms to generate information distribution, use of the Ant Algorithm for exact solutions, complement each other.Finally, by testing the standard examples the announced makes pans are obtained, which can prove the new algorithm's better performance on JSP.