同类机半在线机器覆盖问题研究
论文摘要: 本文主要研究两台同类机半在线机器覆盖问题.全文共分为三章. 第一章是绪论部分,主要介绍排序问题,近似算法和竞争比分析等基本概念. （略）主要研究了两台同类机已知工件总加工时间的半在线模型,目标是极大化最小（略）.根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FF(当1≤s≤(1+5（略）)/2时)和优先考虑速度慢的机器的算法SF(当s>(1+5~(1/2))/2时).并且证明了这两个算法都是最优的,竞争比是: 第三章主要研究了两台同类机已知工件最大加工时间的半在线模型,目标是极大化最小机器完工时间.根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FFLS(当1≤s≤(1+5~(1/2))/2时)和优先考虑速度慢的机器的（略）(当s>(1+5~(1/2))/2时).其中算法FFLS对1≤s≤(1+5~(1/2))/2是最优的,算法SFLS对s∈[1.618,2.1479)∪(3.83598,+∞)是最优的,在s∈（略）9,3.83598)时,算法SFLS的竞争比和问题的下界的差距最多不超过0...
This thesis mainly concerns design and analy（omitted）roximation algorithms on semi-online uniform machine covering problems. We first introduc（omitted）tions scheduling problem, approximation algorithms and competitive analysis.In Chapter 2, we investigate semi-online scheduling （omitted） two uniform machines, where the total size of all jobs is known in advance, the objective is to maximize （omitted）m load of two machines. We present two optimal algorithms FF for and （omitted）espectively. FF gives pref...
目录:摘要 第4-5页
Abstract 第5页
第1章 绪论 第7-15页
·排序问题 第7-8页
·近似算法和竞争比分析 第8-9页
·半在线排序问题 第9-10页
·西台同类机在线半在线排序问题 第10-12页
·论文综述 第12-15页
第2章 已知工件总加工时间的两台同类机排序 第15-22页
·问题Q2|sum|C_(min)的下界 第15-16页
·问题Q2|sum|C_(min)的最优算法 第16-22页
第3章 已知最大工件加工时间的两台同类机排序 第22-35页
·问题Q2|max|C_(min)的下界 第22-24页
·问题Q2|max|C_(min)的算法 第24-35页
参考文献 第35-37页
致谢 第37-38页
在学期间完成的论文 第38页
【同类机半在线机器覆盖问题研究】相关文章：
机器带中断的若干延误问题研究论文提纲11-18
考虑节能降耗的关键机器调度问题研究11-18
林权在线竞价信任机制研究提纲11-29
变电设备在线检测技术的应用研究03-03
企业品牌经营问题研究11-15
教学的存在问题及对策研究11-14
企业采购管理问题研究03-30
在线高校毕业生档案管理系统的研究02-25
企业债务重组问题的研究论文01-12
- 相关推荐