Application Of Genetic Algorithm In The Job Shop Scheduling Problem

The study of production scheduling problem is helpful to optimize the processing line of products, improve the utilization rate of equipment, reduce the waiting time of the procedure, which can reduce the production cost of enterprises, make the right decision to provide a reference for enterprise managers. As the job shop scheduling problem of production scheduling problem research began in the fifty’s of last century, Johnson, which were studied for two sets of machine production scheduling and op-timization algorithm is proposed to solve the special problem of job shop scheduling part.With the expansion of the scale of the problem, the complexity of the problem increases exponentially, so the traditional branch and bound method, dynamic pro-gramming method is not suitable for solving it. In recent years, simulated annealing and tabu search, genetic algorithm and so on, provides an opportunity to solve this problem. Since Davis in 1985by using the genetic algorithm to solve the scheduling problem success. Genetic algorithm because of its intelligence, global the scholars have been a large number of used it in production scheduling field.Job shop scheduling is to solve how to n workpiece in mmachine problems. The known specific processing sequence, each part of each working procedure processing time and contained in the process required for each job, to meet the appropriate of the constraints, the goal is to determine the processing order of all parts of each machine, in order to ensure an optimal performance index, are generally required to achieve the shortest processing time.By using genetic algorithm on job shop scheduling, according to the characteristics of the job shop scheduling problem, choose a suitable and relatively simple way of coding, showing the unique nature of the job shop scheduling problem, the chromosome number in each can be workpiece number and determined the process of the workpiece. According to the characteristics of the proposed coding method, crossover operator and mutation operator does not destroy the stability, so as to ensure the work is feasible solution of job shop scheduling problem. The fitness function of the reciprocal of the use of time, the objective function to choose the shortest processing time, and the optimal individual in each generation preserved. After the procedure, application ft - 06and ft - 10 standard problem, used to test the feasibility of the algorithm, to prove the validity of the algorithm. Finally, analysis problems and introduces various problems in job-shop scheduling problems that may be encountered in actual existence.