本文主要考虑平行机半在线排序问题.本文首先简要介绍了排序问题、竞争比分析和近似算法等基本概念，总结了近年来出现的各个半在线模型及其有关结果. 第二章考虑已知工件最大加工时间的半在线模型，目标为极大化最小机器负载.主要讨论两个问题：1三台同类机的情形，我们给出min3算法并且证明此算法的竞争比为max{r+1，3s+r+11+r+s}.min3算法是紧的且当1≤s≤2、r=1时是最优的.2m台特殊同类机问题，我们给出Cmin算法及其竞争比max{m-1，ms+m-1}，并证明Cmin算法是紧的且当1≤s≤(m-1)(m-2)(m≥3)时是最优的. 第三章考虑已知工件最大加工时间的半在线问题，目标为极小化机器最大负载.主要讨论四个问题：1对于两台同类机的问题，我们给出竞争比分别为2(s+1)s+2(1≤s≤2)和s+1(s＞2)的Qmax2算法，并且证明此算法是紧的且相应某些s的特殊值是最优的.2对于三台同类机半在线问题，我们给出Qmax3算法并证明此算法的竞争比不大于2(r+s+1)2r+s(1＜s≤2)和r+2s+1(s＞2)且严格小于2.3对于三台特殊同类机问题，给出Qmax3t算法并证明其竞争比不大于s+2(1≤s≤2)和s+2s(s＞2)且恒小于2.4最后我们考虑m台同型机问题，给出一个竞争比为2m-3的Cmax算法并证明此算法对任何m≥3是紧的. 第四章中，我们考虑已知工件总加工时间的两台同类机半在线问题，目标为极大化最小机器负载.我们给出Q2min算法并证明此算法的竞争比小于2+√22，而此问题竞争比的下界为1+√52.同时证明当s=1+√52时Q2min算法最优的. 在第五章中，我们考虑带机器准备时间的已知工件总加工时间的半在线问题.第一节考虑P2，ri｜sum｜Cmin问题，给出Prsum算法并证明此算法的竞争比为32且是最优算法.在第二节则考虑Q2，ri｜sum｜Cmax问题，给出Qrmax算法并证明此算法的竞争比为√2；同时给出此问题的一个下界. 第六章我们首先引进一个新的半在线术语：半在线模型的松弛，然后我们介绍一个新的半在线模型：已知工件最大加工时间在某一区域内，即knownlargestjobinterval模型.第一节考虑P2｜knownlargestjobinterval｜Cmax问题，我们给出Pinterval算法及其竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过433.第二节考虑P2｜knownlargestjobinterval｜Cmin问题，我们给出Pinterval算法的竞争比，并证明此竞争比是紧的且与最优竞争比的误差不超过14.