排序是组合最优化的一个重要分支，它广泛地应用于管理科学、计算机科学和工程技术等很多领域，也是运筹学研究的重要分支。分批排序是排序中的重要部分，它起于上世纪末，来源于半导体生产中的芯片测试过程,是一类新型排序问题,有着很重要的应用价值,在理论上也有重要的意义.因此，分批排序问题在近年来受到了国内外学者、专家、及企业家的高度关注,新的研究成果也是不断出现.本文就分批排序问题的新进展作了一些介绍,指出了它独有的魅力,并给出了丰富的参考文献。我们这篇文章主要研究了n个工件，工件J j, j=1,2,…,n的体积为s j工时为p j，在两台平行机上加工，然后分批运输的问题。工件有体积是指在被运输时所占的物理空间，而且此文中我们假设运输车辆容量为z且只有一辆。本文中把车看做箱子，先把工件按装箱问题分箱，同箱物体为一批，再分批加工、运输。我们的目标函数是求完工时间（车把工件全部运输到目的地后回到原出发点的时间）的最小值。由[1]知它是NP难的，本文分为两章，具体内容如下：第一章是绪论，主要写了排序方面的一些基本定义和知识、及本文的背景、意义。第二章首先介绍相关知识，其次提出本文研究的问题P2→D, k=1|v=1, c=z|Cmax，然后在算法H2的基础上写出了问题的改进算法MH2′及其算法证明，最后得出最差性能比为1.5+ε（ε>0，可任意趋近与0）。由[1]知一台机器时最差性能比的下界不会小于1.5除非P=NP，所以本文的最差性能比的下界也不会小于1.5。