蚁群优化算法在差异工件批调度问题的应用研究

摘要

调度问题是一类重要的组合优化问题，广泛应用于生产制造、现代物流、网络通信和计算机科学等领域。批处理机调度问题是经典调度问题的拓展。在批调度问题中，一台机器可以同时加工多个工件。差异工件的批调度问题是研究尺寸和加工时间均不同的工件在批处理机器上的调度问题。它比尺寸相同工件的批调度更接近真实的生产环境，但也比相同尺寸工件的批调度更为复杂，因此针对该问题的研究具有更大的理论价值和应用前景。
　　本文首先介绍了调度问题的应用背景、问题的表示和分类，以及研究现状。接着介绍批调度问题的相关概念、以及与经典调度问题的区别，并对本文所研究的差异尺寸工件批调度问题进行了介绍。
　　其次，本文介绍了批调度问题的求解算法，包括数学规划法、启发式算法和元启发式算法，同时针对各类求解算法给出举例，具体地介绍了FFLPT、BFLPT等经典的启发式算法和基于遗传算法、模拟退火算法等的智能批调度算法。
　　接着，介绍了蚁群算法的起源、基本原理、算法模型、算法流程、性能指标评价方法，并对该算法的优点和不足进行分析，此外，介绍了本文所采用的最大最小蚁群算法(MMAS)。
　　随后，针对最小化制造跨度的差异工件单机批调度问题，本文提出了一种改进的最大最小蚁群算法。通过将研究目标转化为最小化浪费空间，采用候选集策略构建分批以减少搜索空间，利用基于浪费空间的启发式来更新信息素，最后还引出一种局部优化策略以进一步提高算法的性能。然后通过大量试验比较，确定了合适的参数配置，仿真实验结果表明，与其他几种已有算法相比，所提出的算法具有更好的效果。
　　最后，总结全文的研究内容，并对今后的研究方向进行了展望。

目录

声明

摘要

第一章 引言

1．1 调度问题的概述

1．1．1 研究背景

1．1．2 生产调度问题简述

1．1．3 参数表示及问题分类

1．1．4 研究现状

1．2 批调度问题

1．2．1 经典调度问题和现代调度问题

1．2．2 批调度问题和差异工件批调度问题

1．3 研究内容和结构安排

1．3．1 研究内容

1．3．2 论文结构安排

第二章 批调度问题的求解算法

2．1 数学规划法

2．2 启发式算法

2．3 元启发式算法

2．3．1 遗传算法

2．3．2 模拟退火算法

2．3．3 粒子群算法

第三章 蚁群算法

3．1 蚁群算法的起源与发展

3．2 经典蚁群算法

3．2．1 TSP问题

3．2．2 算法模型

3．2．3 算法流程

3．2．4 算法性能评价的指标

3．2．5 蚁群算法的优点与不足

3．3 最大最小蚁群算法

第四章 差异工件单机批调度问题的改进型最大最小蚁群优化算法

4．1 问题模型

4．2 问题下界

4．3 基于MMAS的求解算法

4．3．1 基于浪费空间的候选工件集

4．3．2 信息素定义

4．3．3 启发式信息

4．3．4 解的构建

4．3．5 信息素更新

4．3．6 信息素重新初始化

4．3．7 局部优化策略

4．3．8 算法描述

4．4 实验结果与分析

4．4．1 实验数据

4．4．2 参数设置

4．4．3 实验结果

4．5 结论

第五章 总结与展望

5．1 研究总结

5．2 研究展望

参考文献

致谢

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