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

工件可拒绝的在线排序问题的两个模型

作　者: 步海林
导　师: 蒲利群
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 在线排序 平行分批 单机排序 同型机 竞争比 下界
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 10次
引　用: 0次
阅　读: 论文下载
 

内容摘要


在经典的排序问题中,总是假设工件信息在排序之初都已经全部知道。在实际应用中,工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个到达。这就是我们在此文中所要研究的有到达时间的在线排序问题（on-line-over-time）。带拒绝费用的平行机排序问题,由Bartal等人最先提出并研究。其目标是最小化最大完工时间与所有被拒绝工件的罚值之和。对列表在线情形,他们给出一个竞争比2+α的最好可能的在线算法。一般来说,单机平行分批排序和多台同型机排序之间存在密切的联系。文中,我们考虑单机批容量无界和两台同型机环境下的两个在线模型。我们可以用三参数法表示这两个模型为1丨on-line,p-batch,b=∞,lj=upj丨w,P2丨on-line,rj,lj=upj丨w,其中u∈（0,1）,w=max{ri,cj}+P（R）。文章的主要结果,是用H∞算法和AR算法对前述模型分别进行分析得出的。对单机批容量无界情形,H∞算法的竞争比是（1+α）/u;对两台同型机情形,AR算法的竞争比是1+2u。本文中,我们还使用对手方法构造实例,得到上述两个模型的下界。

全文目录


摘要  4-5
Abstract  5-7
第一章 绪论  7-18
  §1.1 排序论简介  8-13
  §1.2 排序问题的记法  13-14
  §1.3 相关文献综述及主要结果  14-18
第二章 带到达时间和拒绝费用的单机平行分批在线排序  18-27
  §2.1 问题的相关介绍与分析  19-21
  §2.2 H~∞算法  21-23
  §2.3 算法分析  23-27
第三章 带有到达时间和拒绝费用的的两台同型机在线排序问题  27-33
  §3.1 问题的综述和相关介绍  28
  §3.2 问题的下界  28-30
  §3.3 AR算法及其上界分析  30-33
后记  33-34
参考文献  34-36
致谢  36

相似论文

  1. 无人机视觉着陆引导中的位姿估计问题研究,V249.32
  2. 一类紧致黎曼流形的特征值问题研究,O186.12
  3. 工件带有优先约束的平行机在线排序问题,O223
  4. 最大化按时完工工件个数的单位长度工件的单机在线分批排序问题,O223
  5. 部分机器分批的平行机在线排序,O223
  6. 等长工件序约束下分批在线排序,O223
  7. 一类连分数的线性型下界研究和几类代理签名方案设计,TN918.1
  8. 连分数对数的线性型下界与基于身份的签名的研究,TN918.1
  9. 布尔函数的代数免疫度和扩展代数免疫度,TN918.1
  10. 带进位反馈移位寄存器的相关问题,TN918.1
  11. 链组约束下的平行机排序问题,O223
  12. 链组约束下的平行机在线排序,O223
  13. 两类特殊的在线分批排序问题,O223
  14. 机器有准备时间的平行机半在线排序,O223
  15. 两类加权幂和形式的分批排序问题,O223
  16. 有服务等级约束的平行机排序问题,O223
  17. 具有学习与退化效应的排序问题,O223
  18. 与双目标分批排序相关的排序问题,O223
  19. 带有运输时间的在线排序问题,O223
  20. 带有不可相容工件组的在线排序问题,O223
  21. 具有前瞻区间的分批在线排序问题,O223

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com