Multi-processor scheduling to minimize flow time with ε resource augmentation

Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar

Research output: Contribution to journalConference articlepeer-review


We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1 + ε)m machines or m machines of speed (1 + ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs. The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their Lp norms, for ay fixed p ≥ 1.

Original languageEnglish (US)
Pages (from-to)363-372
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2004
Externally publishedYes
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004


  • Flow Time
  • Load Balancing
  • Multi-processor Scheduling
  • Online Algorithms
  • Resource Augmentation
  • Stretch

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Multi-processor scheduling to minimize flow time with ε resource augmentation'. Together they form a unique fingerprint.

Cite this