Multistage-based genetic algorithm for flexible job-shop scheduling problem

Flexible job shop scheduling problem (fJSP) is an extension of the traditional job shop scheduling problem (JSP), which provides a closer approximation to real scheduling problems. In this paper, a multistage-based genetic algorithm with bottleneck shifting is developed for the fJSP problem. The genetic algorithm uses two vectors to represent each solution candidate of the fJSP problem. Phenotype-based crossover and mutation operators are proposed to adapt to the special chromosome structures and the characteristics of the problem. The bottleneck shifting works over two kinds of effective neighborhood, which use interchange of operation sequences and assignment of new machines for operations on the critical path. In order to strengthen the search ability, the neighborhood structure can be adjusted dynamically in the local search procedure. The performance of the proposed method is validated by numerical experiments on three representative problems.