本文主要研究了两阶段车间作业排序问题:第一类是两阶段自由作业排序问题,第二类是两阶段混合车间作业排序问题。研究的重点是,证明这些问题的计算复杂性,设计问题的近似算法,并对算法的最坏情况界进行证明。全文共分为四章。具体如下:第一章简要的介绍排序的基本理论。第二章主要研究一类新型两阶段自由作业排序问题。第一阶段是自由车间,第二阶段是流水车间,目标是极小化最大完工时间。其中要求工件一旦进入流水车间的两台机上加工,必须完成流水车间加工才可进行下一阶段任务。本章分两种情形,目标均是极小化最大完工时间。情形一:考虑一般的情况,第一阶段机器为m台,第二阶段机器为两台,本章提出一个近似算法,并证明其最坏情况界为2;情形二:第一阶段机器为一台,第二阶段机器为两台,本文对问题进行复杂性证明,证明该问题是NP难问题,并给出一个5/3-近似算法及其最坏情况界证明。第三章主要研究一类两阶段混合车间作业排序问题。第一阶段是自由车间共两台机,第二阶段是流水车间共两台机。其中工件可选择任一阶段的车间进行加工,目标是极小化最大完工时间。本文对问题的复杂性进行证明,证明该问题是一般NP难问题,同时提出一个近似算法,并证明其最坏情况界为27/14。第四章总结全文并提出相关问题进一步的研究方向。