本文研究了两台同型机的在线和半在线排序问题.该问题可以描述为：给定一个相互独立的工件序列J={p1，p2，…，pn}，每个工件的加工时间(长度)是pi，i=1，…，n，且需要把它们分配到两台同型机M1，M2上进行不可中断地加工.工件和机器在零时刻都处于就绪状态.机器的负载是指所有在这台机器上加工的工件的总长度.在算法S下机器Mi的负载记为Li(J,S)(在不会引起歧义的情况下，可简记为Li),i=1，2.目标是极小化机器负载的lp范数，即Lp(J,S)≡[l1(J,S)p+l2(J,S)p]1/p，这里p＞1.全文共分为三章. 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识. 第二章主要研究了lp范数下两台同型机上己知工件按照加工时间从大到小的顺序到达的半在线排序问题.本文证明了LS算法是求解该问题的最优半在线算法，竞争比为max1≤△≤2((△+2)p+(△+1)p/(2△)p+3p)1/p，同时还证明了该问题及其所对应的在线问题的随机下界. 第三章主要研究了Lp范数下两台同型机的另两个半在线排序问题.对于已知工件的最大加工时间和总加工时间的两个问题，证明了最优半在线算法的竞争比均为(2p-1(2p+1)/3p)1/p.