本文主要研究了两类加工时间依赖机器的两阶段车间作业排序问题，一类是加工时间依赖机器的两阶段流水作业排序问题，另一类是加工时间依赖机器的两阶段自由作业排序问题.本文分别设计了相应的近似算法，并证明了算法的最坏情况界.全文共分为四章，具体如下:　　第一章简要介绍与排序问题相关的一些概念及相应的理论基础知识.　　第二章研究一类源于计算机网络数据传输中的加工时间依赖机器的两阶段流水作业排序问题，用三参数表示法表示为:HFS(2，m)/pij=pj/Cmax.在该问题中，工件需要先在第一阶段加工完工后再到第二阶段进行加工，其中第一阶段和第二阶段分别由2台和任意m台同型机组成，且相同工件在两个阶段的加工时间都相同.本文针对m=2情况下的问题，给出了一个近似算法，并证明了算法的最坏情况界为4/3，同时给出了紧界实例.针对任意m≥3的情况，同样给出了问题的一个近似算法，并证明了算法的最坏情况界不大于3/2.　　第三章研究一类源于并行数据处理中的加工时间依赖机器的两阶段自由作业排序问题，用三参数可以表示为O2(m1，m2)|pij=pj|Cmax.在该问题中，工件需要在两个阶段进行加工，且在两个阶段间的加工顺序可以任意但不能重叠.其中第一阶段和第二阶段分别由m1台和任意m2台同型机组成，且相同工件在两个阶段的加工时间都相同.由于该问题是一个新问题，所以本文首先用多项式时间规约的方法证明了该问题当min{m1，m2}≥2时是NP-难的.其次，针对该问题给出了一个近似算法，并证明了算法的最坏情况界不大于3/2-3/2(2min{m1，m2}+1）.同时进步一步说明了当min{m1，m2}=1时，该算法为问题的最优算法.最后，我们通过改进该算法的第一阶段工件的排序得到了改进算法，这是因为算法的最坏情况界由第一阶段的排序决定.　　第四章对全文的工作进行总结，并给出了今后问题的进一步研究的方向.