置换流水车间调度问题上的蚁群算法研究

摘要

置换流水车间调度问题(Permutation Flow Shop Problem-PFSP),是车间调度领域一个经典的问题,具有重要的理论意义和现实意义。在理论上,该问题代表了一类具有排列性质的组合优化问题,其求解对于其他问题有很强的指导意义。在现实中,一个好的调度顺序,能够减少企业的生产时间,提高企业的资源配置能力,增强企业的竞争力。
　　 由于置换流水车间问题的NP-难性质,借鉴蚁群算法在旅行商问题上的成功应用,本文使用蚁群算法来对其求解进行了尝试。在求解质量和计算时间两个方面,提出了改进的机制。
　　 首先,提出蚁群算法解决置换流水车间调度问题的一般步骤,即针对该调度问题的蚁群算法的通用结构。
　　 在提高求解质量方面:提出了一种蚂蚁在周游的过程中一次选择两个任务的路径构造方法；提出了一种新的与任务“协调度”有关的本地启发规则,将这些工作组合成一个改进的蚁群算法,用于求解调度问题。实验中,将改进算法应用于标准的测试问题中,并将所求结果与文献中数据比较,比较显示改进工作能够求得较好的调度结果。
　　 在减少计算时间方面:提出了一种减少时空复杂度的类似快速排序的周游方案；根据置换流水车间问题的关键路径、关键块概念,设计了邻域搜索时的剪枝规则,用以提高计算的效率；对蚁群算法求解该调度问题,进行了并行计算方面的设计,通过实验验证了所做工作的有效性。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 问题背景和意义

1.2 问题描述

1.3 计算复杂性

1.4 PFSP问题的求解算法

1.4.1 PFSP的精确求解方法

1.4.2 PFSP的构造式启发式算法

1.4.3 PFSP的提高式启发式算法

1.5 本文主要工作

1.6 本文组织结构

第2章 蚁群算法简介

2.1 群集智能

2.2 自然启发

2.3 工作机制

2.4 蚁群算法的演变

2.5 蚁群算法的理论性研究

2.6 蚁群算法的应用

第3章 优化求解质量的改进蚁群算法

3.1 PFSP的形式化描述

3.2 蚁群算法求解PFSP的通用框架

3.2.1 蚁群算法的核心流程

3.2.2 蚁群算法求解PFSP的一般步骤

3.3 改进的周游方案

3.3.1 方法描述

3.3.2 实验表现

3.3.3 原因分析

3.4 改进的启发信息

3.4.1 启发信息介绍

3.4.2 协调度优先启发信息

3.5 数值实验

3.6 小结

第4章 减少计算时间的优化策略

4.1 类似快速排序的构造方案

4.1.1 方案描述

4.1.2 算法的起因

4.1.3 复杂度分析

4.2 剪枝规则的应用

4.3 并行化的蚁群算法

4.3.1 关于PFSP的并行性

4.3.2 蚁群算法的内在的并行性

4.3.3 并行求解Cmax(π)的实验

4.3.4 综合实验

结论

参考文献

致谢

附录A攻读硕士学位期间发表的论文

附录B 攻读硕士学位期间参加的项目