Parallel Genetic Algorithm For Job Shop Scheduling Problem

Job-shop scheduling plays a great role in the production activity of an enterprise, job-shop scheduling system is also a great part of CIMS or ERP. Production scheduling is at the middle layer in the CIMS system structure, which is the joint of control and management. On one hand, it will supply decisions for the enterprise; on the other hand, it will arrange production tasks and supervise the control layer. So the production scheduling is the key of the CIMS. JSSP is a typical NP-hard problem, so it attracts great attention from both the academia and industry. Therefore, the study of job shop schedule is of great theoretical and practical importance.So far there have been many research methods to deal with JSSP, such as branch-bound method and some heuristic procedures based on priority rules, but the difficulty and complexity of general JSSP makes it very hard for the conventional search-based methods to find an optimal solution in reasonable time. New techniques emerging from the field of artificial intelligence have been introduced to address these problems in recent years, such as simulated annealing, tabu search, artificial neural network and genetic algorithm , and so on .The Genetic Algorithm (GA) is a random search method imitating the rules of the organic world. The main distinguishing feature are as following: operating on the composition target, requesting no guide and function continuance; having conceal concurrence and splendid capability with the better situation as a whole; adopting approximately the guiding of the most splendid means of leading, being able to gain voluntarily and the searching room the direction optimizes, self-adopting the regulation direction of search, not needing certain regulation. The features of GA have been widely used applied in territories such as optimization, machine learning, treatment of signal, self-adoption control, artificial existence and so on.Parallel Genetic Algorithm (PGA) is one of the research focuses of GA from past 10 years, and has improved a lot both in theory and application. This paper use PGA to solve JSSP scheduling problem, and the main content is as following:(1) Introduce and analyze some aspects about Job-shop scheduling problem, such as description of the problem, expression of the model, features and main research methods on JSSP. This paper divide all the methods into two classification, optimization method and heuristic procedures;(2)Introduce the Simple Genetic Algorithm as the foundation of PGA, such as following aspects: SGA's origin, background about biology, encoding methods, function, basic genetic operation(selection,crossover,mutation), and the regulation about the initialization of the basic parameters;(3)Introduce and analyze Parallel Genetic Algorithm, classification and status quo on research, transferring methods of CPGA, synchronous and asynchronic;(4)Introduce detailedly the new algorithm of CPGA aim at the features of the JSSP, include encoding methods, genetic operations, transferring methods. At last, implement the emulational experiment on the two typical examples of JSSP, FT6×6,LA01. The result prove that the new algorithm is better than the general GA.