Q-learning Based Tree Structure Encoding Discrete Symbiotic Organisms Search Algorithm to Solve Shop Scheduling Problem

Based on the practical scheduling situation, this paper considers the effect of learning effect on scheduling and the learning threshold of jobs, and designs a learning effect no-wait scheduling model based on position truncation. A Q-learning based tree structure encoded discrete symbiotic organism search (QDTSEDSOS) algorithm is proposed for the scheduling problem, which first transforms feasible solutions into a tree structure more suitable for representing complex problems to improve search efficiency and expand solution space. Secondly, in the mutualism phase, the "advantageous block" of jobs is preserved to improve global optimization ability. In addition, the population is divided into superior and inferior subpopulations based on the distribution characteristics of particles. The superior subpopulation proposes three neighborhood search strategies to deal with the "large valley" phenomenon and uses Q-learning to utilize the results and information of historical search in order to guide the current search process. The solution space is searched more efficiently by selecting operators based on prior experience, while the inferior subgroup performs a parasitic strategy based on backward connectivity to purposely explore promising individuals. Experimental results on the Taillard benchmark set show that QDTSEDSOS is feasible and effective in solving the learning effect-based no-wait flow shop scheduling problem.