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

同类机半在线机器覆盖问题研究

作　者: 曹顺娟
导　师: 谈之奕
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 排序算法的设计与分析半在线竞争比分析
分类号: O223
类　型: 硕士论文
年　份: 2006年
下　载: 22次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要研究两台同类机半在线机器覆盖问题。全文共分为三章。第一章是绪论部分,主要介绍排序问题,近似算法和竞争比分析等基本概念。第二章主要研究了两台同类机已知工件总加工时间的半在线模型,目标是极大化最小机器完工时间。根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FF(当1≤s≤(1+5^1/2)/2时)和优先考虑速度慢的机器的算法SF(当s>(1+5^1/2)/2时)。并且证明了这两个算法都是最优的,竞争比是: 第三章主要研究了两台同类机已知工件最大加工时间的半在线模型,目标是极大化最小机器完工时间。根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FFLS(当1≤s≤(1+5^1/2)/2时)和优先考虑速度慢的机器的算法SFLS(当s>(1+5^1/2)/2时)。其中算法FFLS对1≤s≤(1+5^1/2)/2是最优的,算法SFLS对s∈[1.618,2.1479)∪（3.83598,+∞）是最优的,在s∈[2.1479,3.83598)时,算法SFLS的竞争比和问题的下界的差距最多不超过0.064。

同类机半在线机器覆盖问题研究

内容摘要

全文目录

相似论文