改进细菌觅食算法求解流水线调度问题

摘要

进入21世纪以来，市场竞争越来越激烈，人们的需求也越来越多样化，因此结合多种方法与技术而产生的先进制造系统已经成为现阶段企业共同关注的一种重要的生产制造模式。生产调度作为先进制造系统中的一个关键的模块，是企业提高生产率、降低生产成本、提高综合实力的基础和关键。流水线调度问题是生产调度领域研究得最广泛的问题之一，相关资料表明:约有四分之一的生产制造系统或组装线都可以简化成流水线模型，具有很强的工业应用背景;再加上该问题的NP-hard性质，常规方法难以求解，因此对该问题的研究也具备理论价值。
　　论文首先研究了混合流水线调度问题，对其研究背景、分类以及研究方法进行了分析，为论文的研究做好理论准备;然后结合流水线调度问题的特点以及细菌觅食优化算法求解组合优化问题的优势，提出运用一种改进的细菌觅食优化算法求解流水线调度问题。其次在深入研究标准细菌觅食优化算法的基础上，针对算法的不足，提出引入交叉优化算子、混合复制策略以及基于健康度和适应度共同作用的自适应迁徙概率以改进算法的策略。最后针对混合流水线调度问题中的置换流水线调度问题和零空闲流水调度问题，分别从编码方式、初始化、适应度函数、主要操作算子以及终止条件五个方面进行改进细菌觅食优化算法的设计，并通过Matlab编程实现算法对典型流水线调度问题的求解，以验证算法的有效性;同时通过标准算法和改进算法的对比体现了改进算法的优化性能，并对比了两种初始化方法对改进算法的影响，以验证算法的初始解鲁棒性。结果表明:在中小规模的流水线调度问题中，改进细菌觅食优化算法的性能优于标准算法，能获得问题的最优解，并且具有良好的初值鲁棒性。

目录

声明

摘要

第一章 绪论

1．1 引言

1．2 国内外研究现状

1．2．1 流水线调度研究现状

1．2．2 细菌觅食优化算法研究现状

1．3 研究目标、技术路线和可行性分析

1．4 创新性

1．5 主要内容和框架

第二章 混合流水线调度问题

2．1 引言

2．2 混合流水线调度问题概述

2．3 混合流水线调度问题的研究方法

2．3．1 精确方法

2．3．2 启发式方法

2．3．2 智能优化算法

2．4 流水线调度Benchmark问题

2．5 本章小结

第三章 改进细菌觅食优化算法

3．1 引言

3．2 标准细菌觅食优化算法

3．2．1 BFO算法概述

3．2．2 BFO主要操作

3．2．3 BFO算法流程

3．3 改进细菌觅食优化算法

3．3．1 趋向性操作的改进策略

3．3．2 复制操作的改进策略

3．3．3 迁徙操作的改进策略

3．3．4 IBFO算法流程

3．4 本章小结

第4章 IBFO在置换流水线调度中的应用

4．1 引言

4．2 置换流水线调度问题的数学描述

4．2．1 数学模型

4．3．2 最大完成时间的计算方法

4．3 IBFO算法设计

4．3．1 编码方法

4．3．2 初始化

4．3．3 适应度函数

4．3．4 IBFO操作算子设计

4．3．5 终止条件设计

4．4 仿真试验及结果分析

4．4．1 IBFO求解Car类问题的结果和分析

4．4．2 IBFO求解Taillard问题的结果和分析

4．5 本章小结

第5章 IBFO在零空闲流水线调度中的应用

5．1 引言

5．2 零空闲流水线调度问题

5．2．1 NIFS问题描述

5．2．2 NIFS数学模型

5．2．3 最大完成时间的计算方法

5．3 算法设计

5．3．1 设计方案

5．3．2 基于NEH的种群初始化

5．3．3 算法流程

5．4 仿真试验和结果分析

5．5 本章小结

总结和展望

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果