本文主要研究有服务等级约束的平行机排序问题的可中断算法.全文共分三章. 第一章是绪论部分，主要介绍了排序问题的相关概念和准备知识，以及对本文的一个简要概述. 第二章介绍了有服务等级约束的平行机排序问题的可中断离线算法.首先研究m台同型机的可中断离线排序问题，并给出了一个时间复杂性为O(n)的最优算法.接着考虑了2台同类机可中断离线排序问题，给出了一个时间复杂性为O(n2)的最优算法. 第三章介绍了有服务等级约束的平行机排序问题的可中断在线算法.主要考虑了2台同型机和2台同类机可中断在线排序问题，要求服从先来先加工的服务原则.对于2台同型机在线情形，本文给出了一个最优算法，竞争比为3/2.对2台同类机在线情形，本文分了两种情况：其中一种情况是2台同类机中等级较高的机器速度也较大，此时本文给出了一个最优算法，竞争比为1+1/s+1；另一种情况是等级较高的机器速度较小，此时本文给出了一个算法，其竞争比与下界至多相差0.2228.