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

误工排序问题的推广及其最优性的证明

作　者: 苏永英
导　师: 唐国春
学　校: 重庆师范大学
专　业: 运筹学与控制论
关键词: 排序误工算法最优性
分类号: O223
类　型: 硕士论文
年　份: 2010年
下　载: 14次
引　用: 0次
阅　读: 论文下载

内容摘要

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,它是排序论中最基本的问题之一,具有重要的理论意义和实用价值。本文研究误工排序问题的推广,研究这些问题的算法和改进。本文第一章,综述了排序论的学术意义和排序问题的研究概况。本文第二章,介绍了排序问题的一些基础知识。本文第三章,首先研究研究求解工件的就绪时间不相同、但是与交货期有“一致性”关系时,使误工工件的个数为最少的误工问题1 |(ri≤rj)=>(di≤dj)|∑Uj。1978年Kise、Ibaraki和Mine提出算法(简称为KIM算法),证明他们提出的KIM算法可以得到这个误工问题的最优解。最近李杉林、陈志龙、唐国春用反例指出他们证明最优性时提出的引理2是错误的,孙叶平、唐国春用新的方法证明KIM算法的最优性。本文继续孙叶平的研究,补充和完善引理2,并且给出各种情况下KIM算法最优性的证明。在此基础上,又分析和研究了求解其他几种推广的误工排序问题的算法,并给出了相应的证明。比如研究求解在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的误工排序问题1 |T|∑Uj的Sidney算法,把Sidney算法修改成一个简洁的形式并给出其最优性的一个新证明；研究了工件的就绪时间可以不相同、但是与交货期有“一致性”关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使误工工件的个数为最少的推广的误工排序问题1 |T,(ri≤rj)=>(di≤dj)|∑Uj,提出该问题的最优算法,并且证明提出的算法得到的排序是最优排序。本文第四章,对全文作了一个总结,并提出了一些有待研究的问题。

全文目录

中文摘要  4-5
英文摘要  5-8
1 绪论  8-11
  1.1 课题的学术和应用意义  8
  1.2 国内外现状综述  8-9
  1.3 本文研究的目的和研究内容  9-11
2 基础知识  11-17
  2.1 排序问题的定义  11-12
  2.2 机器的分类  12
  2.3 输入参数  12
  2.4 输出数据  12-13
  2.5 排序问题三参数表示  13-15
  2.6 排序问题的求解  15-17
3 推广的误工排序问题  17-36
  3.1 误工排序问题1|(r_i≤r_j)=>(d_i≤d_j)|∑U_j  17-25
    3.1.1 KIM算法及其引理2  17-18
    3.1.2 补充和完善修改后的引理2’的各种情况  18-24
    3.1.3 KIM算法仍然可以得到最优解  24-25
  3.2 误工排序问题1|T|∑U_j  25-29
    3.2.1 误工排序问题1|T|∑U_j的几个引理  25-26
    3.2.2 Sidney算法及其最优性证明  26-29
  3.3 一般的误工排序问题1|T,(r_i≤r_j)=>(d_i≤d_j)|∑U_j  29-36
    3.3.1 误工排序问题1|T,(r_i≤r_j)=>(d_i≤d_j)|∑U_j的性质和算法  29-33
    3.3.2 误工排序问题1|T,(r_i≤r_j)=>(d_i≤d_j)|∑U_j算法的最优性证明  33-36
4 总结与讨论  36-37
参考文献  37-39
附录A 作者在攻读硕士学位期间发表的论文目录、科研情况  39-40
致谢  40-41

误工排序问题的推广及其最优性的证明

内容摘要

全文目录

相似论文