Previous research has shown that inaccurate estimates of execution times can lead to better backfilling schedules. We characterize this effect on several workloads, and show that average slowdowns can be effectively reduced by systematically lengthening estimated execution times. Further, we show that the average job slowdown metric can be addressed directly by sorting jobs by increasing execution time. Finally, we modify our sorting scheduler to ensure that incoming jobs can be given hard guarantees. The resulting scheduler guarantees to avoid starvation, and performs significantly better than previous backfilling schedulers.

@article{keleher00,
	title = "Attacking the Bottlenecks in Backfilling Schedulers",
	author = "Pete Keleher and Dmitry Zotkin and Dejan Perkovic",
	journal = {Cluster Computing: The Journal of Networks},
	volume = {3},
	issue = {4},
	year = {2000},
}