Research On Job Shop Scheduling Problem Based On Genetic Algorithm

Job Shop Scheduling Problem (JSSP), which characters as its complicated calculation, dynamic multi-restriction, and multi-objective, has been proved as NP-hard problem. Many intelligent computation methods such as simulated Anneal Algorithm, Genetic Algorithm, heuristic algorithm, are introduced into job shop scheduling problem in recent years. Genetic Algorithm is widely used in JSSP because of its less-dependency of optimization problem, simplicity, robustness and implicit parallelism, but it also has problem of slow convergence and low precision.Firstly, this paper explains the JSSP and its description and analyzes the encoding strategy, crossover operator and mutation operator of Genetic Algorithm on JSSP. At the same time Genetic operator's influence on solution precision has been isllustrated.Secondly, based on thorough study the operation-based representation, this paper designs a new crossover which is based on jobs and uses the algorithm to solve the job shop scheduling problem with a determination process period. Through the comparative simulations with position-based crossover, the new algorithm can get a better solution.At last, this paper studies the JSSP with fuzzy processing time and fuzzy duedate. In order to solve the fuzzy scheduling problem, we use a triangular fuzzy number to represent the fuzzy processing time and a semi trapezia fuzzy number to represent the fuzzy duedate, seek the scheduling that maximizes the minimum value of customer satisfaction and introduce the priority rule-based algorithm to solve the conflict of G&T algorithm. Our extensive simulation results show that the improved algorithm is prior to the formerly algorithm. The improved algorithm is also feasible and valid.