本文主要研究有维护时段的平行机排序问题的近似算法设计及其最坏情况界分析．对多个不同机器环境和目标函数下的机器带有维护时段的排序问题及其他相关问题，讨论了这些问题的复杂性或难近似性，设计了相应的近似算法并证明了其最坏情况界．　　 全文共分为五章，第一章介绍了组合优化问题，计算复杂性和近似算法以及与排序问题相关的一些预备知识，并叙述了机器有维护时段排序问题的背景．研究现状和相关概念．　　 第二章研究有维护时段的m台同型机排序问题，目标为极小化工件总完工时间，工件加工为不可恢复情形．若每台机器上均有多个维护时段，证明了该问题不存在最坏情况界为常数的多项式时间近似算法，若每台机器上恰有一个维护时段且各台机器上的维护时段互不重叠，该问题不存在最坏情况界小于m/m-1的多项式时间近似算法，除非P=NP.随后考虑了前k(1≤k≤m-1)台机器上均有多个维护时段的情形，证明了算法SPT的最坏情况界至多为m/m-k．当前k（1≤k≤m）台机器中每台机器恰有一个维护时段且各台机器上的维护时段互不重叠时，证明了算法SPT的最坏情况界不超过2+k-1/m-1．　　 第三章考虑有维护时段的两台同型机排序问题，目标为极小化工件总完工时间，工件加工为不可恢复情形．若其中一台机器上没有维护时段而另一台机器上恰有一个维护时段，证明了算法SPT的最坏情况界为3/2且该界是紧的．若两台机器上均恰有一个维护时段且两台机器上的维护时段互不重叠，算法SPT的最坏情况界为2且此时算法SPT是求解该问题的最坏情况界最小的多项式时间近似算法，除非P=NP.　　 第四章讨论有维护时段的单机排序问题，工件加工为半可恢复情形．当目标函数为makespan时，给出了算法LPT的最坏情况界并得到了该问题的FPTAS.当目标为加权总完工时间时，设计了一个最坏情况界不超过2的多项式时间近似算法．此外，对于该目标的两个特殊情形，文中也分别给出了相应的近似算法或近似方案的设计与分析．　　 第五章研究一个与有维护时段相关的问题：有禁止操作时段的单机排序问题．所谓禁止操作时段是指在该时段内任何工件都不能进行开工和完工操作，但是在该时段之前开始加工的工件在该时段内可以正常加工，直至该时段结束后的某个时刻加工完成．目标为极小化工件总完工时间．证明了该问题是NP-hard的，并设计了一个最坏情况界为20/17的多项式时间近似算法．