论文部分内容阅读
车间调度是制造执行系统中的核心内容和关键技术,是提高制造系统性能的支撑点。高效的调度策略能够提高企业的产品质量和管理效率,缩短生产周期,增强制造企业的综合实力。生产调度问题复杂多样,是一种典型的NP-hard问题。而现有的智能调度策略在算法设计及参数选择上均具有一定的随机性及盲目性,很难满足实际生产中的复杂要求。车间调度问题的理论研究及高效算法的设计仍然是本领域的研究热点。适应度地形(fitness landscape)的统计特征分析方法已被广泛应用于众多领域。对车间调度问题的适应度地形进行分析,有助于理解演化算法(evolutionary algorithm)在离散解空间中的搜索行为,预测算法求解该问题的性能,提升智能算法(cleveralgorithms)对车间调度问题的适应度。本论文主要从零等待车间调度问题(No-Wait Flow shop Scheduling Problem,简称NWFSP)的适应度地形分析入手,研究不同邻域结构的适应度地形差异,挖掘NWFSP的本质特征,为演化算法的设计提供了理论支持,并由此给出了高效的车间调度优化策略。本论文的研究工作和成果主要包含如下几个方面:(1)分析了基于阶乘数表示的NWFSP适应度地形。本文在阶乘数表示法的基础上构建了相应的编码和解码方法,以完成离散工件调度序列与自然数之间的映射,将NWFSP转化为一种连续问题。之后使用位置类型分布(position type distributions)和适应距离相关性(Fitness Distance Correlation,简称FDC)两个指标对适应度地形进行评价,并与其他6种经典邻域结构进行对比。FDC实验结果以及对阶乘数编码理论的分析证实了适应度地形中存在多个大山谷结构(big valleys),这使得演化算法(evolution algorithm)能有效地探索(explore)由阶乘数表示的离散解空间。然而,位置类型分布的统计结果表明该地形高度崎岖并存在着大量的局部最优,不利于演化算法在开发(exploiting)阶段展开局部搜索。通过对NWFSP适应度地形的分析,揭示了该类问题的本质特征,并对演化算法的选择及设计提供了必要的理论支持。(2)设计了一种基于粒子群优化(Particle Swarm Optimization,简称PSO)及种群自适应(population adaptation)的调度算法(FPAPSO),用以求解阶乘数表示的NWFSP问题(F-NWFSP)。首先,本文使用阶乘数编码解码方法将离散工件调度序列映射至连续自然数空间。然后,根据对F-NWFSP适应度地形的分析结果,在标准的PSO中引入了三个算子以增强其求解性能:使用最近邻(nearest neighbor)及NEH启发式算子来为PSO构造优质的初始种群;使用变邻域搜索(variable neighborhood search)算子提升PSO在该地形中的局部搜索能力;使用种群自适应算子来提高PSO的种群多样性以避免其陷入局部最优。最终在一些经典测试集上的实验以及严格的假设检验结果均表明了FPAPSO求解NWFSP问题的有效性、高效性及鲁棒性。(3)针对迭代局部搜索(Iterated Local Search,简称ILS)算法在连续优化问题上应用的不足,提出了一种基于种群的混合迭代局部搜索算法(Hybrid population-based ILS,简称HILS)来求解连续优化问题。为了提高ILS的全局及局部搜索能力,本文增强了原始ILS中的三个关键算子:使用有限内存的拟牛顿法(LBFGS)作为局部搜索算子提升ILS局部搜索能力,使用基于成功历史自适应的差分进化算法(SHADE)作为扰动算子提升ILS全局搜索能力,使用基于模拟退火的接收准则算子来平衡ILS的搜索过程。在CEC2017标准测试函数上的实验结果表明,与当前一些最先进的算法相比,HILS具有优秀的搜索性能及更快的收敛速度,并可扩展于求解F-NWFSP问题。