Scheduling heterogeneous processors isn't as easy as you think

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider preemptive online scheduling algorithms to minimize the total weighted/unweighted flow time plus energy for speed-scalable heterogeneous multiprocessors. We show that the well-known priority scheduling algorithms Highest Density First, Weighted Shortest Elapsed Time First, and Weighted Late Arrival Processor Sharing, are not O(1)-speed O(1)-competitive for the objective of weighted flow even in the special case of fixed variable speed processors (aka the related machines setting). This illustrates that scheduling heterogeneous multiprocessors is a different, and algorithmically more challenging problem, than scheduling homogeneous multiprocessors. We then show that a variation of the non-clairvoyant algorithm Late Arrival Processor Sharing coupled with a non-obvious speed scaling algorithm is scalable for the objective of unweighted flow plus energy on speed-scalable multiprocessors. This is the first provably scalable non-clairvoyant algorithm on heterogeneous multi-processors, even in the related machines setting, for the objective of total (unweighted) flow time.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781611972108
StatePublished - 2012
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Scheduling heterogeneous processors isn't as easy as you think'. Together they form a unique fingerprint.

Cite this