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

最大化按时完工工件个数的单位长度工件的单机在线分批排序问题

作　者: 李文杰
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 在线排序 必须交货期 Lookahead 平行分批
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 3次
引　用: 0次
阅　读: 论文下载
 

内容摘要


本文研究在Lookahead作用下的单位长度工件的单机在线平行分批排序问题.目标函数为求最大按时完工工件个数。平行分批是指,多个工件可以组成一批同时加工,而每一批的加工时间等于该批中工件的最长加工时间。我们用b=∞和b＜∞分别表示批容量无限制和有限制。LK_L模型是指,在一时刻点t,在线算法可以预见在时间段(t,t+L)内将要到达工件的全部信息。本文的主要结果如下。(1)当0≤L＜1时,我们证明了一个简单的贪婪在线算法是最好可能的在线算法.该算法的竞争比为1/min{n,b+1},其中n表示工件个数。这意味Lookahead在这种情形下是没有任何帮助的。(2)当1≤L＜2时,对b=∞和b＜∞本文分别给出了问题的上界为0.39和2/3。同时我们设计了一个批延迟在线算法,并证明该算法的竞争比分别为1/4(b=∞时)和1/5(b＜∞时)。

全文目录


摘要  4-5
Abstract  5-7
第一章 引言  7-11
  §1.1 问题的背景及相关结果  7-10
  §1.2 本文主要结果  10-11
第二章 最大化按时完工工件个数的单位长度工件的单机在线分批排序问题  11-26
  §2.1 问题提出及预备知识  11-12
  §2.2 0≤L  12-15
  §2.3 1≤L  15-26
后记  26-27
参考文献  27-30
致谢  30

相似论文

  1. 工件可拒绝的在线排序问题的两个模型,O223
  2. 部分机器分批的平行机在线排序,O223
  3. 链组约束下的平行机在线排序,O223
  4. 两类特殊的在线分批排序问题,O223
  5. 两类加权幂和形式的分批排序问题,O223
  6. 与双目标分批排序相关的排序问题,O223
  7. 带有不可相容工件组的在线排序问题,O223
  8. 带有运输时间的在线排序问题,O223
  9. 有服务等级约束的平行机排序问题,O223
  10. 机器有准备时间的平行机半在线排序,O223
  11. 链组约束下的平行机排序问题,O223
  12. 关于重新排序问题的研究,O223
  13. 特殊并行工件排序的研究,O223
  14. 几类分批排序和在线排序问题的复杂性,O223
  15. 单机分批排序和平行机在线排序问题,O223
  16. 允许重启的平行分批在线排序问题,O223
  17. 带有运输的单机平行分批在线排序问题,O223
  18. 两类可拒绝同类机排序问题,O223
  19. 分批排序问题及带机器准备时间的同类机排序问题,O223
  20. 具有多处理器任务的固定工件在线排序问题研究,O223

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