本文的内容分三大部分：第一部分提出了三种新型分批排序模型：(1)具有主次指标的单机分批排序问题(第二章)；(2)具有三重指标的单机平行分批排序问题(第三章)；(3)单机准时分批排序问题(第四章)．对于这些问题的研究在文献中几乎没有见到，而这些模型具有很强的应用背景和理论研究意义．本文对这些新型排序模型给出了若干研究结果．第二部分对一些现有单机分批排序问题最优解的结构性质进行了系统研究(第五章)．对于分批排序结构性质的研究在文献中也没见到．第三部分研究了工件在限选机器上加工的若干平行机分批排序问题(第六章)． 在第二章中，本文研究了具有主次指标的单机分批排序问题，其主要结果如下：证明了带有到达时间、主指标为最大完工时间的两个问题是强NP．困难的：第一个是批容量有限制、次指标为总存储费用的平行分批排序问题；第二个是批容量无限制、次指标为最大延迟的继列分批排序问题．给出了三个批容量无限制问题的多项式时间算法：第一个是带有到达时间、主指标为最大完工时间、次指标为占用机器总时间的继列分批排序问题；第二个是主指标为最大延迟、次指标为最大完工时间的平行分批排序问题；第三个是主指标为最大延迟、次指标为误工总数的平行分批问题．此外，给出了主指标为最大延迟、次指标为关于Cj的任意正规函数、批容量无限制的平行分批模型的拟多项式时间算法． 在第三章中，对于具有三重指标的单机平行分批排序问题，主要给出了两种批容量无限制平行分批模型的O(n2)时间算法：第一个问题是带有到达时间、三个指标依次为最大完工时间、占用机器的总时间、总存贮费用；第二个问题的三个指标依次为最大延迟、最大完工时间、关于工件完工时间的任意正规函数． 在第四章中，对于若干批容量无限制的继列分批和平行分批准时排序问题，给出了当每批恰有b个工件且工件有相同交工期时的O(nlogn)时间算法． 第五章主要研究批容量无限制的继列分批和平行分批问题最优特殊分批的存在性条件，目标函数分别为：加权完工时间之和、总完工时间、完工时间平方之和及最大延迟．这里，特殊分批主要指仅分一批和恰分n批． 第六章主要讨论当工件的加工长度均为1、每个工件Jj只能在限选机器(允许加工的机器)Mj上加工时的平行机分批排序问题，其中朋f是机器集合的某个子集．已知分批排序问题PIs-batch；Pj=1；A4jICm越可归结为非分批问题Plnj=1；A4jIemax．Pinedo(1995)给出了当子集族{Mj}是嵌套集族时的LFJ(1eastflexiblejobfirst)算法．这里给出了子集族{Mj}为一般情形的多项式时间算法．作为子集族{MJ)为嵌套情形的推广，本文研究了子集族{Mj}是凸的情形并给出了有效算法.