排序问题是经典组合优化的问题，在线排序是排序论当前研究的热点问题之一，本文主要考虑一致平行机器上工件有到达时间一些在线模型，并分析算法下的竞争比，全文共分三章． 第一章是绪论部分，主要介绍排序问题，竞争比分析和近似算法等基本概念，总结近年来出现在线模型及其有关的结论． 第二章考虑工件到达时间任意，机器加工速度为si=1（1≤i≤m-1），Sm=S>1，目标函数为极小化最大机器负载的在线模型，主要讨论两个问题：1当m=2时，给出来竞争比为2+1/s且界是紧的．2m台同类机器的情形，根据LS算法并证明此算法的竞争比为3+2（m-1）/s+m-1。 第三章讨论了工件有到达时间任意，机器加工速度为s1，s2…，sm（s1≤s2≤…≤sm）在线排序问题，目标函数为极大化最小机器负载的在线模型．提出了新的算法，并证明了算法下的竞争比为常数20.