Open Problem—Size-Based Scheduling with Estimation Errors

For queueing systems, leveraging knowledge of job sizes to perform size-based scheduling leads to policies with attractive performance characteristics. Although there is a body of literature in this area, in the interest of space, we highlight one classical result: for a single-server system, the shortest remaining processing time (SRPT) policy (priority is given to the job closest to completion) is known to minimize the mean response time ( …