一台批处理机一次可以同时加工多个工件（称为一批），每批工件有相同的开工和完工时间，加工时间等于其中最长工件的加工时间。本文研究单台批处理机上有就绪时间和截止时间约束的n个等长度工件的排序问题，目标是求一个可行时间表。就该问题，Baptiste已经提出了一个复杂性为O（n⁸）的算法，在此基础上，本文推广Garey等人关于对应的经典排序问题的算法，得到了一个复杂性为O（n²）的算法。算法分两个阶段执行：在阶段I，算法找出所谓的禁止开工区间，在这些区间中将不允许有工件开工；在阶段II，算法从时刻零开始，每当机器有空闲且不属于禁止开工区间的时候，就按照最早截止时间优先规则从已就绪的未加工工件中选择尽可能多的工件作为一批进行加工，若当前的机器空闲时刻属于某个禁止开工区间，则首先更新其到该禁止开工区间的右端点再进行决策。