GA with Priority Rules for Solving Job-Shop Scheduling Problems

Abstract

The Job-Shop Scheduling Problem (JSSP) is considered as one of the difficult combinatorial optimization problems and treated as a member of NP-complete problem class. In this paper, we consider JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. First, we develop a genetic algorithm (GA) based approach for solving JSSPs. We then introduce a number of priority rules such as partial reordering, gap reduction and restricted swapping to improve the performance of the GA. We run the GA incorporating these rules in a number of different ways. We solve 40 benchmark problems and compared their results with that of a number of well-known algorithms. We obtain optimal solutions for 27 problems, and the overall performance of our algorithms is quite encouraging.