Dynamic job shop scheduling with alternative routes based on genetic algorithm

In this paper, we propose Genetic Algorithms (GAs) for the Dynamic Job-Shop Scheduling Problem (DJSP) with alternative routes, which is an extension case of the classical job-shop scheduling problem. Although the alternative machines add more complexity to the problem, it simulates real world job shop production scheduling requirements more effectively. GAs have been widely used for scheduling problems but the quality of the solution mainly depends on the design of the solution procedure. Therefore, different strategies are presented and applied to form the initial population. A single individual crossover operator is applied to produce a new chromosome and a mutation operator is presented to generate alternative routes as well as to maintain the diversity of the population. The model was validated by using different instances taken from the literature. The result obtained from the computational study has shown that the proposed approach is a feasible and effective solution to the DJSP.