Improved Genetic Algorithm Approach Based on New Virtual Crossover Operators for Dynamic Job Shop Scheduling

Abstract

The realtime manufacturing system is subject to different kinds of disruptions such as new job arrivals, machine breakdowns, and jobs cancellation. These different disruptions affect the original schedule that should be updated to maintain the system's performance. An effective re-scheduling is required in this situation to make better utilization of the system resources. This paper studies the dynamic job shop scheduling problem. The problem is known as strongly NP Hard optimization problem where new jobs are unconditionally arrived at the system. Hence, to deal with system changes and performing hard tasks scheduling, we propose an evolutionary genetic algorithm based on virtual crossover operators. Experimental results are compared with state-of-the-art heuristics and metaheuristics dedicated for evaluating large scale instances. Simulation results show the efficiency of the proposed virtual crossover operators integrated into the genetic algorithm approach.

Keywords

• Dynamic job shop scheduling problem
• genetic algorithm
• crossover operators
• makespan
• dispatching rules
• metaheuristics