论文部分内容阅读
本文主要研究同类机在线排序问题．全文共分为三章．
第一章是绪论部分，主要介绍排序问题，近似算法和竞争比分析等基本概念
第二章主要研究了m台同类机的在线覆盖问题，目标是极大化最小机器完工时间．给出了该问题的参数下界以及经典的LS<,s>算法解此问题的参数竞争比．
第三章首先证明了对于目标为极小化最大机器完工时间的m台同类机在线问题，若m台机器的速度分别为s<,1>，s<,2>…．s<,m>(s<,1>≤s<,2>≤…≤s<,m>)，LS<,c>算法的参数竞争比不超过然后又研究了三台特殊同类平行机的在线问题，三台机器的速度分别为1，1，s。