Algorithms for Scheduling Tasks on Unrelated Processors

Ernest Davis, Jeffrey M. Jaffe

Research output: Contribution to journalArticlepeer-review

Abstract

Several algorithms are presented for the nonpreemptlve assignment of n independent tasks to m unrelated processors One algorithm requires polynomial Ume in n and m and IS at most 2√m times worse than optimal in the worst case This is the best polynomial-time algorithm known for scheduling such sets of tasks. An algorithm with slightly better worst case performance requires polynomial time in n but exponential tume in m This 1s the best algorithm known that requires time [formula omitted] for every fixed value of m.

Original languageEnglish (US)
Pages (from-to)721-736
Number of pages16
JournalJournal of the ACM (JACM)
Volume28
Issue number4
DOIs
StatePublished - Oct 1 1981

Keywords

  • largest processing time
  • nonpreemptlve schedules
  • performance ratio
  • unrelated processors
  • worst case fimshlng time

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Algorithms for Scheduling Tasks on Unrelated Processors'. Together they form a unique fingerprint.

Cite this