Adaptive multimeme algorithm for flexible job shop scheduling problem

In this paper, we propose an adaptive multimeme algorithm (AMMA) to address the flexible job shop scheduling problem (FJSP) with the objective to minimize the makespan. The search operator is modeled as a synergy of genetic and memetic mechanisms through integrating a stochastic variation and a local search procedure into a composite operator for each individual. Three effective local search methods, featured with distinctive neighborhood structures, are adopted. The stochastic variations include crossover operators and mutation operators crafted for the FJSP. A bandit based operator selection strategy is applied to select operators for individuals adaptively. So as to better suit the current stage of search process, a sliding window is used to record the recent performance achieved by the operators, thereby guiding the subsequent selection of operations. The proposed AMMA is tested on several well-known sets of benchmark problems and is compared with some existing state-of-the-art algorithms. The results show that AMMA achieves satisfactory performance in solving these different sets of problems. Furthermore, a further in-depth analysis is presented to elucidate the improved search performance generated by the adaptive mechanism.