本文从下界和算法的角度对带服务等级的两台同类机半在线排序问题进行了研究，目标函数为最小化时间表长。问题中的机器和工件都被赋予了不同的服务等级，只有当一个工件的服务等级不低于一台机器的服务等级时，这个工件才被允许在该台机器上加工。在半在线排序问题中，工件按照一个给定列表中的顺序依次到达，在工件到达之前，排序者已知工件的部分信息。我们考虑的是已知工件加工时间上下界的情形。　　第二章研究了工件加工时间有界的两台同类机半在线排序问题，其中第二台机器速度是第一台的s(0＜s≤1)倍，而且只能加工部分等级的工件。设所有工件的加工时间上下界之比为t(t≥1)，即1≤p≤t。目前关于该问题下界及算法的研究，仍然有面积约为0.2的(s，t)区域没有得到解决。我们对没有解决的(s，t)区域作出了进一步的研究，分析了部分(s，t)区域的下界，并设计了一个算法A，该算法A在这些(s，t)区域上达到了最优。本文研究结果将未解决的(s，t)区域面积缩小到了0.007。