分批排序问题，是一类重要的组合优化问题，主要是基于大规模的现代化生产流水作业线提出的。本文研究的问题是：给定工件集J=｛1，2，…，n｝，对每个工件j有释放时间rj，加工时间p，以及大小sj·有一台批处理机器，其容量为1。若干个大小之和不超过1的工件可分作一批同时加工，同一批中的工件都释放后才可以开始加工，加工时间为批中工件的最大加工时间。我们的目标是确定如何分批及排序，使最后加工的批的完工时间最小.　　 本文由三章组成．第一章绪论主要介绍了组合优化和分批排序的基本概念和主要研究成果。第二章研究了两个释放时间的分批排序问题1｜B，rj∈{0，r｝，sj｜Cmax，设计了近似比不超过(?)+1(≈2.732)和((?)+7)/8(≈2.461)的两个算法。并针对任意释放时间的一般问题设计了两个算法，给出了其下界.第三章研究1｜B，sj，｜Cmax，当P≠NP时，已知该问题近似比的下界是3/2．我们采用取整，拆分等方法，对其设计了(3/2+ε)-近似算法．