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

一类分装式排序问题的计算方法和计算复杂性研究

作　者: 胡荣
导　师: 吕绪华
学　校: 武汉科技大学
专　业: 应用数学
关键词: 复合并行机分装式流水作业 NP--完全问题分支定界算法启发式算法
分类号: O223
类　型: 硕士论文
年　份: 2006年
下　载: 58次
引　用: 0次
阅　读: 论文下载

内容摘要

排序问题是一类重要的组合最优化问题。在经典排序问题中,通常假设工件不能同时在不同的机器上加工,但随着并行计算机和生产柔性化的出现,工件可以同时在多台机器上加工,因此产生了可同时加工的现代排序问题。可同时加工排序是一类重要的新型排序,有着广泛的实际背景。本文研究了生产系统中的一种特别类型的可同时加工条件下的现代排序问题----分装式流水作业复合并行机排序问题(简记为TMF)。论文第一、二章在阐述排序问题概念的基础上,对相关排序问题的研究现状进行了回顾;第二章证明了该排序问题是NP--完全问题,没有多项式时间算法;第三章给出了该问题的分支定界算法;第四章对于某些特殊情况下零件的最优加工次序作了证明;第五章设计了求解该问题的三个启发式算法,分析证明了启发式算法在最坏情况下的品性及其可达性,文章的最后编制了求解该问题的计算机程序。

全文目录

摘要  3-4
ABSTRACT  4-7
第一章绪论  7-10
  1.1 引言  7
  1.2 经典排序与现代排序  7-8
  1.3 本文研究的主要内容和结构  8-10
第二章相关排序问题的研究现状  10-14
  2.1 平行机排序问题  10-11
  2.2 复合并行机排序问题  11
  2.3 流水作业排序  11-12
  2.4 装配式流水作业排序  12-14
第三章分装式流水作业排序问题的计算复杂性  14-17
  3.1 分装式流水作业排序问题加工模型的定义  14
  3.2 分装式流水作业排序问题的NP--完全问题的证明  14-17
第四章 F'2|m_1=1,m_2≥2|C_(max) 的分支定界算法  17-21
  4.1 定界  17-18
  4.2 分支  18-19
  4.3 分支定界算法  19-21
第五章特殊类型的F'2|m_1=1,m_2 ≥2|C_(max) 多项式时间算法  21-26
第六章求解F'2|m1=1,m_2≥2|C_(max) 的三个启发式算法  26-32
  6.1 启发式算法1  26-27
    6.1.1 LS 算法  26
    6.1.2 LS 算法的最坏情况品性分析  26
    6.1.3 算法性能比的上界的可达性证明  26-27
  6.2 启发式算法H_1  27-30
    6.2.1 启发式算法H_1  27-28
    6.2.2 启发式算法H_1 的最坏情况下性能比分析  28-29
    6.2.3 启发式算法H_1 的应用实例  29-30
  6.3 启发式算法H_2  30-32
    6.3.1 算法H_2  30
    6.3.2 启发式算法H_2 应用实例  30-32
第七章结论  32-33
参考文献  33-36
附录计算机程序  36-38
致谢  38-39
作者在学期间发表的论文  39

一类分装式排序问题的计算方法和计算复杂性研究

内容摘要

全文目录

相似论文