排序问题有着深刻的实际背景和广阔的应用前景，一直受到国际学术界的重视．本文主要研究了带有固定工件和工件运输时间的单机排序问题。固定工件是一类特殊的工件，它们的开工时间和完工时间都是预先确定的，在时间轴上占据着一些互不相交的区间。在整个加工过程中，工件不允许中断。每个工件有一个运输时间，我们假定在工件加工完后有足够多的卡车运输。 论文共分两章． 第一章(概述)主要介绍了排序的背景、发展、基本概念及排序模型的记法． 第二章主要讨论了四个排序模型的复杂性、拟多项式时间算法和近似算法。用三参数法表示我们的模型即是： 1｜FB(F)，q<,j>｜L<,max>， 1｜FB(F)｜maxw<,j>C<,j>， 1｜FB，q<,j>｜L<,max>， 1｜FB(F)｜∑w<,j>C<,j>． 本文主要结果如下： (1)问题1｜FB(F)，q<,j>｜L<,max>、 1｜FB(F)｜maxw<,j>C<,j>和1｜FB(F)｜∑w<,j>C<,j>是NP-困难的，问题1｜FB，q<,j>｜L<,max>是强NP-困难的。 (2)问题1｜FB(F)，q<,j>｜L<,max>、1｜FB(F)｜maxw<,j>C<,j>和1｜FB(F)｜∑wC<,j>是拟多项式时间可解的。 (3)对于问题1｜FB，q<,j>｜L<,max>给出了最坏性能比为2的近似算法，并证明这是最好可能的多项式时间近似算法； 对于问题1｜FB(1)，q<,j>｜L<,max>给出了最坏性能比为3/2的多项式时间近似算法； 对于问题1｜FB(1)｜maxw<,j>C<,j>给出了最坏性能比为2的多项式时间近似算法，在为常数的情况下我们得到了PTAS算法．并证明除非P=NP，对于问题1｜FB(2)lmaxw<;j>C<,j>，不存在常数界的多项式时间近似算法．