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.

@inProceedings{zotkin-hpdc99,
	title = "Job-Length Estimation and Performance in Backfilling Schedulers",
	author = "Dmitry Zotkin and Pete Keleher",
	booktitle = {The 8th High Performance Distributed Computing Conference (HPDC)},
	month = {August},
	year = {1999},
}