本文研究了自由作业和流水作业环境下的两类排序问题模型,研究的核心是问题的近似算法设计和最坏情况界分析,全文共分五章,具体如下。第一章简要地介绍了排序问题的基本知识以及自由作业和流水作业的相关知识。第二章研究了一类加工时间由工件和机器速度决定的三台机自由作业排序问题,在此问题中工件首先要在三台自由作业机器上加工,工件J_j在机器上的加工时间由工件长度pj和机器的速度si决定。目标是极小化最大完工时间,用三参数表示为O3|pij=pj-si|Cmax,我们设计了一个最坏情况界不大于5/4的近似算法。第三章研究了一类工件加工不等待且机器具有多功能属性的两台机流水作业排序问题,在此问题中工件首先要在两台流水作业机器上加工,工件J_j的两个工序在加工过程中不能中断,第一台机可以加工工件J_j的两个工序。目标是极小化最大完工时间,用三参数表示为F2|nwt,mtflx|Cmax,我们改进了已有文献的结果(最坏情况界为5/3),设计了一个最坏情况界不大于13/8的近似算法。第四章研究了一类工件加工不等待且可分割,机器具有多功能属性的两台机流水作业排序问题,在此问题中工件首先要在两台流水作业机器上加工,工件J_j的两个工序在加工过程中不能中断,第一台机可以加工工件J_j的两个工序,工件的第二个工序在加工过程中可以中断。目标是极小化最大完工时间,用三参数表示为F2|nwt,mtflx,prmp|Cmax,我们进一步推广了现有的文献结果(现有的文献给出启发式算法),设计了一个最坏情况界不大于8/5的近似算法。第五章总结全文并提出相关问题进一步的研究方向。