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

有服务等级约束的平行机排序问题

作　者: 耿志超
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 平行机服务等级约束近似算法在线排序竞争比
分类号: O223
类　型: 硕士论文
年　份: 2008年
下　载: 4次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究了有服务等级约束的平行机排序问题。所谓服务等级约束指的是:机器和工件都被标注了服务等级,只有当一个工件的服务等级不低于一台机器的服务等级时,这个工件才能在该台机器上加工。有服务等级约束的平行机排序问题的实际背景是服务业中推行的等级差异服务。全文共分三章。第一章是绪论部分,共有三节。其中,前三节介绍了排序问题产生的背景、排序论的发展现状以及与排序问题有关的一些基本概念;第四节介绍了本文所考虑的排序问题的实际背景、相关文献以及本文的主要结果。第二章主要研究m台同型机上有服务等级约束的排序问题的近似算法。在机器数m固定的情况下,我们给出了一个完全多项式时间近似方案(FPTAS)和一个多项式时间近似方案(PTAS)。第三章主要研究三台同型机上有服务等级约束的在线排序问题。当工件允许中断时,我们证明了问题的竞争比下界是5/3,并给出了一个竞争比为2的在线算法;当工件不允许中断时,我们证明了问题的竞争比下界是9/5,并给出了一个竞争比为11/5的在线算法。

全文目录

摘要  3-4
Abstract  4-6
第一章绪论  6-13
  §1.1 排序问题  6-8
  §1.2 近似算法和最坏情形比  8-9
  §1.3 在线排序、在线算法和竞争比  9-10
  §1.4 相关文献和本文主要结果  10-13
第二章有服务等级约束的同型机排序问题的近似算法  13-23
  §2.1 问题Pm|GOS|C_(max)的一个完全多项式时间近似方案  13-17
  §2.2 问题Pm|GOS|C_(max)的一个多项式时间近似方案  17-23
第三章三台同型机上有服务等级约束的在线排序问题  23-34
  §3.1 工件允许中断的情形  23-29
  §3.2 工件不允许中断的情形  29-34
后记  34-35
参考文献  35-38
致谢  38

有服务等级约束的平行机排序问题

内容摘要

全文目录

相似论文