基于差分进化算法的流程工业生产调度研究与应用

发布时间：2020-04-05 11:10

【摘要】：车间调度是制造业信息化的关键技术,是提高企业核心竞争力的重要力量。如何利用先进技术解决实际工业问题,合理安排生产流程,提高企业生产效率,是一个非常重要的课题。启发式算法是众多解决车间调度问题中较有效的算法,而差分进化算法(DE)是典型的启发式算法,也是一种基于种群进化的算法,主要经过交叉、变异、选择操作产生新种群,对各种复杂优化问题具有较好的性能。本文基于DE算法做了一些研究、改进并在车间调度中进行了应用,主要工作包括:(1)提出了一种改进的自适应差分进化算法(FMDE)。传统的DE算法的变异因子是个固定常数,会导致种群出现局部最优(“早熟”现象)。对变异因子的改进能提高算法的性能,本文提出了一种改进的自适应差分进化算法(FMDE),利用测试函数对算法性能进行验证。实验结果表明,该算法在种群进化时可以自动调节变异因子值,提高了全局搜索能力,表明FMDE算法具有较优的性能。(2)提出了一种粒子群和改进自适应差分进化的混合算法(PSO_FMDE)。鉴于粒子群算法(PSO)和DE算法都是基于种群进化的算法,本文结合两个算法的特点,提出了一种随机变异机制,通过生成随机个体的方式避免种群出现停滞现象。采用测试函数对算法性能进行分析,结果表明,PSO_FMDE算法较单一算法而言,性能更优,更易于靠近全局最优解。(3)将所提出的FMDE算法和PSO_FMDE算法应用于车间调度优化。流水车间调度(FSP)是一种典型的流程工业生产调度方式,为了更好的解决FSP问题,本文以最小化最大完工时间为优化目标,将流水车间调度问题转化为数学问题模型,使用FMDE算法和PSO_FMDE算法进行求解。采用标准调度问题测试集上对流水车间调度问题进行求解和性能分析。结果表明,本文提出的两种算法在解决FSP问题中有良好的性能,更容易找到最优调度方案。本文提出了两种DE改进算法,通过函数优化问题验证了算法的有效性。所提出的改进算法分别应用于生产调度优化问题,结果表明算法在解决FSP问题方面具有良好的性能。本文研究成果有助于推动进化算法和生产调度理论的发展,具有重要的理论和实际意义。
【图文】：

甘特图,甘特图,调度方案,算法

在三种数据规模（20*5、50*5、100*5）下，FMDE 算法的方差依次为52.32、50.67、26.84。说明在相同的机器数量下，随着工件数目越来越多，FMDE算法的稳定性会表现得更好。PSO_FMDE 算法的方差依次为 13.91、12.76、6.12。同样说明了算法的稳定性和数据规模成正比，而且在相同数据规模下，PSO_FMDE 算法比 FMDE 算法的稳定性更高。通过上述分析可以发现，本文提出的改进自适应差分进化算法（FMDE）比 MDE 算法和 DE 算法表现出更好的性能，并且引入粒子群算法的 PSO_FMDE 算法更具有稳定性和优越性。试验表明了通过在进化过程中对变异因子适时进行合理的优化，能够保证种群个体的多样性，，增强算法在整个运算空间中各个情况的搜索能力。为了更好的观察求解车间调度问题的进度和效果，实验还对四种不同的算法绘制甘特图。甘特图是一种用来随着时间进度来观察整个项目进度发展的工具，而且易于理解。通过甘特图可以清楚的了解不同算法求解车间调度问题的调度过程、每个机器上的调度方案、每个机器上的完工时间、整个工程的完工时间等。DE、MDE、FMDE、PSO_FMDE 四个算法求解车间调度问题的甘特图如图 4-3~4-6所示。

甘特图,甘特图,调度方案,算法

而且易于理解。通过甘特图可以清楚的了解不同算法求解车间调度问题的调度过程、每个机器上的调度方案、每个机器上的完工时间、整个工程的完工时间等。DE、MDE、FMDE、PSO_FMDE 四个算法求解车间调度问题的甘特图如图 4-3~4-6所示。图 4-3 使用 DE 算法对规模为 20*5 的调度集优化的一次调度方案甘特图Fig. 4-3 Gantt Chart of Primary Scheduling Scheme for Scheduling Set Optimization with Scale20*5 Using DE Algorithms
【学位授予单位】：青岛科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：F274;TP18

【相似文献】