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

带服务器的平行机排序问题的两个近似算法

作　者: 周颖
导　师: 苏纯洁
学　校: 华东理工大学
专　业: 应用数学
关键词: 排序平行机服务器近似算法最坏情况界
分类号: O223
类　型: 硕士论文
年　份: 2012年
下　载: 19次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究的是带一个服务器的平行机排序问题,它是经典平行机排序问题的一个推广。其中每个工件在由机器加工之前都必须由一个服务器将其安装到一台机器上,而一个服务器在同一时刻只能安装一个工件。本文对带一个服务器的两台平行机和三台平行机的排序模型,研究了目标函数为极小化工件最大完工时间的问题,分别设计了近似算法并分析了其最坏情况界。对于两台平行机的排序问题,当工件安装时间相等时,给出了最坏情况界为4/3的近似算法。对于三台平行机的排序问题,当工件安装时间均为1时,给出了最坏情况界为3/2的近似算法。

全文目录

摘要  5-6
Abstract  6-8
第1章引言  8-14
  1.1 排序问题的简介  8
  1.2 排序问题的符号表示法  8-11
    1.2.1 机器的环境  8-9
    1.2.2 优化目标  9
    1.2.3 排序问题的三参数表示法  9-11
  1.3 平行机排序问题  11
  1.4 带服务器的平行机排序问题  11-12
  1.5 本文研究内容  12-14
第2章 P2,S1|s_i=s|C_(max)的近似算法  14-31
  2.1 背景介绍  14
  2.2 算法介绍  14-15
  2.3 近似算法A  15
  2.4 算法A的最坏情况界  15-31
第3章 P3,S1|s_i=1|C_(max)的近似算法  31-39
  3.1 背景介绍  31
  3.2 算法介绍  31-32
  3.3 近似算法B  32
  3.4 算法B的最坏情况界  32-39
第4章总结与展望  39-40
参考文献  40-42
致谢  42

带服务器的平行机排序问题的两个近似算法

内容摘要

全文目录

相似论文