近几年来，排序问题由于其深刻的实际背景和广泛的应用前景而受到了极大关注。在经典的排序模型中，机器是一直可用的。然而，在实际生活中机器也需要维修，工人也需要休息，这就导致了机器在使用过程中不可能是一直可用的。所以很多人研究了机器带有不可用约束的排序问题。同时我们也考虑了工件带有运输时间的问题，这是因为在具有很多工件数的大型排序问题中，往往在工件加工完之后还需要在一定的时间内将其运送到指定的生产地方。这就使得我们不仅要单纯考虑工件的完工时间也要把运输时间计划在内，使其更符合实际意义。本文主要讨论在机器具有不可用约束的情形下的平行机排序问题。文章主要分为四个部分，第一章中介绍了排序问题的背景，描述及表示方法，并对机器的不可用区间和工件的运输时间做了陈述。第二章中主要讨论了机器具有不可用区间的平行机排序问题。其中第一台机器上有一段不可用区间，第二台机器是可以连续使用的，工件在加工过程中是不允许中断的，目标函数是极小化时间表长。首先介绍了与之相关问题的发展情况，然后通过图例解释了这个问题的动态规化算法，并给出了该问题的全多项式近似方案和时间复杂性。第三章中主要讨论了在机器具有不可用区间的同时，工件还带有运输时间的平行机排序问题，目标函数是极小化最大运输完工时间，同样给出了这一问题的全多项式近似方案和时间复杂性。最后针对以上这两个问题做出了总结。