学位论文 > 优秀研究生学位论文题录展示

启发式算法及其在同顺序流水作业问题中的应用

作　者: 董兴业
导　师: 黄厚宽
学　校: 北京交通大学
专　业: 计算机应用技术
关键词: 调度启发式算法元启发式算法多目标优化流水作业最大完工时间总流程时间
分类号: TP301.6
类　型: 博士论文
年　份: 2008年
下　载: 421次
引　用: 1次
阅　读: 论文下载

内容摘要

对于NP-完全问题,通常不能有效地求得问题的最优解,而是使用启发式算法在可接受的时间内找到问题的尽量好的解。车间调度(shop scheduling)问题具有约束性、非线性、多极小性、大规模性、多目标性等特点,一般属于NP-完全问题,目标解的搜索涉及解空间的组合爆炸。线性规划、分支定界等传统方法对于稍大规模的车间调度问题的求解无能为力,因此,通常使用启发式算法求解。车间调度是一个交叉性研究领域,吸引了运筹学、数学、管理学、决策学、自动化、计算机等领域的众多专家学者,同时,车间调度与控制技术是实现生产高效率、高柔性和高可靠性的关键,有效实用的调度方法和优化技术的研究与应用已成为先进制造技术的基础,因此研究求解车间调度问题的启发式算法有现实意义。本文研究了启发式算法在一类经典的车间调度问题——同顺序流水作业——中的应用,取得的主要研究成果如下:1.针对以最小化最大完工时间为目标的同顺序流水作业,在著名的NEH算法的基础上,提出了一个改进的构造性算法NEH-D。NEH-D算法主要从两点改进了NEH算法:首先使用一个更优的排序规则,在该规则中,不仅考虑了工件的总加工时间,而且考虑了这些加工时间的标准方差;其次,使用了一个消解插入冲突的策略。使用的优先规则有利于改进算法的性能;使用的消解插入冲突的策略对算法性能的改进起关键的作用。实验表明,NEH-D算法的性能优于NEH算法的性能,也优于最近提出的NEHKK算法和NEHKK1算法的性能;2.研究了求解目标为最小化最大完工时间的禁忌搜索算法的几个要素对算法性能的影响。结果表明提出的搜索策略对算法性能有较明显的影响,而提出的禁忌表结构、禁忌状态和不同的初始解对算法的性能没有明显的影响;3.针对以最小化总流程时间为目标的同顺序流水作业,提出了一个迭代局部搜索算法。该算法对初始解不是很敏感:当算法陷于局部极小时,需要对当前最优解做扰动并继续搜索,此时扰动强度对算法的性能有明显的影响。实验表明该算法的性能优于当前已有的算法,且该算法改进了90个基准问题中47个问题的当前最优解;4.针对求解最小化最大完工时间和总流程时间的多目标同顺序流水作业,提出了一个多目标局部搜索算法。针对两个目标,用现有的构造性算法牛成两个解,作为该算法的初始解,然后从这两个初始解出发,以贪婪的方式求出新的Pareto最优解集,持续改进Pareto前沿。选择新的Pareto解的条件是该解既不被原解支配,也不被产生原解的解支配,同时对某个目标改进最大。当所有的解都陷入局部极小时,扰动已得到的Pareto解集,然后从扰动后的解集出发重新搜索。初始解和选择新的Pareto解的方法对算法性能有显著的影响。在基准问题上,与文献中已有算法的比较结果表明提出的算法的总体性能更优,特别是对较大规模的问题,且此差异具有显著性。

全文目录

致谢  5-6
摘要  6-8
Abstract  8-11
目录  11-14
第一章绪论  14-32
  1.1 引言  14-15
  1.2 启发式算法  15-20
    1.2.1 禁忌搜索算法  16-17
    1.2.2 迭代局部搜索算法  17
    1.2.3 蚁群优化算法  17
    1.2.4 变邻域搜索算法  17-18
    1.2.5 遗传算法  18
    1.2.6 模拟退火算法  18-19
    1.2.7 粒子群优化算法  19-20
  1.3 问题描述  20-27
    1.3.1 相关概念及模型概述  21-24
    1.3.2 本文研究的问题  24-27
  1.4 启发式算法在求解流水作业中的发展  27-30
    1.4.1 第一阶段(1955-1964)  27
    1.4.2 第二阶段(1965-1974)  27-28
    1.4.3 第三阶段(1975-1984)  28
    1.4.4 第四阶段(1985-1994)  28
    1.4.5 第五阶段(1995-2004)  28-29
    1.4.6 近几年的发展(2005-)  29-30
  1.5 本文的研究内容及组织  30-32
第二章一个求解同顺序流水作业的构造性算法  32-48
  2.1 引言  32-34
  2.2 几个重要的构造性算法  34-37
    2.2.1 NEH算法  34-35
    2.2.2 NEHKK算法  35-37
    2.2.3 NEHKK1算法  37
  2.3 优先规则  37-39
  2.4 冲突消解策略  39-42
  2.5 改进的启发式算法NEH-D  42
  2.6 实验结果  42-46
  2.7 小结  46-48
第三章求解同顺序流水作业的禁忌搜索算法的优化  48-64
  3.1 引言  48-50
  3.2 预备知识  50-51
  3.3 禁忌搜索算法  51-58
    3.3.1 邻域结构  52-53
    3.3.2 禁忌表结构  53-54
    3.3.3 禁忌状态  54
    3.3.4 搜索策略  54-56
    3.3.5 初始解  56-57
    3.3.6 提出的禁忌搜索算法框架  57-58
  3.4 各要素对算法性能的影响  58-60
  3.5 算法比较  60-62
  3.6 小结  62-64
第四章一个求解同顺序流水作业的迭代局部搜索算法  64-80
  4.1 引言  64-66
  4.2 相关算法  66-68
  4.3 ILS算法  68-73
    4.3.1 提出的ILS算法  69-70
    4.3.2 选择产生初始解的算法  70-72
    4.3.3 选择合适的扰动强度  72-73
  4.4 实验结果  73-78
  4.5 小结  78-80
第五章一个求解多目标同顺序流水作业的局部搜索算法  80-94
  5.1 引言  80-81
  5.2 多目标优化简介  81-82
  5.3 MOLS算法  82-87
    5.3.1 MOLS算法框架  82-83
    5.3.2 选择初始解  83-86
    5.3.3 选择方法  86-87
    5.3.4 排序方法  87
  5.4 实验结果  87-92
  5.5 小结  92-94
第六章关于一篇文献的注  94-102
  6.1 引言  94
  6.2 关于Tasgetiren等人的PSO算法的讨论  94-96
    6.2.1 算法简介  94-96
    6.2.2 PSO_(vns)算法  96
    6.2.3 VNS算法  96
  6.3 实验结果  96-100
  6.4 关于Tasgetiren等人的PSO算法的结论  100-102
第七章总结与展望  102-104
  7.1 本文总结  102-103
  7.2 展望及今后的工作  103-104
附录A Taillard基准问题  104-109
参考文献  109-119
攻读博士期间发表和已录用的学术论文  119-120

启发式算法及其在同顺序流水作业问题中的应用

内容摘要

全文目录

相似论文