本论文研究两台同类机极大化机器最小负载的排序问题。模型要求在两台速度之比为q的机器上加工工件,并已知工件加工时不可中断,目标是使负载最小的机器其加工时间最大化。本文分析了用LPT算法解离线模型的最坏情况界,给出了证明最坏情况界是紧的实例。其次,针对已知工件从大到小到达的半在线模型,本文根据LPT算法在q的某些区间段达不到问题下界的情况,设计了最优算法,并证明了算法的竞争比。其中最坏情况界和竞争比都表示为参数q的分段函数。最后,针对处于不同区间段上的q,分别给出以q为函数的实例来说明半在线问题的下界,从竞争比的角度证明了算法的最优性。 全文共分为三章,第一章介绍了论文用到的排序知识和相关研究结果；第二章介绍了LPT算法最坏情况界的证明思路和具体证明过程；第三章介绍了最优算法的证明过程和问题的下界。