Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2002 | metadata_only
Journal Article

Asymptotic convergence of scheduling policies with respect to slowdown


We explore the performance of an M/GI/1 queue under various scheduling policies from the perspective of a new metric: the slowdown experienced by the largest jobs. We consider scheduling policies that bias against large jobs, towards large jobs, and those that are fair, e.g., processor-sharing (PS). We prove that as job size increases to infinity, all work conserving policies converge almost surely with respect to this metric to no more than 1/(1−ρ), where ρ denotes the load. We also find that the expected slowdown under any work conserving policy can be made arbitrarily close to that under PS, for all job sizes that are sufficiently large.

Additional Information

© 2002 Elsevier Science B.V. This work was supported by NSF Career grant CCR-0133077, NSF ITR grant 99-167 ANI-0081396 and by Spinnaker Networks via Pittsburgh Digital Greenhouse grant 01-1.

Additional details

August 21, 2023
August 21, 2023