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

部分机器分批的平行机在线排序

作　者: 姚青华
导　师: 李文华
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 平行机排序按时在线排序平行分批竞争比下界
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 1次
引　用: 0次
阅　读: 论文下载

内容摘要

关于两台恒同机器的排序问题,在分批排序和经典排序中,大多数文献都是考虑或者两台机器都是批处理机（批容量无界）或者两台机器都是正常机器（任何时刻最多只能加工一个工件,即批容量为1）。在本文中,我们考虑了两台恒同机器的在线排序问题,但是我们主要考虑第一台机器M₁是平行批处理机,而第二台机器M₂是正常机器。第二章我们研究的在线排序问题可以描述为:有两台恒同机;工件信息（到达时间和加工时间）在排序之初未知,而是随着时间的推移而逐个到达;目标是最小化两台机器上工件的最大完工时间。采用Graham等人[21]提出的排序问题的一般记号,这个问题记为我们首先利用对手法构造一个实例证明了该问题竞争比的下界为1+α。接着提供了一个竞争比为2在线算法。第三章我们研究的在线排序问题可以描述为:有两台恒同机;工件之间的序约束关系是平行链;工件链一旦到达,该链上所有工件的信息才可知;所有工件的长度都相同（即为p）;目标是最小化两台机器上工件的最大完工时间。采用Graham等人[21]提出的排序问题的一般记号,这个问题记为我们首先利用对手法构造一个实例证明了该问题竞争比的下界为1+α。接着我们给出该问题一个最好可能的在线算法。

全文目录

摘要  4-5
Abstract  5-7
第一章绪论  7-13
  §1.1 排序的介绍  7-9
  §1.2 在线排序、在线算法和分批排序  9-11
  §1.3 工件之间的序约束  11
  §1.4 本文主要结果  11-13
第二章一台机器为批处理机的两台平行机在线排序  13-25
  §2.1 相关介绍  13-15
  §2.2 问题竞争比的下界  15
  §2.3 问题的一个在线算法  15-25
第三章链组约束下部分批处理平行机在线排序  25-34
  §3.1 相关介绍  25-26
  §3.2 问题竞争比的下界  26-27
  §3.3 问题的一个最好可能的在线算法  27-34
后记  34-35
参考文献  35-38
致谢  38

部分机器分批的平行机在线排序

内容摘要

全文目录

相似论文