排序论（Scheduling)又被称作为时间表论，它在组合最优化理论中占有很是重要的地位.作为该领域中的一门学科，排序论由于其较强的实际操作特性，在管理学、物流学以及计算机学等许多学科领域被广泛应用，引起了国内国外许多学者的强烈的兴趣.　　在近代排序问题中，在线类的排序和分批类的排序问题，是新兴起的现代排序的模型.多台加工处理机的在线排序问题则是排序论对于实际的生活生产中情况的重要反映，也是对实际社会经济生产力与生产活动的重要体现.文章主要研究了多台同类机的分批的在线排序问题.　　论文共分为四章：　　第一章针对于排序问题产生的历史背景，计算的复杂性理论，分批排序的概念，在线排序的相关定义以及其它的基本知识进行了详细的阐述，并且简单介绍了本文的主要结果和创新之处.　　第二章探讨了一类多台处理机的在线排序问题.主要考虑了工件满足一致性的，批容量无界的两台同类机的在线分批排序问题，目标为极小化工件的最大完工时间.　　对于该问题，我们讨论的是随着到达时间的延后，每一时刻到达的工件集中最大的工件长度会越来越大，并且大于前一到达时刻中到达的工件集中最大的工件长度（用三元素法表示为Q2｜ri＜r j?Pi≤Pj,B=∞,on-line｜Cmax).在本章的设计中，我们假设两台同类机的速度分别是1和s,且s≥1.首先，给出了一个在线算法，证明了这个算法的竞争比不超过s+α,其中α为α2+sα-1=0的正根.当s=1时,该算法的竞争比不超过1.618.　　第三章同样探讨了一类多台处理机的在线排序问题.与第二章不同之处是，我们考虑了工件的一般情况，即工件有到达时间的，批容量无界的两台同类机的在线分批排序问题，目标为极小化工件的最大完工时间.用三元素法表示为Q2|ri,B=∞,on-line|Cmax).在本章的设计中，我们沿用第二章中提到的在线算法，并且分析了这个算法的竞争比不超过(s+α)2.　　第四章考虑了工件满足一致性的，批容量无界的两台同类机的在线分批排序问题，目标为极小化工件的最大流程.　　对于这类问题，我们讨论的是随着到达时间的延后，每一时刻到达的工件集中最大的工件长度会越来越小，并且小于前一到达时刻的到达的工件集中最大的工件长度（用三元素法表示为Q2｜ri＜rj?pi≥pj,B=∞,on-line｜Fmax).在本章的设计中，我们依然沿用第:章中提供的在线算法，并且证明了这个算法的竞争比不超过1+1α.