Algorithms for Scheduling Tasks on Unrelated Processors

Ernest Davis; Jeffrey M. Jaffe

doi:10.1145/322276.322284

Algorithms for Scheduling Tasks on Unrelated Processors

Ernest Davis, Jeffrey M. Jaffe

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	721-736
Number of pages	16
Journal	Journal of the ACM (JACM)
Volume	28
Issue number	4
DOIs	https://doi.org/10.1145/322276.322284
State	Published - 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

Access to Document

10.1145/322276.322284

Cite this

@article{44704f36dc9d4581838ef704331f0bfd,

title = "Algorithms for Scheduling Tasks on Unrelated Processors",

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.",

keywords = "largest processing time, nonpreemptlve schedules, performance ratio, unrelated processors, worst case fimshlng time",

author = "Ernest Davis and Jaffe, {Jeffrey M.}",

year = "1981",

month = oct,

day = "1",

doi = "10.1145/322276.322284",

language = "English (US)",

volume = "28",

pages = "721--736",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Algorithms for Scheduling Tasks on Unrelated Processors

AU - Davis, Ernest

AU - Jaffe, Jeffrey M.

PY - 1981/10/1

Y1 - 1981/10/1

N2 - 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.

AB - 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.

KW - largest processing time

KW - nonpreemptlve schedules

KW - performance ratio

KW - unrelated processors

KW - worst case fimshlng time

UR - http://www.scopus.com/inward/record.url?scp=0019625166&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0019625166&partnerID=8YFLogxK

U2 - 10.1145/322276.322284

DO - 10.1145/322276.322284

M3 - Article

AN - SCOPUS:0019625166

SN - 0004-5411

VL - 28

SP - 721

EP - 736

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 4

ER -

Algorithms for Scheduling Tasks on Unrelated Processors

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this