排序算法的竞争比分析是排序问题对算法风险的一种评估和保障，具有重要的理论意义和实用价值。在排序问题中，半在线排序所需的信息介于完全在线和完全离线的排序之间，比较符合实际应用中的情况。近几十年来，其研究得到了一定进展，形形色色的半在线排序问题和算法不断涌现，但对于这些问题算法的竞争比分析几乎处于空白。本文在经典在线排序模型的基础上，通过增加额外信息构成半在线排序问题，借助一般在线算法性能分析的手段和方法，通过特有的实例转换和分析，对单机最小化完工时间问题、最小化加权完工时间问题和最小化折扣加权完工时间问题的半在线排序算法的性能进行了理论分析。首先，通过构造极端最差实例的方法，分别得到了三种半在线排序问题的竞争比下界，从而确定了半在线排序算法针对这三种问题所能达到的性能极限。然后，对最小化完工时间证明了算法性能随着实例空间的缩小而提升；对最小化加权完工时间问题，分析了哪些信息有助于改善算法性能；针对最小化折扣加权完工时间问题，设计了一个半在线排序算法，推导出该算法的竞争比，证明了该算法在三类特殊的极限情况下是最优算法。本文的主要研究成果包括：1)对基于经典在线排序问题1| rj |？ Cj的半在线排序问题完善了一种半在线排序算法竞争比分析的证明过程，通过限制实例空间，证明了随着实例空间的减小，算法性能会进一步提高。2)针对经典在线问题，研究了该问题在已知未来多步到达时间，加工时间具有上下界限制，以及两者情况皆已知条件下任意半在线算法的竞争比下界。证明了未来多步到达时间对竞争比下界没有改善，但是加工时间限制可以改善竞争比下界，而两者皆已知也不会比仅仅已知加工时间限制得到的竞争比下界更优。3)对经典在线排序问题研究了该问题在已知工件加工时间上下界限制情况下的竞争比下界。并对该问题设计了一种算法，通过实例转化的方式，得到该算法的竞争比。同时证明了对该问题的三类特殊情况，所设计的算法是半在线最优算法。