Job-shop Shop Scheduling Problem Based On Genetic Algorithm

How to improve the productivity under the Job-Shop manufacturing mode has always been an issue of concern to the people. Because of its complicated calculation, dynamic multi-restriction, Job-Shop scheduling problem (JSP) has been proved as NP-hard (Non-deterministic Polynomial-hard) problem, and many intelligent computation methods are introduced into this field in recent years. Among these, genetic algorithm (GA) is one of the most popular methods getting an increasing attention by domestic and overseas experts recently. But slow convergence and low precision still exist in these applications and research. To improve the performance of the existing GA for JSP and speed up searching for the optimal scheduling solution, based on the background of a mould manufacturing shop, this dissertation studied JSP using an improved GA.Three parts were contained:1. Chapter 1(basic theory), introducing the importance of the subject, the status of present worldwide research in this field.2. Chapter 2(project background), describing and analyzing the environment, status, and characteristics of production, the process of plan and control, etc.3. Chapter 3&4(algorithm analysis), based on operation-based representation, designing keeping-fragments-reverse-crossover, which was applied to JSP with fuzzy processing time and duedate, then classical and realistic numeric examples were given which validated the effectiveness and efficiency of the proposed method.The results showed that: this improved algorithm not only ensured validity and diversification of the evolving descendants, but also improved precision of optimal schedule.