一种求解等效并行机调度问题的改进遗传算法

针对预防性维修与工件到达时间的等效并行机调度问题,以最大完工时间的最小化为目标,设计了一种基于灾变机制的改进遗传算法。该算法采用随机与启发式混合方法生成初始种群,能以自适应交叉概率、变异概率以及灾变算子提高种群的多样性和算法的搜索能力,克服传统遗传算法的“早熟”问题。实验结果表明,与数学规划模型和传统遗传算法相比,该算法的求解效率有明显提高。

基于增强拓扑神经进化的等效并行机动态调度

针对工件动态到达、处理时间不确定且机器须要弹性预防维护的等效并行机调度问题,以平均流程时间最小化为目标,提出了基于强化学习的动态调度方法.将调度过程作为马尔可夫决策过程,通过定义状态空间、行为空间、奖励函数与适应度函数,提出基于增强拓扑神经进化(NEAT)算法的动态调度方法.设计三种规模问题的实例,将基于NEAT的方法与最短路径树(SPT)、先装先卸(FIFO)调度规则及基于深度Q网络(DQN)的方法进行比较,结果表明:基于NEAT的方法相比基于DQN的方法能够以更短的训练时间获得更优、更稳健的调度方案,相比SPT和FIFO调度规则能够获得更优的目标值,利用训练好的NEAT模型对随机生成的大规模问题实例的快速高质量求解结果表明,基于NEAT的调度方法具有更好的泛化性能.