| 【中文题名】 | 遗传算法在车间调度中的应用研究 |
| 【英文题名】 | Application Research of Genetic Algorithms in Shop Scheduling |
| 【学科专业】 | 计算数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 智能调度,约束可满足问题,遗传算法,车间调度,, |
| 【英关键词】 | AI Scheduling,Constraint Satisfaction Problem,Genetic Algorithms,Shop scheduling Problem, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
智能调度(AI Scheduling)是人工智能领域的一个重要研究方向，虽然它的起步和智能规划(AI Planning)基本同时(20世纪50年代)，却很晚(20世纪80年代)才受到AI领域研究的足够重视，由于和智能规划问题有很大的相似性和相关性，不少学者也把它作为智能规划方向的一个特例来研究，所以智能规划中大部分成熟的思想和算法如约束满足、启发式搜索、基因算法、神经元网络等都可以成功地解决智能调度问题，使得智能调度在后期的20年取得突飞猛进的发展。
作为智能调度中最难解问题之一的Job-Shop调度问题，其模型具有现实应用问题的一般通用性，如车间调度管理，物流运输、时间表安排以及人力资源规划等问题，正是由于这样的现实意义，所以它的研究持续半个多世纪都没有中断过，而且人们在Job-Shop问题上已经提出很多优秀的算法诸如分支界定、优先级分派规则(Priority Dispatching Rule)、局部搜索(LocalSearch)、启发式(Heuristic)引导以及约束满足(Constraint Satisfaction)等，然而各个算法都存在一定的优缺点。目前调度问题的理论研究成果主要... |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-8 |
|
第一章 引言 |
8-10 |
|
1.1 问题产生的背景 |
8-9 |
|
1.2 本文的结构与重点 |
9-10 |
|
第二章 智能调度研究 |
10-14 |
|
2.1 经典的智能调度 |
10-11 |
|
2.2 智能调度问题模型 |
11-12 |
|
2.3 调度和约束满足(Constraint Satisfaction) |
12-13 |
|
2.4 约束满足方法求解调度问题的局 |
13-14 |
|
第三章 遗传算法研究 |
14-23 |
|
3.1 遗传算法概述 |
14-17 |
|
3.1.1 遗传算法的基本思想 |
14 |
|
3.1.2 遗传算法的基本操作 |
14-16 |
|
3.1.3 遗传算法的基本流程 |
16 |
|
3.1.4 遗传算法的特点 |
16-17 |
|
3.1.5 遗传算法的应用关键 |
17 |
|
3.2 遗传算法的数学基础 |
17-20 |
|
3.2.1 模式定理及其意义 |
18 |
|
3.2.2 积木块假设及其意义 |
18-19 |
|
3.2.3 收敛性分析 |
19 |
|
3.2.4 欺骗性问题 |
19-20 |
|
3.2.5 隐式并行性 |
20 |
|
3.3 遗传算法参数与操作的设计 |
20-22 |
|
3.4 遗传算法的改进 |
22 |
|
3.5 遗传算法的应用 |
22-23 |
|
第四章 Job-Shop问题研究 |
23-26 |
|
4.1 Job-Shop问题的介绍 |
23 |
|
4.2 Job-Shop问题模型 |
23-24 |
|
4.3 Job-Shop问题的复杂性 |
24 |
|
4.4 Job-Shop求解方法的研究 |
24-26 |
|
4.4.1 最优化方法 |
24 |
|
4.4.2 近似/启发式方法 |
24-26 |
|
4.4.2.1 人工智能技术 |
24-25 |
|
4.4.2.2 遗传算法 |
25-26 |
|
第五章 用遗传算法求解车间调度问题 |
26-47 |
|
5.1 基于工件加工(Job Shop)的车间生产调度问题 |
26-27 |
|
5.1.1 车间作业调度问题的抽象化模型描述 |
26 |
|
5.1.2 问题的约束条件 |
26-27 |
|
5.2 模型建立 |
27-28 |
|
技术约束的描述 |
27-28 |
|
5.3 JSP析取图描述及其意义 |
28-29 |
|
5.4 基于遗传算法的模型 |
29-32 |
|
5.4.1 遗传算法的基本流程 |
29-30 |
|
5.4.2 基于操作的编码 |
30 |
|
5.4.2.1 编码算法 |
30 |
|
5.4.2.2 染色体的实际意义 |
30 |
|
5.4.3 解码及活动化解码算法 |
30-31 |
|
5.4.4 基本操作的设计 |
31-32 |
|
5.4.4.1 变异操作 |
31 |
|
5.4.4.2 交叉操作 |
31-32 |
|
5.4.4.3 选择操作 |
32 |
|
5.5 算法设计与实现 |
32-44 |
|
5.5.1 获得最优解的一般算法 |
32 |
|
5.5.2 数据结构与遗传算法参数设计 |
32-33 |
|
5.5.3 主程序设计的伪代码描述 |
33-34 |
|
5.5.4 重要函数的伪代码描述 |
34-44 |
|
5.5.5 存在的问题 |
44 |
|
5.6 快速获得较优解的一个设想及其实现方法 |
44-46 |
|
5.6.1 遗传算法的一个结论 |
44 |
|
5.6.2 贪婪法思想的启发 |
44 |
|
5.6.3 将贪婪法思想用于该问题的一个设想 |
44-45 |
|
5.6.4 主程序设计的伪代码描述 |
45-46 |
|
5.6.5 函数设计的伪代码描述 |
46 |
|
5.7 小结 |
46-47 |
|
第六章 问题的总结与展望 |
47-50 |
|
6.1 问题总结 |
47 |
|
6.2 研究展望 |
47-50 |
|
参考文献 |
50-51 |
|
致谢 |
51 |
|
| 【DOI】 | LunWen.ID:2.2008.388825 |
