排序是一类古老而又充满活力的组合优化问题,在其提出之初就出现了工件(或任务)之间不相互独立的概念,其中加工优先序是一种典型的工件不独立情形。本文研究具有加工优先序约束的流水作业机排序,目标是极小化工件最大完工时间。对所有工件的加工时间都相同的单位工件情形,排序问题的求解与序约束图的分层相关,不同的分层算法能够生成不同的排序算法,这在排序问题的以往研究中是不常见的。本文的主要贡献是利用序约束图的自然分层设计了三台流水作业机排序的一个5/3-近似算法,对序约束图为最长链结构的情形(Longest Chain Graph,LCG)证明了算法的最坏情况紧界是3/2。此外,本文还提出了序约束图的改进分层算法,从而得到了改进的排序算法。以上结果均可以推广到任意台流水作业机上。全文分为五章进行阐述。第一章首先给出了排序问题的基本定义,以及计算复杂性和近似算法的相关概念,接着重点介绍了加工优先序和不同类型的序约束图。第二章综述了序约束排序的国内外研究现状,包含不同序约束图、不同目标函数、不同机器环境下的计算复杂性和近似算法结果,特别指出了若干序约束排序的open问题,其中包括本文研究的模型,其计算复杂性仍然是open的。第三章主要研究了单位工件、具有序约束的三台机流水作业排序问题,目标函数是极小化工件最大完工时间。本章首先分析了最优排序的结构,给出了最优解下界,并根据序约束图的自然分层设计了最坏情况界为5/3的排序算法。接着,对LCG型序约束图,在自然分层的基础上,为各层寻找相容工件的匹配,由此得到了3/2-近似的改进算法。最后,通过构造实例,说明了3/2的算法界是紧的。第四章将序约束图分解成LCG和剩余子图两部分,并将剩余子图中的顶点(即工件)与LCG中的完全二部图分层进行匹配,由此提出了序约束图的改进分层算法,进而得到了改进的排序算法。最后,讨论了算法和最优解的性质。第五章总结全文,猜测第四章所提算法的最坏情况界,提出了证明思路。