所谓排序，即在一定的资源限制下更好地安排和完成一些任务，使得期望的效益或目标达到最优值或理想值。排序论在工业制造领域，计算机科学，物流运输管理等领域都有广泛地应用，具有重要的理论研究价值和广泛的应用前景。　　本论文主要研究的是工件具有相容性的多台平行分批处理机的在线排序问题。在线排序是指每个工件都有一个到达时间，决策者在工件到达之后才知晓其信息。对到达的工件，排序者可以立即安排加工，也可推迟安排加工。平行分批排序是指工件在加工过程中被分成若干批，每个批中允许同时放置多个工件，但工件总数不得超过批容量。批容量通常分为有限和无限两种情形。同一批中的工件有相同的开工时间和完工时间。批的加工时间定义为该批中加工时间最大的工件的加工时间。工件具有相容性约束一般分为两种类型：　　（1）工件具有区间相容性；　　（2）工件属于不同的工件组。工件具有区间相容性是指，每一个工件都有一个可以用区间表示的信息，两个工件相容当且仅当两工件的区间相交，此时，二者可以放在同一个批中加工。工件属于不同工件组是指任意一个工件都属于某个确定的工件组，只有同一个工件组中的工件才能够放在同一个批中加工。本文研究的排序问题的目标函数是最小化最大完工时间。　　本文的主要成果如下：　　（1）对排序问题Pm｜on-line,rj,G=INT,p-batch,b=∞｜Cmax，本文证明了任意一个在线算法的竞争比都不小于2，并设计出竞争比为2+(m-1)/(m+1)的在线算法，且该在线算法是单机情形下的一个最优在线算法；对工件加工时间相同的特殊情形，设计出了一个竞争比为2的最优在线算法。　　（2）对排序问题Pm｜on-line,rj,family,p-batch,b=∞｜Cmax本文证明了任意一个在线算法的竞争比都不小于2，并设计出了一个竞争比为7/3-1(3m)的在线算法，且证明这个界是可达的；对工件加工时间相同的特殊情形，设计出了一个竞争比为2的最优在线算法。