基于蚁群算法的订单接受与加工调度优化决策问题研究

摘要

对于按单生产的企业，由于产能的有限性、交货期承诺要求等因素，接受并加工所有的订单可能会导致部分订单不能及时交付、延迟惩罚罚金增加、顾客满意度下降。从供应链管理角度考虑，应该区分订单对企业的重要性，合作与协调订单选择与加工调度决策，以实现优化企业收益。
　　 订单接受与加工调度优化决策问题是典型的NP-难的，难以用传统的精确优化算法求解大规模决策问题。蚁群算法是由意大利学者Dorigo等人根据自然界真实蚂蚁觅食的过程所提出的智能算法。实践表明，蚁群算法在复杂的组合优化问题上已经有了较多的应用。本文从蚁群算法的基本特征出发，首先针对单机环境下优化决策问题提出了改进的蚁群算法。在改进蚁群算法中对概率函数进行适当的修改，有助于选择收益大、交货紧急的订单;多种局部搜索相结合的方式，能够有效地跳出局部收敛;其次，针对两机流水线环境下优化决策问题提出了混合蚁群算法。在混合蚁群算法中将禁忌搜索算法与蚁群算法相结合，蚁群算法为禁忌搜索算法提供较好的初始解，而禁忌搜索则增强了算法的局部搜索能力，极大地提高了算法的寻优能力。
　　 最后，本文针对两种环境下所提出的蚁群算法，进行相应算法的参数设定，并通过大量的仿真实验来验证效果的有效性。结果表明，改进后的两类蚁群算法在运算结果和运算时间等均有较好的性能表现。

目录

声明

摘要

1 绪论

1．1 研究背景及意义

1．2 订单接受与加工调度优化决策问题研究现状

1．2．1 订单接受与加工调度优化决策问题描述

1．2．2 订单接受与调度问题的研究现状

1．3 本文研究内容

1．4 本文组织结构

2 蚁群算法

2．1 引言

2．2 蚁群算法基本原理

2．2．1 人工蚂蚁和真实蚂蚁的异同

2．2．2 人工蚁群算法的原理

2．3 基本蚁群算法模型及实现

2．4 蚁群算法的发展

2．4．1 蚁群算法的特点

2．4．2 蚁群算法参数设计改进

2．4．3 蚁群算法结构设计的改进

2．5 本章小结

3 基于改进蚁群算法的单机环境下优化决策问题研究

3．1 单机环境下的订单接受与加工调度问题

3．2 算法设计

3．2．1 解的算法表示

3．2．2 初始解的生成

3．2．3 蚂蚁数目和迭代次数对蚁群算法性能的影响

3．2．4 信息素、期望启发因子以及信息素挥发因子

3．2．5 信息素变异机制

3．2．6 邻域操作

3．2．7 精英蚂蚁策略

3．3 改进蚁群算法的实现及算例分析

3．3．1 改进蚁群算法的实现过程

3．3．2 算例分析

3．4 实验结果分析

3．4．1 数据生成

3．4．2 蚁群算法的参数设定

3．4．3 实验结果分析

3．5 结论

4 基于混合蚁群算法的两机流水线环境下优化决策问题研究

4．1 两机流水线下的订单接受与加工调度问题

4．2 混合蚁群算法设计

4．2．1 禁忌搜索算法特征简介

4．2．2 初始解及初始信息素的设计

4．2．3 概率函数的选择

4．2．4 信息素的设置规则

4．2．5 禁忌搜索的邻域操作

4．2．6 禁忌搜索表的嵌入

4．2．7 评价函数、终止准则及藐视准则

4．3 混合蚁群算法的实现及算例分析

4．3．1 混合蚁群算法的实现过程

4．3．2 算例分析

4．4 实验结果分析

4．4．1 参数设定

4．4．2 实验结果分析

4．5 结论

5 总结与展望

5．1 论文总结

5．2 研究展望

致谢

参考文献

附录