本文研究了两类排序问题，一类是同型机上可中断半在线排序问题，一类是同类机上的在线排序问题.并且对这两类问题都给出了最优的(半)在线算法.全文共分为三章. 第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识.第二章主要研究了m台同型机上已知总和的可中断半在线排序问题.目标是极小化最大的机器完工时间(Cmax)和极大化最小的机器完工时间(Cmin).对于Cmax目标，给出了一个最优的半在线算法，其竞争比为1.对于Cmin目标，当m＞2时，证明了任何半在线算法的竞争比至少为2m-3/m-1，并且对于m=2，3的情形分别给出了最优的半在线算法. 第三章主要研究了两台同类机上的在线排序问题，目标函数为极小化最大工件开工时间.首先证明了问题的下界为1+s，然后证明了贪婪(Greedy)算法的上界为1+s，从而是最优的在线算法.这里s是两台机器的速度比.