本文主要研究了两类不可中断的平行机排序问题：一类是带服务等级约束的m台机在线排序问题，目标是极小化总完工时间；另一类是带单服务器装卸载的两台机排序问题。目标是极小化最大完工时间（makespan）。全文共四章。第一章简要介绍了排序的基本理论知识。第二章研究了带服务等级约束的m台机在线排序问题。本章主要考虑了单位工件情况下该问题的下界以及算法设计，其中要求等级较低的工件只能安排在第一台机器上，等级较高的工件可以安排在台机中的任一台上。本章首先证明下界为，其中。特别地， m=2时问题的下界为16/131.2308，改进了已有的结果1.1573。然后给出了一个贪婪算法，通过分析该算法最坏情况实例的结构，证明了该算法的竞争比为且是紧的。最后，我们对于特殊情况m=2，设计了一个竞争比为16/13的最优算法。第三章研究了带单服务器装卸载的平行机排序问题。即工件在加工前后必须由一台服务器进行装载和卸载，且在装卸载时所在的机器不能加工工件。本章主要考虑用经典的LS算法和LPT算法研究该问题装载时间和卸载时间相等且均为单位时间的情形。首先分析了该问题的列表排序结构，最后利用分块的思想得到LS算法和LPT算法的界分别是12/7和4/3且证明是紧的。第四章总结全文并提出今后的研究方向。