本文主要研究了一类新型的混合shop排序问题，文章中将问题分为两类，第一类是一类新型的混合flow shop排序问题，第二类是一类新型的混合openshop排序问题。目标函数是最小化机器最大完工时间。　　 第一章介绍了排序问题，近似算法和计算复杂性以及竞争比分析的一些的基本概念。第二节主要介绍了P类，NP类的定义，以及NP—难，强NP—难的定义，并给出了NP—难，强NP—难的证明方法和步骤。第四节给出了混合shop排序问题的研究成果。　　 第二章研究第一类问题——一种新型的混合flow shop排序问题。研究了该类问题的两种特殊情况F(O2，1)|| max和F(O2，O)||Cmax。首先证明了F(O2，1)|Cmax问题为强NP—难问题，从而得到F(O2，O2)|Cmax问题也是强NP—难问题。对于每个问题，都给出了多项式时间近似算法。最后讨论了一般情况F(Om2，Om2)||Cmax，对于一般情况，在一个基于Qm||Cnmax问题的近似算法的基础上，给出了F(Om1，Om2)||Cmax问题的一个多项式时间近似算法，并分析了其竞争比与前者的竞争比的关系。　　 第三章研究第二类问题——一种新型的混合open shop排序问题，研究了一种特殊情况O(F2，1)||Cmax问题和此类问题的一般情况O(Fm1，Fm2)||Cmax。首先证明了O(F2，1)||Cmax问题为一般NP一难的，从而一般情况也是一般NP—难的，然后分别给出了特殊情况和一般情况的多项式时间近似算法。