基于Sarsa的动态蜂群算法求解作业车间调度问题

A Dynamic Artificial Bee Colony Algorithm Based on Sarsa for Job-Shop Scheduling Problem

针对作业车间调度问题,提出了一种基于Sarsa算法的动态人工蜂群算法。首先,提出了探索因子和开发因子两个参数,分别量化人工蜂群算法的探索能力和开发能力,并在此基础上改进了它的解的更新公式;其次,根据种群的状态,实时地使用Sarsa自适应地调整探索因子和开发因子的值,使得人工蜂群算法可以在需要探索时探索新的解,需要开发时,开发现有的解,从而实现探索和开发之间的动态平衡;最后,使用11个不同规模的作业车间调度问题来验证所提算法的性能。通过对标准实例求解并与其它论文结果对比,证明了该改进算法的高效性。

A dynamic artificial bee colony algorithm based on Sarsa algorithm is proposed for job shop scheduling problem.First,two parameters,the exploration factor and the exploitation factor are proposed to quantify the exploration ability and exploitation ability of the artificial bee colony algorithm respectively,and on this basis,the updating formula of its solution is improved.Secondly,according to the state of the population,Sarsa is used to adaptively adjust the values of the exploration factor and the exploitation factor in real time,so that the artificial bee colony algorithm can explore new solutions when it needs to explore and exploit existing solutions when it needs to exploit,so as to achieve a dynamic balance between exploration and exploitation.Finally,11 job shop scheduling problems of different scales are used to verify the performance of the proposed algorithm.Finally,by solving some standard cases and comparing with the results of other papers,the efficiency of the improved algorithm is proved.