排序问题是一类重要的组合优化问题，它是利用一些处理机、机器或资源最优地完成给定的一批任务或作业，在线排序为排序问题中的一个重要分支.本文主要考虑在平行机上对到达时间不为零的工件进行在线排序的问题，并提出了相应排序模型，且分析了此算法的性能比.全文共分为三章.　　 第一章为本文的绪论部分，主要介绍了组合优化，排序问题和近似算法等基本概念及其研究近况.　　 第二章讨论了平行机的两类机器一一同类机与非同类机的排序问题.本章针对J.Aspnes，Y.Azar，A.Fiat，S.Plotkin，O.Waarts等人在[1]中提出的在线排序算法，考虑一种新的情况一一工件的到达时间不为零.在同类机的情形下，改进算法并得其性能比为12；在非同类机的情形下，提出了新算法并知其性能比为O(logn).　　 第三章考虑一种特殊情况，即到达时间不为零且不递减,加工时间为单位“1”的工件应用LS算法进行在线排序，证明了LS算法为最优算法，即其最坏性能比为1.