排序(scheduling)问题是运筹学领域中一个非常活跃的分支，它广泛应用于计算机科学、管理科学和工程技术等众多领域。本文主要研究带服务等级约束的同型机在线排序问题，目标是极小化总完工时间(∑n j=1Cj)。　　全文共分为四个章节。　　第一章简要介绍排序的基本理论及带服务等级约束排序问题的相关知识。　　第二章主要研究带两个服务等级约束的m台平行机排序问题，所有工件的加工时间均为单位时间且服务等级为1或2，服务等级为1的工件只能在服务等级为1的机器上加工，服务等级为2的工件可以在m台机器中任意一台上加工。目标是极小化总完工时间。本章主要考虑以下两种情形:对机器台数为m台，其中第1台机器服务等级为1，后m-1台机器服务等级为2的情形给出了竞争比为1+2(m-1)/√8m3-11m2+5m-1+2m-1的在线算法，且该结果好于已有结果;对前k台机器服务等级为1，后m-k台机器服务等级为2的情形给出了问题的下界LBk={1+min{1/m，max{g(「x0(」)，g((「)x0」)}}，k≥m/21+min{1/m，max{q(「x1(」)，q((「)x1」)}}，k＜m/2其中:g(x)=2/(x-A)+A2+3A+2m/k/(x-A)+(1+2A)，x0=√A2+3A+2m/k+A，A=1/2k(2k-(「)k/m-k」(m-k））（1+([)k/m-k」）;q(x)=2/(x-1)+2m/k+4/x-1+3,x1=√4+2m/k+1。　　第三章主要研究带服务等级约束的3台平行机排序问题，目标是极小化总完工时间。本章主要考虑以下两种情形:当一台机器等级为1，两台机器等级为2时，给出了竞争比为17/14的最优在线算法;当两台机器等级为1，一台机器等级为2时，给出了竞争比为43/36的最优在线算法。　　第四章总结全文内容并提出可进一步研究的方向。