| 【中文题名】 | 基于智能计算的车间作业调度研究 |
| 【英文题名】 | The Research of Job Shop Scheduling Problem Based on Intelligence Computation |
| 【学科专业】 | 控制工程 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-11-6 |
| 【中关键词】 | 车间作业调度,遗传算法,蚁群算法,粒子群优化,不可行调度, |
| 【英关键词】 | job shop scheduling problem,genetic algorithm,ant colony algorithm,particle swarm optimization,unfeasible scheduling, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
车间作业调度问题(JSP)是生产管理和组合优化领域的重要研究内容。合理地安排生产与调度对提高生产效率，减少生产成本，改进产品质量起着非常重要的作用。车间作业调度问题属于NP-complete类，对它的学术研究始于1954年，迄今为止，已经有很多关于该问题的研究方法，如分支界定方法、动态规划方法、移动颈瓶方法、拉格朗日松弛法和禁忌搜索方法等。
本文在求解车间作业调度问题时，分别采用遗传算法、蚁群算法和粒子群优化算法等三种智能计算。
首先提出基于先后表编码的求解JSP的遗传算法，在分析车间作业调度问题的数学模型的基础上，给出了：(1)死锁问题及其解决方法；(2)生成可行调度的算法；(3)计算调度目标函数的算法；(4)三种遗传算子及其辅助算子—修正算子的设计。在车间作业调度(JSP)问题中，存在着大量的不可行调度解，严重影响了遗传算法查找最优调度的质量。通过JSP问题数学模型的图论形式，深入分析了不可行调度产生的原因及其特征，得出了一个调度是可行调度的充要条件。提出了遗传算法求解JSP的基于操作的编码方法，能够彻底避免产生不可行调度解，大大提高了遗传算法的质量。
其次设计了专门的蚁... |
| 【论文题纲】 |
|
摘要 |
5-7 |
|
ABSTRACT |
7-11 |
|
第一章 绪论 |
11-20 |
|
1.1 研究的目的与意义 |
11-12 |
|
1.2 车间作业调度问题 |
12-18 |
|
1.2.1 车间作业调度问题的数学模型 |
12-13 |
|
1.2.2 JSP性能指标的正规性、等价性和活动调度 |
13-15 |
|
1.2.3 车间作业调度的优化算法综述 |
15-18 |
|
1.3 论文的研究工作 |
18-20 |
|
第二章 智能计算方法概述 |
20-36 |
|
2.1 遗传算法 |
20-26 |
|
2.1.1 遗传算法的形成和发展 |
20 |
|
2.1.2 遗传算法的基本思想 |
20-22 |
|
2.1.3 遗传算法的买现 |
22-24 |
|
2.1.4 遗传算法的特点 |
24-25 |
|
2.1.5 遗传算法的应用情况 |
25-26 |
|
2.2 蚁群算法 |
26-32 |
|
2.2.1 蚁群算法的背景 |
26-27 |
|
2.2.2 蚁群算法的原理 |
27-29 |
|
2.2.3 蚁群算法的实现 |
29-30 |
|
2.2.4 基本蚂蚁算法的流程 |
30-31 |
|
2.2.5 蚁群算法的特点 |
31-32 |
|
2.2.6 蚁群算法的应用 |
32 |
|
2.3 粒子群优化算法 |
32-36 |
|
2.3.1 基本粒子群算法的描述 |
32-34 |
|
2.3.2 算法流程 |
34-35 |
|
2.3.3 粒子群算法的特点 |
35 |
|
2.3.4 粒子群算法的应用 |
35-36 |
|
第三章 遗传算法求解车间作业调度 |
36-51 |
|
3.1 遗传算法求解 JSP的编码研究 |
36-37 |
|
3.2 基于先后表编码的遗传算法求解JSP |
37-44 |
|
3.2.1 个体(染色体)编码 |
38-39 |
|
3.2.2 死锁及解决方法 |
39-40 |
|
3.2.3 初始解群的生成 |
40-41 |
|
3.2.4 个体的适应度函数 |
41-42 |
|
3.2.5 遗传算子的设计 |
42-43 |
|
3.2.6 算法仿真 |
43-44 |
|
3.3 不可行调度问题解决方法 |
44-51 |
|
3.3.1 车间作业调度数学模型的图论形式 |
44-45 |
|
3.3.2 不可行调度分析 |
45-46 |
|
3.3.3 基于操作的编码的遗传算法 |
46-49 |
|
3.3.4 算法仿真 |
49-51 |
|
第四章 蚁群算法求解车间作业调度 |
51-57 |
|
4.1 Job-shop调度问题的析取图模型 |
51 |
|
4.2 求解 Job Shop调度问题的蚁群算法 |
51-57 |
|
4.2.1 Job Shop调度问题的蚁群算法的模型 |
51-53 |
|
4.2.2 最早开始加工时间 |
53-54 |
|
4.2.3 算法的改进 |
54-55 |
|
4.2.4 算法流程 |
55-57 |
|
第五章 粒子群优化算法求解车间作业调度问题 |
57-65 |
|
5.1 设计粒子表示方法的关键问题 |
57-59 |
|
5.2 基于操作和粒子位置的编码方法 |
59-61 |
|
5.2.1 粒子编码 |
59-60 |
|
5.2.2 求解Job Shop调度的粒子群算法步骤 |
60-61 |
|
5.3 基于操作的编码方法的离散粒子群优化算法 |
61-62 |
|
5.4 不同粒子表示的PSO的性能比较 |
62-65 |
|
第六章 算法仿真和参数分析 |
65-70 |
|
6.1 算法仿真和比较 |
65-67 |
|
6.2 粒子群算法的参数分析 |
67-70 |
|
第七章 结论和展望 |
70-71 |
|
7.1 本文的创新点 |
70 |
|
7.2 今后工作展望 |
70-71 |
|
参考文献 |
71-74 |
|
致谢 |
74-75 |
|
攻读学位期间发表的学术论文目录 |
75 |
|
| 【DOI】 | LunWen.ID:2.2008.389201 |
