基于自适应混合粒子群算法的流水车间调度问题研究.pdf

摘要

摘要

生产调度问题，作为企业生产管理的核心内容之一，研究和开发科学且高效的调

度策略，对于提升企业的生产管理效率和整体生产效能有着显著的推动作用。流水车

间调度问题（FlowShopScheduling,FSP）属于生产调度问题中的一种，普遍被认为

是一种难以解决的组合优化难题。因此，如何寻求更有效的解决策略，一直是智能优

化领域众多专家学者研究的热点。本文通过对基本粒子群算法进行改进，分别提出解

决置换流水车间调度问题(PermutationFlowShopSchedulingProblem,PFSP)和混合流

水车间调度问题(HybridFlowShopSchedulingProblem,HFSP)的自适应混合粒子群算

法(Self-adaptiveHybridParticleSwarmOptimization,SHPSO)，并在对应调度问题的测

试集上验证所提改进算法的有效性，其优化思想和方法可推广应用于其他类型的调度

问题，包括但不限于生产调度、资源分配等方面。本文的具体研究工作如下：

1.针对基本粒子群算法，设计了一种基于Q学习的自适应参数更新策略。本文对

种群多样性、平均适应度和个体全局最优适应度按比例加权设计Q学习的状态集，

根据基本粒子群算法参数特性设计动作集。利用Q学习算法在不同状态下控制粒子

选择不同的动作，实现对解空间进行不同范围的搜索，平衡算法的探索和开发，提高

粒子跳出局部最优解的概率。选取了10个测试函数验证算法的性能，实验结果表明

本文所提策略与其他自适应策略相比，寻优能力更强、更稳定，在高维问题上的表现

更好。基于上述策略，结合其他策略，成功设计了用于PFSP和HFSP的自适应混合

粒子群算法，下文分别介绍。

2.设计了针对最小化最大完工时间的置换流水车间调度问题的自适应混合粒子

群算法。本文结合自适应参数更新策略，引入了粒子停滞的判断方法，对陷入局部最

优的全局极值使用迭代贪婪算法进行局部搜索，并在迭代贪婪算法的解构和构建过程

中引入TBFF机制和Taillard加速算法进行改进，帮助粒子跳出局部最优。将所提算法

在Rec测试集上与粒子群算法的不同变种进行对比，实验结果说明加入的改进策略能

有效提高粒子群算法的求解质量和收敛能力。在Taillard测试集上的实验结果表明，

对比其他改进的4种粒子群算法，RPD分别降低了91.6%、89.7%、85.0%和83.2%，

avg

说明所提算法能极大程度改善易陷入局部最优的问题，在求解质量上具有明显优势。

I

重庆三峡学院硕士学位论文

3.设计了针对最小化最大完工时间的混合流水车间调度问题的自适应混合粒子

群算法。根据粒子群算法的特点，首先对粒子种群进行分层，再对分层后的普通粒子

和劣等粒子进行重新初始化和删减，对精英粒子进行解构和构建，最后对粒子种群的

全局极值进行联合局部搜索，增加搜索到全局最优解的概率，并与自适应参数更新策

略结合。实验结果表明在算例较小的Carlier测试集上对比其他3种改进算法，寻优

率分别提高了5.12%、1.3%、5.12%，RPD分别降低了5.91%、0.78%、2.80%。在

avg

较大的Liao测试集上比较，实验结果均优于4种对比算法，验证了所提算法在求解

混合流水车间调度问题上的有效性。

关键词：粒子群算法;迭代贪婪算法;Q学习;置换流水车间问题;混合流水车间问题

II

Abstract

Abstract

Productionschedulingproblem,asoneofthecorecontentsofenterpriseproduction

man