回填（backfilling）被认为可以提高系统利用率并且已在几种排程软件中实现。回填的工作原理是通过发现存在于2D图表中的“洞”，将较小的、能“进洞”的任务提前处理。常见的回填有两种，保守的和积极的。

并行任务

并行任务排程通常被看作是一张2维图表：一个轴代表时间，另一个代表所需处理器的数量。每个任务可以被想象成一个长方形，高是用户期望值（时间）而宽是所需处理器数。并行排程策略在过去已被广泛地研究过。最简单的排程方法莫过于使用先来先服务策略（FCFS）。但这种方法会使系统利用率低下。

回填

在保守的回填中，每个任务在进入系统时都会被赋予一个保留值。当不会造成前面的任务延迟时，一个较小的任务才会被提前。在积极的回填中，只有队首的任务才会被赋予保留值。只要它不影响处于队首的任务，一个较小的任务就会被提前处理。在FCFS策略下，一个任务的优先级是它的等待时间（wait time）。其它的优先级策略如最短任务优先（SF），扩展因素（XF）也可以被使用。在SF下，一个任务的优先级与其用户期望值（user estimated run time）成反比。在XF下，任务的优先级为由以下公式定义的XFactor（扩展因素）

XFactor = (Wait time + Estimated Run time) / Estimated Run time

最常见的用以衡量排程方案效果的指标是平均完成时间和平均总体延迟（average bounded slowdown）在我们的研究中也采用了这些指标。一个任务的总体延迟被如下定义：

Bounded Slowdown = (Wait time + Max(Run time, 10))/ Max(Run time, 10)

门限值10用于限制耗时极短的任务对于观测指标的影响