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

一致平行机上在线排序

作　者: 何晓琼
导　师: 李荣珩
学　校: 湖南师范大学
专　业: 运筹学与控制论
关键词: 在线排序问题竞争比空闲同类机器
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 11次
引　用: 2次
阅　读: 论文下载

内容摘要

排序问题是经典组合优化的问题,在线排序是排序论当前研究的热点问题之一.本文主要考虑一致平行机器上工件有到达时间一些在线模型,并分析算法下的竞争比.全文共分三章.第一章是绪论部分,主要介绍排序问题,竞争比分析和近似算法等基本概念,总结近年来出现在线模型及其有关的结论.第二章考虑工件到达时间任意,机器加工速度为s_i=1（1≤i≤m-1）,s_m=s>1,目标函数为极小化最大机器负载的在线模型,主要讨论两个问题:1当m=2时,给出来竞争比为2+（?）且界是紧的.2m台同类机器的情形,根据LS’算法并证明此算法的竞争比为3+（?）.第三章讨论了工件有到达时间任意,机器加工速度为s₁,s₂,…,s_m（s₁≤s₂≤…≤s_m）在线排序问题,目标函数为极大化最小机器负载的在线模型.提出了新的算法,并证明了算法下的竞争比为常数20.

全文目录

中文摘要  3-4
英文摘要  4-6
1 绪论  6-14
  1.1 组合优化简介  6-7
  1.2 排序问题  7-10
  1.3 算法和计算复杂性  10-13
  1.4 论文概述  13-14
2 机器加工速度为1,s的一致平行机上LS'算法  14-28
  2.1 引言  14-16
  2.2 Q_m//C_(max)问题  16-23
  2.3 Q_2//C_(max)问题  23-28
3 一致平行机上机器加工速度任意的近似算法A  28-36
  3.1 引言  28-29
  3.2 近似比为常数的算法A  29-36
结束语  36-38
参考文献  38-40
攻读硕士学位期间完成的论文  40-42
致谢  42-43

一致平行机上在线排序

内容摘要

全文目录

相似论文