A Genetic algorithm approach for solving a dynamic job shop scheduling problem

Abstract

Job Shop Scheduling Problem (JSSP) is a non-deterministic, polynomial-time (NP) hard combinatorial optimization problem. It 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. Indeed, it is not possible to obtain an optimal solution when the number of jobs and the machines increase. Numerous researches have been carried out studying many approaches to solve this problem. In this research, Genetic Algorithm (GA) which is another widely used nonlinear optimization technique has been used to propose an algorithm. A novel chromosome representation (indirect) with an encoding based on time is introduced in this research. The proposed solution is capable of handling multiple disruptions which are new job arrivals, sudden machine breakdown and unplanned machine maintenance. The proposed algorithm is tested against benchmark problems in Static JSSP and some developed scenarios to simulate Dynamic JSSP conditions. The results show that the proposed algorithm generates near optimal schedules for Static JSSP. This algorithm can be used as a planning tool by the planners. It is possible to simulate almost all the real-life scenarios using this algorithm and schedules can be generated satisfying the required conditions. The algorithm can be developed further by employing a local search algorithm which produced more precious, optimal schedules.