New Approach to Solve Dynamic Job Shop Scheduling Problem Using Genetic Algorithm

摘要

Job Shop Scheduling Problem (JSSP) is one of the most common problems in manufacturing due to its widespread application and the usability across the manufacturing industry. Due to the vast solution space the JSSP problem deals with, it is impossible to apply brute force search techniques to obtain an optimal solution. In this research, Genetic Algorithm (GA) approach, which is another widely used nonlinear optimization technique, has been used to propose a solution using a novel chromosome representation which makes seeking solutions for the Dynamic JSSP more efficient. Due to operation order criteria of the jobs and the machine allocation requirement on machines, generating solutions for JSSP needs an extra effort to eliminate infeasible solutions. Due to level of the complexity with added constraints, there is a high tendency to get more infeasible solutions than feasible solutions. This results in consuming a lot of computing resources to correct such a conventional order-based chromosome representation. Due to this, a new representation is proposed in this paper. It is found that the proposed new chromosome representation approach makes it possible to model such dynamic behaviours of schedules without compromising the performances of GA.