基于一种新编码的作业车间调度

摘要

作业车间调度问题（Job Shop Scheduling Problem，简称JSSP）是一个非常复杂的NP—难组合优化问题，它在工程应用中有着十分重要的意义。早期学者对作业车间调度问题的研究主要集中在数学方法上。随着计算机运算速度的迅速增长和对调度有效性要求的显著增加，越来越强调在消耗某些额外计算费用的基础上获得更好的调度方案，于是，各种启发式方法在作业车间调度问题中的应用应运而生。 本文在研究现有的JSSP求解方法和相关基本理论的基础上，对目前JSSP的编码方式（特别是基于操作的编码方式）进行了深入的分析，提出了一种新的JSSP编码方式——调度编码。该编码直接表示为调度矩阵和调度中各操作的完成时间矩阵的形式，不需要解码过程，从而避免了编码空间与调度空间多对一的映射问题。 人工免疫系统是近年来计算智能的研究热点。本文对免疫克隆选择算法进行了深入的研究，并结合新的编码方式，提出了一种基于调度编码的免疫记忆克隆选择作业车间调度算法。 该算法根据新的编码方式和JSSP解分布较广的特点，构造了抗体群和抗体死亡单元。抗体群根据抗体亲和力的大小被分为记忆单元和一般抗体单元。记忆单元保存抗体群中亲和力较高的抗体。 算法通过对记忆单元和一般抗体单元中的每个抗体执行免疫克隆操作，使抗体群不断进化。 在算法的每一次迭代以后，对记忆单元和一般抗体单元中的抗体进行交互。对一般抗体单元中某些不能变好的抗体执行死亡操作，并用新产生的抗体替代。抗体死亡单元是一个规模固定的，比抗体群规模小很多的另外一个抗体群，它保存来自每一代抗体群在死亡操作中死亡的抗体。如果在抗体群中出现与抗体死亡单元中相同的抗体，则直接死亡该抗体并用新产生的抗体替代。实验结果表明这种方法是有效的。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2作业车间调度的求解方法和研究现状

1.2.1最优化求解方法(Optimization Method)

1.2.2近似求解方法(Approximation Method)

1.3本文的主要内容

第二章作业车间调度问题的基本理论

2.1车间调度问题概述

2.1.1车间调度问题的描述

2.1.2车间调度问题的分类

2.2作业车间调度问题描述

2.2.1作业车间调度问题(Job Shop Scheduling Problem)

2.2.2性能评价标准

2.2.3 JSSP的基本数学模型

2.3 JSSP的表示法

2.3.1甘特图(Gantt Chart)表示法

2.3.2析取图(Disjunctive Graph)表示法

2.4 JSSP调度分类

2.5 JSSP的计算性

2.6本章小结

第三章人工免疫系统

3.1生物免疫系统

3.2人工免疫系统

3.2.1研究历史

3.2.2基本术语

3.3克隆选择算法

3.3.1克隆选择学说

3.3.2免疫克隆选择算法

3.4本章小结

第四章作业车间调度问题的编码研究

4.1编码要考虑的问题

4.2 JSSP编码分类

4.3基于操作编码方式的分析

4.3.1编码分析

4.3.2解码分析

4.3.3编码空间与调度空间的映射关系分析

4.4 JSSP的一种新编码

4.4.1编码

4.4.2解码

4.4.3编码特性分析

4.5本章小结

第五章基于调度编码的免疫记忆克隆选择作业车间调度

5.1编解码

5.2基于调度编码的免疫记忆克隆选择作业车间调度

5.3仿真实验与结果分析

5.4本章小结

第六章总结与展望

参考文献

致谢