A Comparison of Genetic Algorithms for the Dynamic Job Shop Scheduling Problem

摘要

The majority of the research using evolutionary algorithms for the Job Shop Scheduling Problem (JSSP) has studied only the static JSSP. Few evolutionary algorithms have been applied to the Dynamic Job Shop Scheduling Problem (DJSSP) which is more similar to real-world applications. We implement a hybrid genetic algorithm for solving the dynamic job shop problem. A direct chromosome representation, containing the schedule itself, is used. Order-based operators are combined with techniques that produce active and non-delay schedules. We refer to our algorithm as the Order-Based Giffler and Thompson (OBGT) Genetic Algorithm. OBGT is compared in terms of the quality of solutions against published solutions for benchmark problems. OBGT consistently finds better solutions on larger problems compared to several other evolutionary algorithms, including Temporal Horizon GA (THX) and Heuristically guided GA (HGA).