Study On Job-shop Scheduling Problem By Genetic Algorithm

The Production planning and scheduling system directly affect the efficiency and cost of enterprise.Effective plying and scheduling algorithms can improve benefit.But scheduling problem is combinatorial optimization problem, which belongs to NP problems and is difficult to solve by regular method,In recet years, some intelligent algorithms have been used for it such s GA(gente algnthm) and SA(simulated annealling).etc.The genetic algorithm is a search algorithm based on the mechanics of natural selection and natural genetics.It is widely used in many kinds of fields because of its less-dependency f optimization problem,simplicity robustness and implicit parallelism.Job-shop Scheduling Problem is a typical NP problems ,which is one of the hardest combinatorial optimization problem.In this paper,GA is applied to solve job-shop scheduling problem. Some jobs have been done in the following aspects:1. In the aspect of engineering the paper designs a standard genetic algorithm to solve Job-shop scheduling problern(JSSP);2. One improved genetic algorithms(diploid genetic algorithm) are applied in JSSP;3. The adaptive GA is used to solve JSSP and two improved Adaptive GAs are proposed;4. After doing above jobs,corresponding software is designed;5. Feasibility and efficiency of three kinds of genetic algorithms are compared and analyzed baseing on the results;6. The scheduling program of JSSP are designs.