排序是运筹学组合优化领域中研究最为活跃的分支之一.近年来，随着理论研究及实际的需要，产出了很多新型排序问题.本文主要研究三类新型混合车间作业排序问题，并且这些混合问题都可以看成是不同机器环境意义下的混合.研究的核心是近似算法的设计和最坏情况界的分析.全文共分为四章.　　第一章首先介绍了排序问题、计算复杂性和算法等的基本概念和理论，接着论述了与本文相关的若干排序问题的相关研究成果.　　第二章研究了一类源于服装生产流水线等领域的新型混合车间排序问题.在该问题中，工件的有些工序之间的加工顺序是确定的且每个工件都相同，而其他工序的加工顺序则是不确定的，可以看成是若干台流水作业机器与开放作业机器的混合模型，目标函数是极小化最大完工时间.首先，证明了该问题是一般NP-困难的.其次，对于两台流水作业机器和一台开放作业机器的混合情况，给出了问题的一个3/2-近似算法，且说明界是紧的.最后，将问题推广，考虑两台流水作业机器与任意台平行机的混合模型，给出了问题的一个2-近似算法，并同样说明界是紧的.　　第三章研究了一类开放作业环境下的带运输排序问题.考虑在两台开放作业的机器环境下，工件加工完后需要由唯一的一辆运输工具运输到顾客处，运输工具有容量限制，每个工件占用的运输工具的空间也不同（工件尺寸不同），目标是极小化最后完工工件运输到顾客处同时运输工具返回机器的时间.对于该问题的一般情况，给出了问题的一个2-近似算法，且说明界是紧的.对于运输工具每次只能运输一个工件的情况，给出了问题的一个改进的3/2-近似算法，且同样说明界是紧的.　　第四章则研究了一类平行开放作业排序问题.工件需要在若干个平行的两台机开放作业系统中选择一个进行加工，目标是极小化最大完工时间.对于具有m个开放作业系统的一般情况，给出了问题的一个2-近似算法，并说明界是紧的.对于具有2个开放作业系统的情况，给出了一个改进的3/2-近似算法，且同样说明界是紧的.