排序问题是组合优化中的一类重要问题,它的一般定义可描述为:一些机器在一定条件下加工若干个工件,排序决策者需要将机器按时间分配给工件,使得某个或某些目标函数达到最优。本文主要研究工件具有相容性约束和友好到达时间的在线排序问题。在在线排序中,工件的信息是随时间逐步释放的,排序决策者只能根据当前已到达的工件的信息来做决策,而对未来到达的工件的任何信息是一无所知的,并且一旦做出决策,就不允许改变。在不超过批容量的情况下,一台平行批处理机可以同时加工多个工件。批的加工时间定义为该批中加工时间最长工件的加工时间。因此,同一批中的工件具有相同的开工时间和相同的完工时间。文献中关于工件具有相容性约束的平行批处理排序问题包括两类模型:一类是相容工件族,每一个工件都属于一个工件族,只有来自同一族的工件才可以在同一批被加工。另一类是工件具有加工时间区间相容性,每一个工件都有一个标准的加工时间,而它的实际加工时间属于由标准加工时间决定的一个时间区间。如果两个工件的加工时间区间的交集非空,则二者是相容的,并可以放在同一批中加工。本文将主要研究后者。在这里,假设工件具有友好到达时间,即机器在忙碌时不会有新的工件到达。目标函数是最小化最大完工时间。本文第一章主要介绍了排序论的研究背景、主要应用和排序论的基本概念。第二章主要介绍了在线排序、平行分批排序以及它们各自的研究现状,并介绍了在线排序问题的一般研究方法。第三章针对工件具有相容性约束和友好到达时间的在线排序问题进行具体研究:找出了该在线排序问题所有在线算法竞争比的一个下界,然后根据此下界设计出了一个在线算法,接着对此在线算法进行竞争比的理论分析,并最终证明了所设计的在线算法是一个最好可能的在线算法。该论文有图11幅,有参考文献74篇。