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

同类平行机半在线排序问题的若干研究

作　者: 谭金芝
导　师: 何勇
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 排序问题半在线近似算法竞争比
分类号: O223
类　型: 硕士论文
年　份: 2005年
下　载: 46次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要研究了两类预先知道两种信息的同类平行机半在线排序问题，一类是带机器准备时间的同型平行机半在线问题；另一类是同类平行机半在线排序问题。全文共分三章，第一章主要介绍了平行机排序问题的背景、基本概念和单信息半在线排序问题的研究进展，第二章介绍了复合半在线及带准备时间的同型机排序问题，并讨论了带机器准备时间且已知所有工件总加工时间和最大工件加工时间的两台同型机的半在线排序问题，目标函数为极小化最大机器和最大工件的完工时间的问题，并证明了SM算法为最优半在线算法，竞争比为6／5，第三章介绍了同类机半在线排序问题，并讨论了预先知道所有工件总加工时间和最大工件加工时间两种信息的两台同类机半在线排序问题，目标函数为极大化最小机器完工时间的问题，并给出了此问题一个竞争比为3s+2／2s+s的半在线算法。

全文目录

摘要  3-4
Abstract  4-6
第一章平行机排序理论  6-18
  1.1 平行机排序问题  6-9
  1.2 排序问题的算法与算法评估  9-12
  1.3 单信息的半在线排序问题  12-18
第二章复合两个信息的半在线排序问题  18-28
  2.1 复合半在线排序问题  18-21
  2.2 带准备时间的平行机排序问题  21-23
  2.3 P_2,r_j／sum,max／C_(max)模型  23-28
第三章同类机半在线排序问题  28-36
  3.1 同类机半在线排序问题  28-31
  3.2 Q_2／sum,max／C_(min)模型  31-36
参考文献  36-42
致谢  42-43
攻读学位期间录用的论文  43

同类平行机半在线排序问题的若干研究

内容摘要

全文目录

相似论文