基于适应度地形理论的作业车间调度方法研究

摘要

作业车间调度是车间调度中一类典型的问题,其研究方法与成果已被运用于众多其它类型调度问题以及实际的生产运作中,针对作业车间调度问题的特性研究和算法设计具有重要的意义。本文从适应度地形理论出发,从搜索空间地形的分布和结构两方面来探讨作业车间调度问题的本质特性和影响因素,并据此设计出高效的调度优化算法。
　　本文首先提出了基于Logistic模型的适应度地形研究方法,该模型能有效地区分不同的问题实例。在使用该方法来研究问题基本属性对适应度地形分布特性的影响中发现:问题的形状约束会对地形分布产生巨大影响,随着工件数对机器数比例的提升,问题的求解难度会呈现“易—难—易”的变化规律,问题加工路径约束的增多会使地形崎岖而难求解,而加工时间的影响比较微弱。实例测试表明,该方法相比以往研究方法能更好地反映问题的适应度地形特性。
　　接着使用局部搜索算法来研究问题适应度地形的结构特征,发现个体的搜索过程也会出现Logistic式的分布规律。分别使用2点交换邻域和关键路径插入邻域的局部搜索算法来研究问题基本属性对适应度地形结构特性的影响,结果表明:加工路径约束会对地形结构中盆地与峡谷的比例和性质产生较大影响,而形状和规模并未改变地形的结构性质。两种邻域策略所表现出来的不同地形结构特征,则为算法的设计提供了思路。
　　基于前述研究结论,本文在广义粒子群优化模型框架下提出了粒子群优化与变邻域搜索的混合算法。使用本文提出的Logistic模型来挑选高效的邻域组合策略,结果表明,基于交换的随机全邻域和基于插入的N5邻域具有较好的组合效果。实例测试表明,该混合算法效果要优于单一的邻域搜索,LA系列的40个实例中,有38个可以求得最优解,验证了所提出的算法的优越性。
　　文章最后对全文进行总结,并对作业车间调度和适应度地形的研究进行了展望。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪 论

1.1 课题来源、目的及意义

1.2 作业车间调度问题及其研究概况

1.3 适应度地形理论及其研究概况

1.4 本文的主要工作与结构

2基于Logistic模型的适应度地形分布研究

2.1 Logistic模型简介

2.2 JSP适应度地形的Logistic分布

2.3 Logistic分布的稳定性验证

2.4 JSP适应度地形的分布特性分析

2.5 本章小结

3 基于局部搜索的适应度地形结构研究

3.1 局部搜索简介

3.2 局部搜索中的Logistic分布现象

3.3 JSP适应度地形的结构特性分析

3.4 本章小结

4基于适应度地形理论的调度算法设计

4.1 广义粒子群优化模型简介

4.2 变邻域搜索简介

4.3 邻域结构设计

4.4 算法流程设计

4.5 实例测试与结果分析

4.6 本章小结

5总结与展望

5.1 全文总结

5.2 研究展望

致谢

参考文献

附录1 攻读硕士学位期间发表论文目录