Abstract:
This paper presents a genetic algorithm for a Job Shop Scheduling problem. Variable-length chromosomes (strings) and their genes (parameters) have been used for encoding the problem. The crossover operation exchanges partial chromosomes (partial routes) at position ally independent crossing sites and the mutation operation maintains the genetic diversity of the population. The proposed algorithm can cure all the infeasible chromosomes with a simple repair function. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. This paper also develops a population-sizing equation that facilitates a solution with desired quality. The equation has been further enhanced and generalized. The equation relates the size of the population, the quality of solution, and other parameters of the proposed algorithm. Computer simulations show that the proposed algorithm exhibits a much better quality of solution (browse optimality) and a much higher rate of convergence than other algorithms. The results are relatively independent of problem type. Furthermore, simulation studies emphasize the usefulness of the population-sizing equation.
