| 【中文题名】 | 改进的伪并行遗传算法在车间调度中的应用研究 |
| 【英文题名】 | Application of Improved Pseudo-Parallel Genetic Algorithms for Job-Shop Scheduling Problem |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-11-23 |
| 【中关键词】 | 遗传算法,分段-迭代交叉,伪并行,车间调度,混沌, |
| 【英关键词】 | Genetic Algorithms,Segment-Iterative Crossover,Pseudo-Parallel,JSP,Chaos, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 当前，是一个竞争激烈和信息技术飞速发展的时代，市场竞争越来越激烈，企业面临着更多挑战，中国正以制造业大国的身份迅速崛起，应变速度、降低成本、以及较高的生产能力和效率成为企业生存和发展最主要的竞争要素。此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有十分重要的理论和实用价值。
作业车间调度问题是许多实际生产调度问题的简化模型，是一个典型的NP-hard问题，因此其研究具有重要的理论意义和工程价值，它也是目前研究最广泛的一类典型调度问题。该问题的复杂性决定了随着调度问题规模的增大，求解时搜索空间的范围也随之扩大，求解的计算量呈指数增长。这就要求在求解作业车间调度问题的过程中必须保证个体的多样性，除了能够实现问题的全局优化外，还能提高寻求到最优调度解的几率，缩短最优解的搜索时间。
本文提出了一种改进的伪并行遗传算法(Improved Pseudo-Parallel Genetic Algorithm，简称IPGA)，将改进的伪并行算法与标准遗传算法伪并行操作(采用并行思想，在同一台机器上完成操作)，保证了种群多样性，防止局部早熟收敛；改进算法对部分遗传算子... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
Abstract |
4-8 |
|
第一章 绪论 |
8-16 |
|
1.1 课题研究的背景、目的及意义 |
8 |
|
1.2 车间调度问题的国内外研究现状综述 |
8-9 |
|
1.3 遗传算法求解调度问题的国内外研究现状综述 |
9-13 |
|
1.3.1 遗传算法的国内外现状 |
9-10 |
|
1.3.2 混合遗传算法的国内外现状 |
10-11 |
|
1.3.3 遗传算法求解车间调度问题的国内外现状 |
11-13 |
|
1.4 课题的来源及研究的主要内容 |
13-16 |
|
1.4.1 课题来源 |
13 |
|
1.4.2 课题研究的主要内容 |
13-14 |
|
1.4.3 课题研究的意义 |
14-16 |
|
第二章 遗传算法和作业车间调度问题 |
16-26 |
|
2.1 引言 |
16 |
|
2.2 遗传算法 |
16-20 |
|
2.2.1 遗传算法的基本概念 |
16-17 |
|
2.2.2 遗传算法的基本操作 |
17-19 |
|
2.2.3 遗传算法的收敛性分析 |
19-20 |
|
2.2.4 标准遗传算法的操作过程 |
20 |
|
2.3 混合遗传算法 |
20 |
|
2.4 作业车间调度问题 |
20-24 |
|
2.4.1 引言 |
20-21 |
|
2.4.2 车间作业调度问题的分类与特点 |
21-22 |
|
2.4.3 JSP的数学模型 |
22-24 |
|
2.4.4 约束条件 |
24 |
|
2.5 作业车间调度的基本方法 |
24-25 |
|
本章小结 |
25-26 |
|
第三章 标准遗传算法解决作业车间调度问题 |
26-35 |
|
3.1 引言 |
26 |
|
3.2 编码方法 |
26-27 |
|
3.3 适应度函数 |
27-28 |
|
3.4 遗传操作 |
28-31 |
|
3.4.1 种群初始化 |
28 |
|
3.4.2 选择操作 |
28-29 |
|
3.4.3 交叉操作 |
29-30 |
|
3.4.4 变异操作 |
30 |
|
3.4.5 替换策略 |
30-31 |
|
3.5 遗传算法的相关参数 |
31-32 |
|
3.6 遗传算法的改进 |
32-34 |
|
本章小结 |
34-35 |
|
第四章 一种改进的遗传算法在车间调度中的应用 |
35-51 |
|
4.1 引言 |
35 |
|
4.2 算法的改进及流程 |
35-42 |
|
4.2.1 编码 |
35-36 |
|
4.2.2 适应度函数 |
36-37 |
|
4.2.3 收敛准则 |
37 |
|
4.2.4 分段-迭代交叉理论的研究 |
37-39 |
|
4.2.5 混沌扰动的引入 |
39-41 |
|
4.2.6 精英个体序列库的建立 |
41 |
|
4.2.7 伪并行操作的开展 |
41-42 |
|
4.3 算法的流程 |
42-44 |
|
4.4 改进算法的收敛性 |
44-45 |
|
4.5 改进算法性能验证 |
45-50 |
|
4.5.1 MT10问题 |
45-47 |
|
4.5.2 实际生产问题 |
47-50 |
|
本章小结 |
50-51 |
|
第五章 遗传算法/车间调度研究平台 |
51-72 |
|
5.1 引言 |
51 |
|
5.2 系统概述 |
51-52 |
|
5.3 总体设计 |
52-56 |
|
5.3.1 设计模式 |
52-54 |
|
5.3.2 系统结构 |
54-55 |
|
5.3.3 软件结构 |
55-56 |
|
5.4 通用函数/过程设计 |
56-62 |
|
5.4.1 通用函数/过程一览 |
56-62 |
|
5.5 数据结构设计 |
62-65 |
|
5.5.1 程序数据 |
62-64 |
|
5.5.2 数据文件 |
64-65 |
|
5.6 甘特图控件 |
65-66 |
|
5.7 运行设计 |
66-71 |
|
本章小结 |
71-72 |
|
结论与展望 |
72-75 |
|
参考文献 |
75-79 |
|
攻读学位期间发表的学术论文 |
79-80 |
|
致谢 |
80 |
|
| 【DOI】 | LunWen.ID:2.2008.388171 |
