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