自适应差分进化算法解决多目标有限缓冲车间调度问题研究

摘要

流水车间调度问题(flow shop scheduling problem，FSSP)是优化组合问题的一个重要分支，对该问题的研究有利于实现有限资源的优化配置和合理利用。但因该问题为NP-hard(non-deterministic polynomial-hard)，人工智能算法如今正逐渐代替数学方法，并取得了一定的成果。FSSP有多种类型，而带有限缓冲的FSSP(FSSP with limited buffers，FSSPWLB)因更接近实际生产状况而受到广泛重视，对缓冲大小的探讨在实际生产应用中也具有重要的经济价值。此外，求解多目标FSSP，可帮助决策者制定折中策略，在满足客户需求的前提下实现经济最大化等其他生产指标。因此研究多目标带有限缓冲的FSSP就显得尤为重要。
　　差分进化(differential evolution，DE)算法因其良好的特性而大量运用于连续问题优化中。该算法的参数对所优化的问题具有敏感性，通常要根据反复实验的结果或经验来设置，因此造成计算资源的额外开销，同时受到先验经验的制约。于是对自适应差分进化算法的研究不断涌现，其应用领域也不断拓宽。在使用DE对FSSPWLB进行优化时，因其测试实例规模不同，更需要自适应机制的参与。
　　综上所述，本文提出了一种自适应差分进化算法及其若干变体，来解决多目标FSSPWLB。目前看来，使用自适应差分进化算法优化多目标FSSPWLB尚属首例。
　　首先，本文使用最大顺序值(largest order value，LOV)规则完成DE个体与工件排序的映射，为设计合理的自适应机制，分析了DE个体、工件排序以及目标值差异之间的关系，研究参数F和CR对目标值的影响。在此基础上提出了一种参数CR的自适应差分进化算法，以适应对算法不同的搜索需求。同时为保证初始种群的质量，使用启发式算法构造了两个特殊个体。
　　其次，为加强算法局部搜索性能，除选择插入算子(Insert)外，还设计了一种基于概率模型的局部搜索算子(local search based on probability model，LSbPM)，目的在于挖掘非支配解集中的优质子序列信息，并加以利用。引入次解保留概念，将其嵌入Insert中，保留多次插入过程中产生的次解，充分运用搜索结果，在一定程度上补偿随即抛弃被支配解而造成的计算浪费。
　　接着，为验证本文所提出算法的各项性能的优劣，设计了其他两种变体，分别去除了LSbPM算子和次解保留机制，三种算法分别记为MPADE1、MPADE2和MPADE3，且与HDE做对比。选取三种不同基准集中的12个实例，以多项评价指标为参考，通过实验对比三种算法与 HDE。实验表明，次解保留机制在算法中发挥了重要作用，使得MPADE1和MPADE3在性能上超越MPADE2和HDE。而 LSbPM的效果并不理想，只有在评价次数较大时才能起到改善作用。整体来说，MPADE3是最好的算法，能够获得更多的非支配解，保证其质量，在分布性上也比其他算法好。
　　最后，MPADE3用以研究与HDE收敛特性的差别，并分析不同缓冲区容量对 FSSPWLB优化结果的影响。实验结果表明，MPADE3具有较快的收敛速度和较好的分布性。缓冲区在加工过程中具有重要作用，且所优化目标值的提升与缓冲区容量的增长不成正比，而是逐渐放缓的，这一结论可为机器配置提供指导。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 论文的主要工作及章节安排

2 差分进化算法发展

2.1 差分进化算法

2.2 多目标自适应差分进化算法

2.3 本章小结

3 有限缓冲流水车间调度

3.1 数学模型

3.2 目标函数

3.3 测试基准集

3.4 解的表示

3.5 缓冲区大小

3.6 本章小结

4 自适应差分进化算法设计

4.1 PADE算法设计

4.2 MPADE算法实现及流程

4.3 MPADE算法性能测试

4.4 本章小结

5 基于MPADE3的特定分析

5.1 收敛性分析

5.2 缓冲区影响研究

5.3 本章小结

6 结论与展望

6.1 论文总结

6.2 工作展望

参考文献

致谢

个人简历、在学期间发表的学术论文与研究成果