A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem

Abstract

Abstract As an important branch of production scheduling, flexible job-shop scheduling problem (FJSP) is difficult to solve and is proven to be NP-hard. Many intelligent algorithms have been proposed to solve FJSP, but their key parameters cannot be dynamically adjusted effectively during the calculation process, which causes the solution efficiency and quality not being able to meet the production requirements. Therefore, a self-learning genetic algorithm (SLGA) is proposed in this paper, in which genetic algorithm (GA) is adopted as the basic optimization method and its key parameters are intelligently adjusted based on reinforcement learning (RL). Firstly, the self-learning model is analyzed and constructed in SLGA, SARSA algorithm and Q-Learning algorithm are applied as the learning methods at initial and later stages of optimization, respectively, and the conversion condition is designed. Secondly, the state determination method and reward method are designed for RL in GA environment. Finally, the learning effect and performance of SLGA in solving FJSP are compared with other algorithms using two groups of benchmark data instances with different scales. Experiment results show that the proposed SLGA significantly outperforms its competitors in solving FJSP.