Application And Research Of Improved Genetic Algorithm For Job Shop Optimization Scheduling

Job-shop scheduling problem is one of the well-known machine scheduling, and also the most difficult combinatorial optimization problems. It plays a significant role in production systems and engineering applications. The development of accurate and effective scheduling algorithm has come into the focus of research in recent years.This dissertation firstly presents a detailed description of deterministic job-shop scheduling problem and then studies some uncertain scheduling problems arising in production due to a variety of random factors, with consideration of actual production processes. In this study, uncertain processing time and due date are denoted by a triangular fuzzy number and a trapezoid fuzzy number respectively, and at the same time factors like fuzzy processing time and fuzzy due date are considered. As a result, the model of the fuzzy job-shop scheduling problem is proposed, and the maximum average satisfaction is taken as the optimization objective.In recent years, local search method has been widely applied to job-shop scheduling problem. This dissertation is intended to make deep investigation into genetic algorithm. It employs two kinds of methods to promote the local search function of traditional genetic algorithm, to tackle such problems as premature convergence and poor local search function and in turn to better optimization quality and search efficiency.The first algorithm proposed, based upon the principle of mutually-guided evolution of two populations, not only increases the diversity of the population, but also improves the ability of resisting pre-maturity; at the same time, it uses the best and worst chromosome to crossover each other to avoid local optimum. And then for the operation-based representation, a new crossover operator is designed for avoiding unfeasible solution resulting from cross-operation. Application of the improved genetic algorithm in deterministic job-shop scheduling problems, and the simulation results of the classic example have proved the feasibility and effectiveness of the algorithm.The second algorithm proposed combines genetic algorithm with simulated annealing algorithm. Simulated annealing algorithm can probably circumvent the local optimal solution. The algorithm uses simulated annealing to bear the selection pressure of genetic algorithm, and uses the good global optimum characteristics of the genetic algorithm. The paper proposes a global optimal of the hybrid optimization algorithm. The simulations of fuzzy job-shop scheduling show the effectiveness and practicality of the hybrid algorithm.