本文针对并行任务（工件）在线排序的若干问题进行了深入研究，文中讨论的排序问题均可以描述为:给定若干台同型处理机以及按照列表顺序到达的并行任务，每个任务需要若干台机器同时加工才可完工，当任务到达时，需要指派其加工所用的机器和开工时间，使得任何时刻每台机器最多只有一个任务进行加工，且每个任务加工时使用的机器数量满足任务要求，加工过程不允许中断（这称为可行排序），目标是使得处理机负载的Lp范数最小。这里任务是按列表顺序到达的，即上一任务安排完毕后下一个任务才到达，且仅当任务到达后其加工信息才知道，任务一旦被安排好，就不能再做任何调整。本文的主要工作是对相应的若干在线排序问题分析经典的LS算法性能，在此基础上设计具有较好竞争比的在线算法。　　论文分为六章，第一章对排序问题和算法设计与分析的相关内容进行了介绍，对我们要研究的相关内容进行了综述。　　第二章研究了两台同型机并行任务半在线排序问题，对经典的LS算法应用到该问题上的竞争比进行了分析。具体而言，对两台同型机，当任务按加工时间非增序到达时，LS算法所得的排序有两种可能，对于第一神情形，LS算法的竞争比为p√2，第二种情形的竞争比为4/3，其界都是紧的。对于并行任务按照加工时间非降顺序到达的半在线排序问题，同样的，LS算法得到的排序也有两种可能，其相应的竞争比为p√(2p+3p)/2p+1和4/3，均为紧界。　　第三章对两台同型机并行任务在线排序问题，分析了问题的下界，分析表明了任何在线算法的竞争比下界不小于4/3。　　第四章将两台同型机半在线并行任务排序问题推广到m台同型机的半在线并行任务排序问题，我们给出了一个半在线算法，证明了该算法的竞争比小于12。　　第五章研究了一般情形，即m台同型机并行任务在线排序问题，给出了一个竞争比不超过16的在线算法。　　第六章对全文进行了总结，分析了文中所提算法的不足和改进之处，对进一步研究提出了展望。