Approximation Algorithms for Average Stretch Scheduling

被引:0
作者
Michael A. Bender
S. Muthukrishnan
Rajmohan Rajaraman
机构
[1] Department of Computer Science,Department of Computer Science
[2] SUNY,College of Computer & Information Science
[3] Rutgers University,undefined
[4] Northeastern University,undefined
来源
Journal of Scheduling | 2004年 / 7卷
关键词
Scheduling algorithms; approximation algorithms; average stretch;
D O I
暂无
中图分类号
学科分类号
摘要
We study the basic problem of preemptive scheduling of a stream of jobs on a single processor. Consider an on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is the completion time of job i, then the flow time of i is C(i) − r(i) and the stretch of i is the ratio of its flow time to its processing time; that is, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{{C(i) - r(i)}}{{p(i)}}$$\end{document}. Flow time measures the time that a job is in the system regardless of the service it requests; the stretch measure relies on the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times.
引用
收藏
页码:195 / 222
页数:27
相关论文
共 9 条
  • [1] Bast H.(2000)On scheduling parallel tasks at twilight Theory Comput. Syst 33 489-563
  • [2] Harchol-Balter M.(1999)Task assignment in a distributed server J. Parallel and Distribut. Comput. 59 204-228
  • [3] Crovella M.(1994)Nonclairvoyant scheduling Theoreti. Comput. Sci. 130 17-47
  • [4] Murta C.(2002)An adversarial model for distributed dynamic load balancing J. Interconnect. Networks 3 35-47
  • [5] Motwani R.(undefined)undefined undefined undefined undefined-undefined
  • [6] Phillips S.(undefined)undefined undefined undefined undefined-undefined
  • [7] Torng E.(undefined)undefined undefined undefined undefined-undefined
  • [8] Muthukrishnan S.(undefined)undefined undefined undefined undefined-undefined
  • [9] Rajaraman R.(undefined)undefined undefined undefined undefined-undefined