ANALYSIS OF SELECTION SCHEMES FOR SOLVING JOB SHOP SCHEDULING PROBLEM USING GENETIC ALGORITHM

A.Ranjini, B.S.E.Zoraida

Abstract: Scheduling problems have the standard consideration in the field of manufacturing. Among the various types of scheduling problems, the job shop scheduling problem is one of the most interesting NP-hard problems. As the job shop scheduling is an optimization problem, Genetic algorithm was selected to solve it In this study. Selection scheme is one of the important operators of Genetic algorithm. The choice of selection method to be applied for solving problems has a wide role in the Genetic algorithm process. The speed of convergence towards the optimum solution for the chosen problem is largely determined by the selection mechanism used in the Genetic algorithm. Depending upon the selection scheme applied, the population fitness over the successive generations could be improved. There are various type of selection schemes in genetic algorithm are available, where each selection scheme has its own feasibility for solving a particular problem. In this study, the selection schemes namely Stochastic Universal Sampling (SUS), Roulette Wheel Selection (RWS), Rank Based Roulette Wheel Selection (RRWS) and Binary Tournament Selection (BTS) were chosen for implementation. The characteristics of chosen selection mechanisms of Genetic algorithm for solving the job shop scheduling problem were analyzed. The Genetic algorithm with four different selection schemes is tested on instances of 7 benchmark problems of different size. The result shows that the each of the four selection schemes of Genetic algorithm have been successfully applied to the job shop scheduling problems efficiently and the performance of Stochastic Universal Sampling selection method is better than all other four selection schemes.

Keywords: Genetic Algorithm, Makespan, Selection schemes

DOI: https://doi.org/10.15623/ijret.2013.0211116