本文主要研究可中断平行机离线情形下i次中断的最优目标值与无限制中断下的最优目标值的比值的最坏情况界以及近似算法的设计。对于不同的机器环境和目标函数，分别给出最坏情况界并设计相应的近似算法。全文共分为四章，首先第1章介绍排序的基本理论以及相关的预备知识。　　 第2章主要研究有限次中断限制的极小化最大完工时间平行机排序问题，主要考虑i次中断最优解值与无限制中断最优解值的比值的最坏情况界。前人[1]通过分析最优解的结构得到该问题的界为Ri=m/2m+i+1，0≤i≤m-1，特别当i=0时，证明LPT算法能够保证该界，本章提出一个更加简单的办法来寻找该问题的界，即找到界为Ri的实例并设计一个最坏情况界为Ri的近似算法，通过该方法不仅获得相同的界Ri还给出一个最坏情况界为Ri(0≤i≤m-1)的近似算法。另外讨论了目标函数值和中断次数之间的关系。最后针对两台同类机情形，通过相同的方法得到i次中断最优解值与无限制中断下最优解值的比值的带参数s（两台机器速度的比值）的最坏情况界和相应的算法（i=0，1）。　　 第3章主要研究有限次中断限制的机器覆盖问题，旨在获得无限制中断下的最优目标值与i次中断下的最优目标值的比值的最坏情况界。针对m台同型机情形，利用第2章中的方法获得该问题的界为Ri=2m-i-1/m，同时给出最坏情况界为Ri的近似算法。针对两台同类机情形（i=0，1），分别给出了带参数s（两台机器速度的比值）的最坏情况界以及相应的近似算法。第4章对全文做了总结并提出进一步的研究内容。