A Caltech Library Service

Asymptotic convergence of scheduling policies with respect to slowdown

Harchol-Balter, Mor and Sigman, Karl and Wierman, Adam (2002) Asymptotic convergence of scheduling policies with respect to slowdown. Performance Evaluation, 49 (1-4). pp. 241-256. ISSN 0166-5316. doi:10.1016/s0166-5316(02)00132-3.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
NSF99-167 ANI-0081396
Pittsburgh Digital Greenhouse01-1
Subject Keywords:Scheduling; Conservation; Large jobs; Convergence; Shortest-remaining-processing-time; Processor-sharing
Issue or Number:1-4
Record Number:CaltechAUTHORS:20201020-074935944
Persistent URL:
Official Citation:Mor Harchol-Balter, Karl Sigman, Adam Wierman, Asymptotic convergence of scheduling policies with respect to slowdown, Performance Evaluation, Volume 49, Issues 1–4, 2002, Pages 241-256, ISSN 0166-5316, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106160
Deposited By: Tony Diaz
Deposited On:20 Oct 2020 19:12
Last Modified:16 Nov 2021 18:51

Repository Staff Only: item control page