Flexible job shop scheduling problem solving based on genetic algorithm with chaotic local search

摘要

Flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem, and provides a closer approximation to real world scheduling situations. This paper present a hybrid genetic algorithm (GA) combined with chaotic local search to solve the FJSP with MAKESPAN criterion. A small percentage of elitist individuals are introduced into the initial population to fasten GA's convergence speed, efficient crossover and mutation operators are adopted to avoid infeasible solutions and to hasten the emergency of optimum solution. During the local search process, Logistic chaotic sequence is adopted to explore better neighborhood solutions around the best individual of the current generation. Representative flexible job shop scheduling benchmark problems are solved in order to test the effectiveness and efficiency of the proposed algorithm.