The Study Of Planning And Scheduling Based On The Genetic Algorithms

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. In the aspect of engineering the paper designs a standard genetic algorithm to solve Job-shop scheduling problem; A new approach is developed combining the genetic algorithm with a bi-directional approach. The critical jobs must be scheduled by the backward algorithm, which ensures the necessary resources allocated to the most important jobs; then the remaining jobs are scheduled with a forward algorithm, which tends to allocate resources where the previous scheduling pass did not use them. The genetic algorithm derives the optimal operations precedence to schedule the operations in the bi-directional scheduling approach. An example of scheduling is given, which proves this method is feasible and efficient.