CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20201020-074935944

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20201020-074935944

Abstract

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
https://doi.org/10.1016/s0166-5316(02)00132-3DOIArticle
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.
Funders:
Funding AgencyGrant Number
NSFCCR-0133077
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:https://resolver.caltech.edu/CaltechAUTHORS:20201020-074935944
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, https://doi.org/10.1016/S0166-5316(02)00132-3. (http://www.sciencedirect.com/science/article/pii/S0166531602001323)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106160
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Oct 2020 19:12
Last Modified:20 Oct 2020 19:12

Repository Staff Only: item control page