A LOCAL SEARCH GENETIC ALGORITHM FOR THE JOB SHOP SCHEDULING PROBLEM

Scheduling of job-shop is very important in the fields of production management and combinatorial optimization. This paper proposes a method for solving general job-shop scheduling problems based on hybridized algorithm that combines a genetic algorithm with a taboo search in two distinct phases research. In the first phase an operations-coded genetic algorithm is used to find an elite population. The set of elite solutions obtained from the first phase acts as the initial population of the second phase, in which a taboo search algorithm is applied to each one of them to intensify the research. The effectiveness of this algorithm is confirmed by applying it to a set of benchmarks with the makespan as the objective function. The results obtained show that local search applied at the final population can improve greatly the research.