n个作业{1， 2， …， n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi（1≤i≤n），批处理作业调度问题（batch-job scheduling problem）要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。（备注：这个定义应该是“流水作业调度问题”的描述，“批处理作业调度问题”的一般关键词是“时间和”，不是“时间”，所以这项目应该是更改词条名比较合适，改成“流水作业调度问题”。）显然，批处理作业的一个最优调度应使机器1没有空闲时间，且机器2的空闲时间最小。可以证明，存在一个最优作业调度使得在机器1和机器2上作业以相同次序完成。