排序论作为最优化理论的重要组成部分,在计算机系统、运输调度、生产管理等诸多领域有着广泛的应用,并且取得了大量有意义的成果。订单排序问题是一类现实意义很强的排序问题,因而具有一定的研究价值。本文讨论了这类问题的计算复杂性。近年来,伴随着生产生活的需要而产生的工件具有优先加工约束的排序问题和半在线（semi-online）模型越来越受到大家的重视。本文就三台同型机上约束链的排序问题和两台带准备时间的同类机半在线问题进行了研究。论文结构安排如下：第一章为绪论部分,首先介绍了排序问题的产生、意义及研究现状,然后给出了必要的预备知识,最后介绍了本文主要研究的问题及其结果。第二章主要讨论极小化带多工类工件订单的完工范围问题：考虑同一类工件放在一起连续加工,任一工件的完工时间为其所在类中全部工件完工时的时间的情况,以订单的完工时间范围最小为优化目标,证明了此问题为NP-hard.并给出了相应的分枝定界算法。第三章主要讨论三台同型机上四个约束链的排序问题,在说明此问题为NP—hard的基础上,通过一个伪多项式时间算法和一个完全多项式时间近似方案来描述此问题的复杂性。第四章主要讨论两台带准备时间的同类机半在线排序问题,文中分析了任意算法竞争比的下界,给出了一个近似算法,并证明其竞争比为一分段函数。