| 【中文题名】 | 共生遗传算法求解作业调度研究 |
| 【英文题名】 | |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-11-6 |
| 【中关键词】 | 遗传算法,共生算法,作业调度,流程设计,柔性, |
| 【英关键词】 | genetic algorithm （GA）,symbiotic evolutionary algorithm,job shop scheduling problem （JSP）,process planning,flexibility, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 车间作业调度问题是制造系统的一个研究热点，在理论研究方面也是最为困难的问题之一，此问题具有约束性，非线性，不确定性和大规模性，已被证明调度问题是NP-hard问题，很难求得最优解。人们研究和发展了多种优化算法来处理此类问题：比如模拟退火，遗传算法，禁忌搜索，神经网络等。这些优化方法模拟或运用自然现象，过程和规律而得到发展，其思想涉及数学，物理，人工智能等多个学科。
在车间作业调度的过程中，要根据生产目标和约束条件，为每个加工对象确定具体的加工路径以及各具体操作的执行机器和时间。传统的作业调度问题的提法是：n个工件(job)要在m台机器上加工，每个工件需要经过m道工序(operation)，每道工序可能要求不同的机器。问题的目标是求n个工件在每台机器上最优的加工顺序，使最大流程时间达到最小。当然还有其他一些变种，比如规定n个工件在m台机器上的加工顺序相同或不同。传统的作业调度一般假定对每个工件只有一个可行的加工方案，即作业处理计划中没有柔性，而在现在的制造系统中，出现了各种作业柔性。大多数工件(job)具有大量的柔性加工方式和工序。即可以选择不同的工序序列来完成加工此工件，同时实现某个工序存在由... |
| 【论文题纲】 |
|
摘要 |
6-8 |
|
ABSTRACT |
8-10 |
|
第1章 绪论 |
10-21 |
|
1. 遗传算法简介 |
10-16 |
|
1.1 遗传操作 |
12-15 |
|
1.2 共生遗传算法 |
15 |
|
1.3 遗传算法与传统优化算法的比较 |
15-16 |
|
2. 作业调度问题综述 |
16-19 |
|
2.1 传统作业调度问题 |
17-18 |
|
2.2 调度问题的分类 |
18-19 |
|
3. 基于遗传算法的作业车间调度问题求解的一般过程 |
19-20 |
|
4. 论文的组织和创新之处 |
20-21 |
|
第2章 柔性作业调度问题说明 |
21-24 |
|
1. 含柔性的作业调度问题 |
21 |
|
2. 三种类型的柔性 |
21-22 |
|
3. 柔性作业调度问题的描述 |
22-24 |
|
第3章 共生算法求解 JSP算法设计及实现框架 |
24-35 |
|
1. 邻域 |
24 |
|
2. 共生算法设计 |
24-26 |
|
3. 编码方法 |
26-27 |
|
3.1 流程设计染色体编码 |
26 |
|
3.2 作业调度染色体编码 |
26-27 |
|
4. 种群的初始化 |
27 |
|
5. 解码方法 |
27-28 |
|
5.1 流程设计染色体的编码解码方法 |
27 |
|
5.2 作业调度染色体的编码解码方法 |
27-28 |
|
6. 交叉方法 |
28-30 |
|
6.1 一点交叉变体 |
28-29 |
|
6.2 两点交叉变体 |
29 |
|
6.3 MSX方法 |
29-30 |
|
6.4 交叉替换的方式 |
30 |
|
7. 变异方法 |
30-31 |
|
7.1 流程设计染色体的变异 |
30-31 |
|
7.2 作业调度染色体的变异 |
31 |
|
8. 本文中共生算法实现说明 |
31-34 |
|
8.1 算法实现了中类说明 |
31-34 |
|
8.2 类之间的组合关系 |
34 |
|
9. 本章小节 |
34-35 |
|
第4章 本文共生算法所做的改进及研究内容 |
35-48 |
|
1. 新适应度函数的计算定义 |
35-39 |
|
1.1 要比较的适应度函数的定义:适应度函数1 |
35-36 |
|
1.2 新的适应度函数:适应度函数2 |
36 |
|
1.3 新提出的适应度函数fitness2定义优越 |
36-39 |
|
2. 所要测试多种因素对共生算法效率和结果的影响 |
39-46 |
|
2.1 交叉方法的性能比较 |
40-41 |
|
2.2 选择的邻域大小对共生算法进化速度及结果的影响 |
41-44 |
|
2.3 随机和轮盘赌自适应选择母体策略 |
44-46 |
|
3. 并行调度算法 |
46-47 |
|
3.2 算法结果 |
47 |
|
4. 本章小节 |
47-48 |
|
第5章 总结和结论 |
48-49 |
|
附录 |
49-54 |
|
参考文献 |
54-58 |
|
致谢 |
58-59 |
|
攻读学位期间发表的学术论文和参加的工作 |
59-60 |
|
学位论文评阅及答辩情况表 |
60 |
|
| 【DOI】 | LunWen.ID:2.2008.388130 |
