排序问题是一类重要的组合优化问题，它被广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，一直受到国内外学术界的重视．分批排序问题和在线排序问题是两类新兴的现代排序模型，有着重要的应用背景，而带配送时间的在线分批排序问题是排序论在供应链理论中应用的重要体现．本文主要研究带配送配送时间的在线分批排序问题．论文共分为三章：第一章主要介绍了排序问题产生的背景，计算复杂性理论，分批排序，在线与半在线排序的概念以及本文的主要结果和创新点．第二章主要对分批加工在两种配送模型下的在线算法进行了分析．这两种模型分别为：分批加工、独立配送模型以及分批加工、按批配送模型．首先证明了在独立配送模型下我们考虑的两个问题的竞争比均为1+δ，其中δ＝（?）；并首次提出了独立配送模型下的一个半在线理论；首次提出了一种新的配送模型：按批配送模型，并对按批配送与独立配送的同一个算法的竞争比进行了分析．第三章首次研究了成比例排序问题BPP的同类机分批排序，目标函数为极小化工件的最大完工时间，这类问题也是NP--完备的．我们对同类机的情形给出了近似算法QBFF和QM，并且证明了它们的竞争比分别不超过兰b/a+1（其中a=min{a_j}）和3/2+ρ（其中ρ=（m-1）S₁/（?）S_j）．