Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Minimizing weighted flow time

Minimizing weighted flow time We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O ( k )-competitive for k weight classes. This implies an O (log W )-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O (log n + log P )-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ε)-speed, (1 +1/ε)-competitive online algorithm. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Minimizing weighted flow time

Download PDF
14 pages

Loading next page...
 
/lp/association-for-computing-machinery/minimizing-weighted-flow-time-WTnb5prKzh
Publisher
Association for Computing Machinery
Copyright
Copyright © 2007 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1290672.1290676
Publisher site
See Article on Publisher Site

Abstract

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O ( k )-competitive for k weight classes. This implies an O (log W )-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O (log n + log P )-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ε)-speed, (1 +1/ε)-competitive online algorithm.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2007

There are no references for this article.