本文研究作业具有加工冲突约束的排序问题。对于每个作业只能被指定的一台机器加工的两台平行专用机排序,冲突约束可以用一个二部图来刻画,即使在一台机器上的作业加工次序给定的假设下,极小化作业最大完工时间的问题也是强NP-难的。本文的贡献是对这一强NP-难问题设计了基于LPT规则的近似算法,证明了算法的最坏情况紧界是35,这是该问题的第一个近似算法。此外,论文还分析了不同冲突图结构下问题的计算复杂性,全文共分为四章。第一章首先定义了排序问题,近似算法以及计算复杂性,接着介绍了平行专用机器和加工冲突约束,最后综述了相关排序问题的研究现状。第二章研究了具有冲突约束的两台平行专用机排序问题,当第一台机器的作业加工次序给定时,设计了基于LPT规则的近似算法,并证明了算法的最坏情况界,给出了紧例。第三章首先给出了两台平行专用机排序问题的两种情形:增加了二部图中对应第二台机器上作业的最大度不超过1的要求,增加了第一台机器上作业的加工安排给定的要求,采用划分问题进行多项式时间归约,证明了两个问题分别是NP-难的和无常数界的。对后者,若二部图中对应第二台机器上作业的最大度不超过k,则该问题也不存在最坏情况界小于k（10）3)2(的多项式时间算法。第四章总结全文。