水波优化算法及在车间调度问题中的应用研究

题名	水波优化算法及在车间调度问题中的应用研究
作者	刘欢
导师	赵付青
答辩日期	2018
学位名称	硕士
关键词	零等待流水车间调度问题水波优化算法迭代贪心块移动操作
摘要	零等待流水车间调度问题(no-wait flow shop scheduling problem,简称NWFSP)广泛的存在于制造业生产系统中,如钢铁轧制、食品加工、化学工业等。NWFSP作为带约束的流水车间调度问题,是一种经典的NP-hard问题。随着问题规模的不断增加,NWFSP就会变得越来越复杂且很难求得最优解。传统的数学方法和已有的调度策略已无法满足实际生产调度中的需求。因此,不论在调度理论方面的研究,还是在实际的制造业生产中设计有效的调度方案都是本领域研究的热点。水波优化算法(water wave optimization algorithm,简称WWO)是一种受浅水波理论启发而得出新型元启发式算法。WWO算法有框架简单,参数少,易实现等优点。此外,它还有特殊的迭代机制以及较强的全局搜索能力。本文深入研究了WWO算法的演化机制,通过分析算法的优缺点,对算法的框架和重要组成部分做了改进,平衡了算法的局部搜索能力和全局搜索能力,将改进的算法运用到NWFSP中。本文的主要研究内容如下:(1)针对水波优化算法稳定性差、随机性强以及局部搜索能力弱等问题,本文提出了一种离散的水波优化算法(a discrete water wave optimization algorithm for no-wait flow shop scheduling proble m,简称DWWO)并首次将其应用于NWFSP。在DWWO中,为了提高初始种群中候选解的质量,提出了一种新的初始化种群方法。采用了具有动态移除因子的迭代贪心算法作为传播算子以提高局部搜索能力。在折射算子中,应用交叉策略以避免算法陷入局部最优。在碎浪算子中,应用基于插入的深度局部搜索策略在局部最优解附近搜索。同时,为了提高算法的收敛速度引入了排差操作。应用Markov模型证明了DWWO算法能够以概率1收敛到全局最优解。仿真结果和统计分析表明了DWWO算法解决NWFSP的效率和有效性。(2)针对水波优化算法种群中各水波演化的特点,提出了一种基于单波机制的水波优化算法(a water wave optimization algorithm with the single wave mecha nis m for no-wait flow shop scheduling proble m,简称SWWO)。在SWWO算法中,首先应用了改进的NEH算法(NEH_COV)来构建高质量初始候选解。在传播操作中,采用了自适应块移位操作。在碎浪操作中,合理的利用了变邻域搜索策略来探索局部最优解。根据遗传算法中提出的模式理论,采用了交叉操作作为折射算子。此外,为了提升算法框架的全局搜索能力引入模拟退火策略来决定是否保留传播得到的差的候选解。最后,通过不同规模的测试集对SWWO算法的性能进行了测试。仿真结果及统计分析表明SWWO算法在求解NWFSP时的效率和有效性。(3)算法参数的设定是影响算法性能的关键因素。在DWWO算法中,针对灵敏性强的参数采用了多项式拟合的方式来确定参数取值。首先,分析影响该参数取值的因素。然后,运行测试集实例拟合得出不同参数取值下参数值与影响因素之间的关系式。最后,将拟合公式作为算法中参数的取值。
页数	79
URL	查看原文
语种	中文
收录类别	CNKI
中图分类号	TP18;TB497
文献类型	学位论文
条目标识符	https://ir.lut.edu.cn/handle/2XXMBERH/93852
专题	兰州理工大学
作者单位	兰州理工大学
第一作者单位	兰州理工大学
推荐引用方式 GB/T 7714	刘欢. 水波优化算法及在车间调度问题中的应用研究[D],2018.