JOB Shop Scheduling using Genetic Algorithm

Abstract

Scheduling is defined as the problem of allocation ofmachines over time to competing jobs. Job shop scheduling involves set of jobs to be processed on finite set of machines with minimum makespan.Job shop scheduling is a NP-complete problem of combinatorial optimization. Genetic Algorithm (GA) is a class of optimization algorithm problems which provides efficient and optimal solution.Genetic algorithm is well suited for solving production scheduling problems. Unlike heuristic methods, genetic algorithm operates on a population of solutions rather than a single solution. In production scheduling this population of solutions consist of many feasible solutions. Initial population of feasible schedules is generated randomly. This population goes through a set of genetic operators such as crossover and mutation to produce new schedules. At each
generation the fitness of the schedule is evaluated to decide whether it can be carried over to the next generation or should be replaced with a better solution.Other methods which can be applied to solve job shop problem converge to the local optima quickly. With genetic algorithm, convergence to local optima is reduced. The result obtained is compared with parameters such as number of generations and crossover rate. It is found that as the number of generations increases better results are achieved.