Study Of Job Shop Scheduling Problem Based On Genetic Algorithm

Job Shop Scheduling Problem (JSP) is a typical combinatorial optimization problem that has interested researchers for several decades. In an environment of global competition, the success of a manufacturing corporation is directly related to the optimization level of its processes in general, in particular, to how it plans and executes production. In this context, the jobshop scheduling is one of the key activities for success. Unfortunately, the dynamics, uncertainty and effort demanded for the creation of a scheduler grows rapidly as the production scenario increases, especially when resources are limited. Due to such complexity, application of a pure mathematical optimization approach to determine an optimal solution may not be efficient in practice, thus simple heuristics algorithms are preferred.Genetic algorithms (GAs) have been widely applied to many scheduling problems, and demonstrated their robustness in finding global or very strong local optimal. However, different problems usually require a different chromosome specially designed to present the solution. In addition, different operators will influence its performance. This thesis presents the development and use of GA to jobshop scheduling problem. The developed GA was applied to two manufacturing scenarios, jobshop scheduling and parallel machines scheduling, and the most important parameters for the configuration of the GA were identified.In this paper, the basic theory of genetic algorithm and some design details were analyzed firstly, including structure of the genetic algorithm, and the objective fitness function , the set of possible individual selection techniques, and the adjustment values for the crossover and mutation operators, and et al.Then a simple GA was applied to the classical jobshop scheduling problem, the encoding of the chromosome is introduced. According to the chromosome structure, the crossover and mutation mechanisms and some operators are specially designed to prevent pre-maturity and saturation of the solution pool. Simulations have been done to testify the feasibility and effectiveness of the GA and to reveal some laws of genetic algorithm design.The GA, as well as its objective fitness function, and its adjustment values for the crossover and mutation operators, was further designed for solving the flexible scheduling problem. A modified GA with immune operator based on vector group is presented. An immune operator is adopted and studied in order to improve the quality of the population. To testify the optimization reliability, the proposed GA has been simulated on 10×4, 15×5, 15×4 benchmark problem. Simulation results indicate the satisfactory performance of the proposed GA.