融合强化学习与变邻域搜索的柔性作业车间调度研究

Reinforcement Learning-based Variable Neighborhood Search Algorithm for Flexible Job Shop Problem

针对柔性作业车间调度问题,以完工时间最小化为目标,提出一种融合强化学习的变邻域搜索算法,提升算法求解性能。基于皮尔逊相关性分析,提炼出工序加工时长这一关键特征,设计一种优先考虑加工时长的邻域结构,精炼搜索空间。基于强化学习,设计算法进化状态集、关键参数动作集和奖励机制。提出改进的ε-贪婪策略来选择动作,随着ε取值的自适应变化,算法前期倾向于探索新解,后期注重利用邻域解,最终构建起算法状态与算法参数的关系,实现了算法参数的自适应选择。结果表明,所提算法利用强化学习动态调整算法参数,在解的寻优能力和稳定程度上更具优势。

To solve the flexible job shop problem with the objective of minimizing makespan,an improved reinforcement learning-based variable neighborhood search algorithm(IRLVNS) was proposed to promote the efficiency of solution procedure. Processing time which was a key impact factor,was extracted via Pearson's correlation analysis. A novel neighborhood structure was designed to refine the search space. On the basis of the strength of reinforcement learning,the evolution state was precisely designed along with the key parameter action set and the reward mechanism of the algorithm. An improved ε-greedy strategy was designed to select the action. As the value of ε changed,in the early stage the algorithm tended to explore new solutions,then exploited neighbor solutions in the late stage. The relationship between the algorithm state and its parameters was finally constructed to realize the adaptive selection of the algorithm parameters. Exhaustive computational experiments indicate that the algorithm(IRLVNS) proposed adjusts its parameters adaptively and therefore shows significant advantages in terms of near-optimality and robustness of solutions.