混合分布估计算法及其在车间调度中的应用研究

摘要

车间调度是影响企业生产效率的关键因素之一，采取合理有效的调度策略可以缩短工期、加快交货速度以及降低库存，提高企业生产效率。然而面对种类繁多，工艺复杂的实际车间调度问题，现有的调度策略及优化方法还不能够解决非线性、高维度、强约束、大规模的车间调度问题。因此，寻求有效的调度策略及优化方法仍然是调度理论研究领域所关注的重要问题。分布估计算法（EDA）是一类基于概率统计的新型进化算法，其根据种群中优质个体的信息来建立概率模型，并通过对所建立的概率模型采样来生成新个体，周而复始，从而实现种群进化。分布估计算法通过概率模型来引导和维持种群的进化过程，有效地避免了遗传算法交叉、变异对构造块的破坏，可以更快速、可靠地解决传统优化方法难以解决的非线性高维复杂问题。分布估计算法具有较快的收敛速度，较强的全局搜索能力和协同能力，因此能够在演化计算及优化领域占据重要地位。
　　本研究主要内容包括：⑴在深入研究分布估计算法理论的基础上，针对分布估计算法局部搜索能力不足的问题，本文提出一种基于分布估计和混沌差分进化的混合优化算法(cDE/EDA)。该算法通过所提出的决策因子将具有局部搜索能力的差分进化算法与分布估计算法融合，有效地弥补了分布估计算法的不足。同时，将混沌参数更新策略（CPC）引入到差分进化算法中以加强其搜索能力。基于单调有界序列的极限定理对cDE/EDA算法的全局收敛性进行了证明，通过正交实验设计的方法分析了cDE/EDA算法的参数灵敏性。最后，通过Benchmark测试函数测试了cDE/EDA的性能，实验结果表明cDE/EDA具有明显的可行性和有效性。⑵针对作业车间调度（JSSP），提出一种基于邻域搜索的混合分布估计和差分进化算法(NS-HDE/EDA)。该算法以cDE/EDA算法为基础，同时融入一种基于关键路径块结构的邻域搜索算法(NS)以加强cDE/EDA算法的搜索能力和改善解的质量；并通过正交实验讨论了所提出算法的参数灵敏性。最后，利用典型Job shop实例对NS-HDE/EDA进行了测试，实验结果表明，NS-HDE/EDA可以有效地解决JSSP问题。⑶针对置换流水车间调度（PFSSP），提出一种混合分布估计----和声搜索算法(HS/EDA)。HS/EDA采用基于工序的编码方式，通过 LOV规则将种群个体转化为编码序列，利用和声搜索算法（HS）初始化种群，EDA算法引导和维持种群进化。为了进一步加强HS/EDA的局部搜索能力，本文将两种局部搜索算法以概率方式融合，提出一种混合局部搜索算法并融入到 HS/EDA。最后，通过典型 Flow shop实例测试了 HS/EDA对于求解PFSSP问题的有效性。

目录

封面

声明

目录

中文摘要

英文摘要

插图索引

附表索引

第1章 绪 论

1.1 引言

1.2车间调度问题研究综述

1.3 车间调度问题概述

1.4论文的主要研究工作以及组织结构

第2章 分布估计算法

2.1从遗传算法到分布估计算法

2.2分布估计算法研究综述

2.3 分布估计算法概述

2.4 小结

第3章 基于分布估计和混沌差分进化的混合优化算法

3.1 引言

3.2 子优化算法

3.3 决策因子

3.4 cDE/EDA算法流程

3.5 cDE/EDA收敛性分析

3.6 仿真实验及结果分析

3.7 小结

第4章 基于NS-HDE/EDA的Job shop调度算法

4.1 引言

4.2 Job shop调度问题

4.3 基于NS-HDE/EDA的Job shop调度算法

4.4 仿真实验及结果分析

4.5 小结

第5章 基于HS/EDA的PFSSP调度算法

5.1 引言

5.2 置换Flow shop调度问题

5.3 基于HS/EDA的PFSSP调度算法

5.4仿真实验及结果分析

5.5 小结

总结与展望

参考文献

致谢

附录A：攻读学位期间发表的学术论文目录