调整时间与工序顺序相关的车间作业调度算法

摘要

调整时间与工序顺序相关的车间作业调度问题（SDST-JSP）广泛存在于制造工业中，如纺织、半导体生产等。由于其比经典车间作业调度问题（JSP）能更好地建模实际生产调度，故具有非常重要的实际应用价值。
　　 本文在分别改进遗传算法和禁忌搜索算法的基础上，提出将两者相结合的混合算法GA+TS。设计启发式算法与随机算法相结合的初始解生成策略，以保持种群的优良性和多样性；构造新的交叉算子（ROX），以有效保存父代的优良基因；提出具有扰动因子的解码算法（RG&T），在生成活跃调度的基础上，扩大算法搜索空间；构造新的启发式算法（BidirS和ListS），为禁忌搜索算法提供铰好的初始解：提出五种新的邻域结构，有效地增强算法的局部搜索能力；采用禁忌表动态变长策略，提高对解空间有效搜索；采用短期记忆和长期记忆相结合的策略，以充分利用搜索历史信息，避免循环搜索，从而扩大算法对解空间的覆盖率；提出遗传算法与禁忌搜索算法相结合的混合启发式算法，通过加强遗传算法局部搜索能力，提高禁忌搜索算法初始解的多样性，从而提高算法总体眭能。
　　 通过基于BT标准的测试实例，将GA+TS与目前最好的两个算法SB+GLS和GA+LS进行比较。实验结果表明所提算法在相对误差方面要优于其它两个算法，故能有效地解决SDST-JSP问题。

目录

文摘

英文文摘

第1章 绪论

1.1 车间作业调度问题

1.1.1 课题背景

1.1.2 车间作业调度问题的特点

1.1.3 SDST-JSP问题的求解方法

1.2 SDST-JSP问题的研究现状

1.3 论文主要内容

1.4 论文结构

第2章 适用于SDST-JSP问题的遗传算法

2.1 SDST-JSP问题描述

2.1.1 相关定义

2.1.2 SDST-JSP问题的数学模型

2.1.3 SDST-JSP问题的有向图表示

2.2 适用于求解SDST-JSP问题的遗传算法

2.2.1 初始解的生成

2.2.2 编码与解码

2.2.3 适应度

2.2.4 交叉算子

2.2.5 选择算子

2.2.6 变异算子

2.3 算法比较与分析

2.3.1 常用的测试实例

2.3.2 比较与分析

2.4 本章小结

第3章 改进的禁忌搜索算法

3.1 改进的禁忌搜索算法

3.1.1 初始解的生成

3.1.2 邻域结构

3.1.3 总完工时间的估算

3.1.4 禁忌表的设计

3.1.5 特赦准则

3.1.6 循环检测

3.1.7 终止准则

3.2 带长期记忆的搜索策略

3.3 算法比较与分析

3.4 本章小结

第4章 求解SDST-JSP问题的混合算法

4.1 求解SDST-JSP问题的混合算法

4.2 算法比较与分析

4.3 本章小结

结论

致谢

参考文献

攻读硕士学位期间发表的学术论文