Hybrid Genetic Algorithm for Solving Job-Shop Scheduling Problem

The job-shop scheduling problem (JSSP) is a well-known difficult combinatorial optimization problem. Many algorithms have been proposed for solving JSSP in the last few decades, including algorithms based on evolutionary techniques. However, there is room for improvement in solving medium to large scale problems effectively. In this paper, we present a hybrid genetic algorithm (HGA) that includes a heuristic job ordering with a genetic algorithm. We apply HGA to a number of benchmark problems. It is found that the algorithm is able to improve the solution obtained by traditional genetic algorithm.