排序问题是组合优化领域中的一类重要问题，它是利用一些处理机、机器或者资源，最优地完成一批给定的任务或作业，在生产管理与调度、网络通信、理论计算机科学等方面有广泛的应用。 本文主要研究在m台同型机上工件有到达时间的排序问题的LS算法。目标函数是使机器的最大完工时间（makespan）达到最小。 第一章介绍了排序问题，算法的竞争比分析等基本概念，描述了（半）在线排序和工件有任意到达时间的在线排序模型的一些特性。第二章研究了m台同型机上有到达时间工件的LS排序问题，研究了LS算法的最坏性能比。给出了LS算法的紧性能比的一个简单证明。第三章讨论了m台同型机上工件有到达时间且加工时间非增的LS算法问题，得到如下的两个结论，一个是证明了对于任意工件序列L={J1，J2，…，Jn）如果 r1≤r2≤…≤rn且P1≥P2≥…≥Pn，有R（m，LS）≤3/2-1/2m；另一个是若到达时间为任意的且加工时间为单调非增序列，则LS算法的最坏性能比不大于2。