本文主要研究Lp范数下的半在线排序问题。问题描述如下,给定m台同型机,以及n个工件,我们需要将每个工件安排在这些机器中的一台或者若干台上进行加工,每一时刻每台机器上只能加工一个工件,每一工件在同一时刻在其需要的数量的机器上加工,每个工件加工时间不一定相同,工件需要的机器数量也可能不同,工件是按照列表顺序达到的,只有当前一个工件安排之后,后一个工件才到来,工件的具体信息只有当其到达之后才知晓。每个工件安排以后就必须加工完,不允许中断。我们的目标是将工件安排在这些机器上,使得处理机的完工时间向量(负载)的Lp范数最小。论文结构如下,第一、二章介绍了排序问题的背景知识。第三章和第四章讨论三台同型机的半在线排序问题,此处讨论的问题中每个工件只需要一台机器加工即可,目标是极小化机器负载的Lp范数,在第三章,针对总加工时间已知的情形,我们设计了竞争比至多为max{3/2,(?)}的半在线算法。在第四章针对的是最大加工时间已知情形,我们设计了竞争比至多为max{(?),(?)}的在线算法。在第五章,我们研究了 Lp范数下m台同型机并行工件半在线排序问题的算法,此处工件是并行工件,即每个工件加工需要的机器数可以不止一台,对已知最大加工时间的情形,我们给出了竞争比至多为40/3的算法,进一步分析表明该算法的竞争比至少为6。最后对论文进行了总结,分析了所得结果的不足之处以及进一步研究的方向和思路。