Flexible Job Shop Scheduling Based on Multi-population Genetic-Variable Neighborhood Search Algorithm

An optimized algorithm according to a variety of population genetic-variable neighborhood search was proposed to solve the problem of flexible job shop scheduling. The new algorithm aims at minimizing the makespan, obtaining the smallest machine maximum load and the smallest total machine minimum loads. At the same time, the new algorithm improves the inherent defects of poor local search ability, premature convergence and longtime calculation in traditional genetic algorithm. The algorithm takes advantages of the strong global search ability of genetic algorithms, rapid and efficient local optimization of variable neighborhood search and diversity of multi-population. Firstly, this algorithm generates a plurality of initial populations based on two-layer coding of processes and machine randomly. Then it looks for non-inferior solutions of every population and introduces the strategy of elitist preserving. After that, it forms an external memory database. Whereafter, in order to find an optimal or suboptimal solution and replace the relatively inferior solution in every population, the variable neighborhood search is used. Finally, this method is applied to a practical example, and compared with other classical algorithms to verify that if the multi-population genetic-variable neighborhood search algorithm is a feasible and effective optimization algorithm or not.