量子粒子群算法在差异工件批调度问题中的应用研究

摘要

调度是影响制造业生产效率的关键因素，采用合理的调度方案可以缩短产品生产周期，减少周转时间和产品库存，提高产品的产出率，最终降低产品制造成本，提高利润和客户满意度。差异工件批调度问题是调度领域的一个重要分枝，与相同尺寸工件批调度问题相比，其更接近于现实的生产状况。当前，半导体制造、港口货物装卸、陶瓷烧制、车床加工、汽车货运等领域都属于差异工件批调度的研究范畴，因此对差异工件批调度问题的研究具有重要的现实意义。
　　 本文首先介绍了调度问题的基本概念，着重介绍了差异工件批调度问题，分析了该问题的性质，说明了差异工件批调度的研究现状，阐述了以往求解差异工件批调度问题的主要算法。
　　 其次，本文介绍了基于差异工件单机批调度问题的量子粒子群算法(BQPSO)及其改进算法(BIQPSO)。针对调度问题的离散特性，本文设计了算法的编码方式，结合启发式算法，设计了基于该问题的量子粒子群算法；又针对迭代过程中粒子逐步失活，算法易趋于早熟的缺陷，引入交叉和变异算子，设计了基于该问题的改进算法，提高了粒子的多样性，保持了粒子的活性，增强了粒子的搜索能力，避免算法陷入早熟；通过大量仿真实验比较，本文中所设计的BQPSO算法及BIQPSO算法优于经典文献中的算法，且BIQPSO算法性能优于BQPSO算法。
　　 接着，将问题拓展到平行机领域，与单机问题相比，平行机批调度问题的应用更广泛，更接近现实情况，也更加符合当前工业领域的需求。本文通过建立数学模型对问题进行描述，在此基础上，设计了基于差异工件平行机调度的量子粒子群算法(P-BQPSO算法)及其改进算法(P-BIQPSO算法)，通过随机方式产生大量仿真算例进行比较，实验证明本文设计算法具有令人满意的性能。最后，在总结全文的基础上，对今后的研究提出了建议和展望。

目录

文摘

英文文摘

声明

第1章绪论

1.1 调度问题概念

1.2 差异工件批调度问题

1.2.1 经典调度问题与现代调度问题

1.2.2 批调度与差异工件批调度问题

1.3 计算复杂性与NP类问题

1.4 批调度问题的研究现状

1.5 研究动机、研究结果和论文结构

1.5.1 研究动机和结果

1.5.2 论文结构

第2章差异工件批调度问题的求解算法

2.1 启发式算法

2.2 元启发式算法

2.2.1 遗传算法

2.2.2 模拟退火算法

2.2.3 粒子群算法

第3章单机批调度问题的量子粒子群算法及其改进算法

3.1 差异工件单机批调度问题的数学模型

3.2 量子粒子群算法

3.3 差异工件单机批调度问题的量子粒子群算法

3.3.1 编码方案及初始化

3.3.2 粒子适应度的计算

3.3.3 算法描述

3.3.4 算法流程

3.4 差异工件单机批调度问题的改进量子粒子群算法

3.4.1 算法描述

3.4.2 算法流程

3.5 实验与结果分析

3.5.1 测试实例的产生方法

3.5.2 算法参数设置

3.5.3 差异工件批调度问题的量子粒子群算法比较

第4章平行机批调度问题的量子粒子群算法及其改进算法

4.1 差异工件平行机批调度问题的数学模型

4.2 差异工件平行机调度的量子粒子群算法及其改进算法

4.2.1 编码方案及初始化

4.2.2 粒子适应度的计算

4.2.3 算法流程

4.3 实验与结果分析

4.3.1 测试实例的产生方法

4.3.2 算法参数设置

4.3.3 差异工件批调度问题的量子粒子群算法比较

第5章结束语

5.1 全文总结

5.2 研究展望

参考文献

致 谢

在读期间发表的学术论文与取得的研究成果