A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. (November 2020)

• Record Type: Journal Article
• Authors: Chen, Ronghua; Yang, Bo; Li, Shi; Wang, Shilong
• Is Part Of: Computers & industrial engineering. Volume 149(2020)
• Publication Date: 2020-11
• Subjects: Flexible job-shop scheduling problem (FJSP) -- Self-learning genetic algorithm (SLGA) -- Genetic algorithm (GA) -- Reinforcement learning (RL); Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106778
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A self-learning GA (SLGA) which combines both SARSA and Q-learning with GA is first proposed to solve FJSP. The combined model of SLGA is constructed according to the features of GA and RL. SARSA algorithm and Q-learning algorithm of RL are combined, which constitute the main part of learning module in SLGA. The components of RL are designed, including the state of GA environment, action of parameters adjustment, and reward method. The mixed strategy of SARSA algorithm and Q-learning algorithm improve the efficiency of SLGA for FJSP. 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.