Research And Application Of Genetic Algorithm For Job Shop Scheduling Problem

Job-shop scheduling problem (JSP) is typically NP-hard, which means that it is impossible to find the global optimum in polynomial complexity. JSP is one of the key problems in the production management. Good algorithms for this problem can promote productivity of enterprises. So this thesis can provide good results for both theory and practice. Consequently, the research and the development of advanced planning and scheduling has been an attractive subject in academic and industrial communities.This thesis gives a brief survey on the current development of job-shop scheduling models and solutions on the domestic and foreign research. Then we explain the description of genetic algorithm and analyze the encoding strategy, crossover operator and mutation operator of genetic algorithm on JSP. At the same time, we propose a new idle time shortening method for job-shop scheduling problem. This method has better performance by inserting it into a genetic algorithm for JSP.At the last section of this article, we studied how to using GA to the flexible job-shop scheduling problem (FJSP). FJSP is an extension of the classical Job-shop scheduling problem, which provides a closer approximation to real scheduling problems. According to the characteristics of the FJSP, we propose a new mutation operator based on critical operations. It improves the performance of the mutation by focusing on the critical path. A new genetic algorithm for FJSP is proposed. Finally, the results of the experiments indicate that the GA is effective.