此文是一篇参考文献论文范文,参考文献方面有关论文范文资料,与同类机半在线机器覆盖问题相关大学毕业论文。适合不知如何写参考文献及开题报告及应届生方面的论文致谢专业大学硕士和本科毕业论文以及参考文献类开题报告范文和职称论文的作为写作参考文献资料下载。
论文摘 要 : 本文主要研究两台同类机半在线机器覆盖问题.全文共分为三章. 第一章是绪论部分,主要介绍排序问题,近似算法和竞争比分析等基本概念. (略)主要研究了两台同类机已知工件总加工时间的半在线模型,目标是极大化最小(略).根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FF(当1&le,s&le,(1+5(略))/2时)和优先考虑速度慢的机器的算法(当s>,(1+5~(1/2))/2时).并且证明了这两个算法都是最优的,竞争比是: 第三章主要研究了两台同类机已知工件最大加工时间的半在线模型,目标是极大化最小机器完工时间.根据机器速度之比s的不同,我们分别给出了优先考虑速度快的机器的算法FFLS(当1&le,s&le,(1+5~(1/2))/2时)和优先考虑速度慢的机器的(略)(当s>,(1+5~(1/2))/2时).其中算法FFLS对1&le,s&le,(1+5~(1/2))/2是最优的,算法LS对s&isin,[1.618,2.1479)&cup,(3.83598,+&infin,)是最优的,在s&isin,(略)9,3.83598)时,算法LS的竞争比和问题的下界的差距最多不超过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 petitive 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页