- 相关推荐
同类机半在线机器覆盖问题研究
论文摘要: 本文主要研究两台同类机半在线机器覆盖问题.全文共分为三章. 第一章是绪论部分,主要介绍排序问题,近似算法和竞争比分析等基本概念. （略）主要研究了两台同类机已知工件总加工时间的半在线模型,目标是极大化最小（略）.根据机器速度之比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页
【同类机半在线机器覆盖问题研究】相关文章：
电压跌落问题的研究论文05-05
电网生产安全在线评估所需要解决的问题论文04-27
在线高校毕业生档案管理系统的研究08-11
企业债务重组问题的研究论文06-05
谈谈林业种植问题策略研究05-24
浅谈急诊急救的问题的研究论文04-27
成本核算的问题研究论文05-01
在线仲裁中《仲裁法》的适用问题浅谈论文04-25
关于企业员工培训的问题与对策研究08-05
关于企业债务重组问题的研究论文06-05