Robustness to Estimation Errors for Size-Aware Scheduling

Abstract

When scheduling size-aware single server systems, Shortest Remaining Processing Time (SRPT) has strong optimality properties - it minimizes the number of jobs at the server and as a consequence, the mean response time. A major caveat of SRPT is that it requires job sizes a priori. This thesis examines a scenario that is likely to occur in practice, where only estimates of job sizes are available. A single server model and a multi-server model using SRPT are compared to a Class-Based policy that is designed to increase robustness to estimation errors. In the single server model we observe from simulations that such robustness is crucial to achieve good performance. In contrast, we observe that a multi-server system is inherently more robust than a single server system. Both policies work well with the estimation errors in the multi-server system.