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

典型车间调度问题中的算法理论分析

作　者: 白丹宇
导　师: 唐立新
学　校: 东北大学
专　业: 系统工程
关键词: 车间调度启发式理论分析渐近分析最坏情况分析
分类号: F273
类　型: 博士论文
年　份: 2010年
下　载: 62次
引　用: 0次
阅　读: 论文下载

内容摘要

车间调度问题是指被调度的工件需要在不同的机器上进行加工,每台机器同时最多只能加工一个工件,而每个工件同时也最多只能在一台机器上加工,工件的加工不允许中断,问题是确定工件在机器上的加工顺序和时间,使得目标函数最优化。由于车间调度问题广泛存在于制造业和物流系统中,而且大多数车间调度问题都是NP难的,因此探讨问题的启发式进行近似求解成为学术界和工业界的主要研究手段。如何从理论上分析和评价启发式的性能是调度领域具有挑战性的研究课题。本文对流水车间和开放车间两类典型车间调度模型进行了研究,分别设计了新的启发式并从理论上对这些启发式进行了渐近分析,针对问题已有的一些典型启发式从理论上进行了渐近分析和最坏情况分析(离线)或最坏竞争分析(在线)。最后通过数值实验仿真验证了所分析的调度启发式的性能。具体内容概括如下：1)针对流水车间最小化最大完工时间问题,提出了单个工件优先(SJF)启发式,并证明了当问题规模趋近于无穷大时该启发式是渐近最优的。为了进一步从数值上对提出的启发式进行评价,提出了一个新的下界,证明了该下界的渐近最优性,并指出其最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真与所提出的下界进行比较,验证了SJF启发式的渐近最优性。2)针对带有释放时间的流水车间最小化最大完工时间问题,提出了动态单个工件优先(DSJF)启发式,并证明了当问题规模趋近于无穷大时该启发式是渐近最优的。从DSJF启发式渐近最优性的证明过程,又得到了先来先服务(FCFS)规则也是渐近最优的推论。对于该问题,提出了一个新的下界,证明了该下界的渐近最优性,并指出其最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真验证了DSJF启发式的渐近最优性和新下界的性能。3)针对流水车间最小化总加权完工时间问题,提出了一个新的下界,并对该下界的性能进行了理论分析。理论分析分为渐近分析和最坏情况分析两个方面：在渐近分析方面,证明了当问题规模趋近于无穷大时,新下界是渐近最优的；在最坏情况分析方面,新下界的最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真验证了新下界的性能。4)针对带有释放时间的流水车间最小化完工时间平方和问题,应用两个典型在线启发式求解该问题,第一个启发式是首台机器最短可用加工时间优先(SPTA-F)策略；第二个启发式是平均最短可用加工时间优先(SPTA-A)策略。通过理论分析,证明了当问题规模趋近于无穷大时这两个启发式都是渐近最优的,并指出SPTA-F启发式的最坏竞争比是无界的,而SPTA-F启发式的最坏竞争比为机器数的平方m2,且为紧界。对于该问题,经过对两个下界性能的分析,提出了一个渐近最优的新下界。最后,通过数值实验仿真验证了两个启发式的渐近最优性和新下界的性能。5)针对开放车间最小化最大完工时间问题,证明了典型启发式循环排序(RS)策略的渐近最优性,并指出该启发式的最坏情况比为机器数m,且为紧界。为了进一步改进RS启发式求解中等规模问题的性能,提出了基于RS的MRS启发式。最后,通过数值实验仿真验证了RS启发式的渐近最优性和MRS启发式的性能。6)针对带有释放时间的开放车间最小化最大完工时间问题,证明了当问题规模趋近于无穷大时,典型启发式紧排序(DS)策略是渐近最优的。为了进一步改进DS启发式求解中等规模问题的性能,提出了基于DS的动态最短加工时间优先—紧排序(DSPT-DS)启发式。最后,通过数值实验仿真验证了DSPT-DS启发式的性能。7)针对开放车间最小化总完工时间问题,提出了最短加工时间分块(SPTB)启发式,并证明了当问题规模趋近于无穷大时,SPTB启发式是渐近最优的。最后,通过数值实验仿真验证了SPTB启发式的渐近最优性,进一步的计算结果表明了所提出启发式的性能优于此问题的典型匹配算法。

全文目录

摘要  6-8
Abstract  8-11
目录  11-15
第一章绪论  15-33
  1.1 调度问题的概述  15
  1.2 调度问题的定义  15-19
  1.3 调度问题的求解方法  19-20
  1.4 求解调度问题的算法及其性能分析  20-22
    1.4.1 调度算法  20
    1.4.2 评价算法性能的主要方法  20-22
  1.5 相关调度问题的研究现状  22-29
    1.5.1 调度算法之渐近分析与概率分析的研究现状  22-24
    1.5.2 车间调度问题的研究现状  24-28
    1.5.3 本文的创新点  28-29
  1.6 本文的研究路线及主要工作  29-33
    1.6.1 本文的研究路线  29
    1.6.2 本文的主要工作  29-33
第二章流水车间最小化最大完工时间问题  33-43
  2.1 引言  33
  2.2 符号与定义  33-35
  2.3 SJF启发式  35-36
  2.4 SJF启发式的渐近性能分析  36-38
  2.5 Fm||C_(max)问题的新下界  38-41
  2.6 数值仿真实验  41-42
  2.7 本章小结  42-43
第三章带有释放时间的流水车间最小化最大完工时间问题  43-55
  3.1 引言  43
  3.2 符号与定义  43-44
  3.3 FCFS规则与DSJF启发式  44-45
  3.4 DSJF启发式和FCFS规则的渐近竞争分析  45-47
  3.5 Fm|r_j|C_(max)问题的新下界  47-50
  3.6 数值仿真实验  50-53
    3.6.1 DSJF启发式实验结果  51-52
    3.6.2 下界LB3.3实验结果  52-53
  3.7 本章小结  53-55
第四章流水车间最小化总加权完工时间问题的新下界  55-65
  4.1 引言  55-56
  4.2 符号与定义  56-57
  4.3 Fm||∑w_jC_j问题的相关结论  57-58
  4.4 新下界及其渐近性能分析  58-59
  4.5 新下界的最坏情况分析  59-61
  4.6 数值仿真实验  61-64
    4.6.1 测试一  62-63
    4.6.2 测试二  63-64
  4.7 本章小结  64-65
第五章带有释放时间的流水车间最小化完工时间平方和问题  65-81
  5.1 引言  65-66
  5.2 符号与定义  66-67
  5.3 带有释放时间的单机完工时间平方和问题  67-68
  5.4 SPTA-F启发式及其性能分析  68-71
    5.4.1 SPTA-F启发式的渐近竞争分析  69-70
    5.4.2 SPTA-F启发式的最坏竞争分析  70-71
  5.5 SPTA-A启发式及其性能分析  71-74
    5.5.1 SPTA-A启发式的渐近竞争分析  72-73
    5.5.2 SPTA-A启发式的最坏竞争分析  73-74
  5.6 Fm|r_j|∑C_j~2问题的新下界  74-78
  5.7 数值仿真实验  78-80
  5.8 本章小结  80-81
第六章开放车间最小化最大完工时间问题  81-95
  6.1 引言  81
  6.2 符号与定义  81-82
  6.3 RS启发式简介  82-84
  6.4 RS启发式的渐近性能分析  84-87
  6.5 RS启发式的最坏情况分析  87-89
  6.6 改进的RS启发式  89-90
  6.7 数值仿真实验  90-94
    6.7.1 测试一  91-92
    6.7.2 测试二  92-94
  6.8 本章小结  94-95
第七章带有释放时间的开放车间最小化最大完工时间问题  95-105
  7.1 引言  95
  7.2 符号与定义  95-96
  7.3 紧排序及其相关结论  96-98
  7.4 DS启发式的渐近竞争分析  98-100
  7.5 DSPT-DS启发式  100-102
  7.6 数值仿真实验  102-104
    7.6.1 测试一  103-104
    7.6.2 测试二  104
  7.7 本章小结  104-105
第八章开放车间最小化总完工时间问题  105-117
  8.1 引言  105
  8.2 符号与定义  105-106
  8.3 SPTB启发式介绍  106-109
    8.3.1 特殊情况  106-108
    8.3.2 一般情况  108-109
  8.4 SPTB启发式的渐近性能分析  109-113
    8.4.1 特殊情况  109-112
    8.4.2 一般情况  112-113
  8.5 数值仿真实验  113-116
    8.5.1 测试一  113-115
    8.5.2 测试二  115-116
  8.6 本章小结  116-117
第九章结束语  117-119
参考文献  119-129
致谢  129-130
作者博士期间撰写的论文  130-132
作者博士期间科研情况  132-133
个人简历  133

典型车间调度问题中的算法理论分析

内容摘要

全文目录

相似论文