Improved Intelligent Algorithms for Solving Job-shop Scheduling Problems

Job-shop Scheduling Problem (JSP) deals with the sequencing operations of a set of jobs on a set of machines with minimum cost. JSP is one of extremely hard problems because it requires very large combinatorial search space considering the precedence constraint between machines. In this paper for solving JSP problems three new and modified intelligent methods are studied. For solving JSP problems, first Genetic Algorithm (GA) method with new crossover and mutation operators is introduced, the crossover operator is based on position of chromosome elements (Position Based Crossover) and Swap mutation is applied to GA. Then Tabu Search algorithm (TS) that is equipped with short and long term memories is presented as a second approach and modified Very Fast Simulated Annealing (VFSA) with a correction in neighbor generation is the third strategy. Finally the capabilities and Performances of the three proposed methods are adopted to prove their efficiencies based on a Job shop benchmark problem. The numerical examples show that the mentioned modified methods have better optimality performances than conventional (unmodified) methods and among them the GA with new operators is the best strategy for solving JSP problem with minimum value of cost function and simulation time.

Keywords:

Job-shop Scheduling Problem , Intelligent methods , Genetic Algorithm , Tabu Search , Very Fast Simulated Annealing