A generalized bound on Lpt sequencing

E. G. Coffman; Ravi Sethi

doi:10.1145/800200.806205

A generalized bound on Lpt sequencing

E. G. Coffman, Ravi Sethi

Computer Science

Research output: Contribution to conference › Paper › peer-review

29 Scopus citations

Abstract

For a number of NP-complete sequencing problems [C], the worst-case performance of heuristics has been bounded relative to optimal performance. The bounds are usually shown to be best in the sense that they are achievable. However, when these bounds are based on a single, pathological example, they are not as informative as might be desired. Such is largely the case with Graham's bound [G] of 4/3- 1/3m on the performance of largest-processing-time- first (LPT) sequencing for the classical problem of minimizing schedule lengths, assuming independent tasks on m ≥ 2 identical processors.

Original language	English (US)
Pages	306-310
Number of pages	5
DOIs	https://doi.org/10.1145/800200.806205
State	Published - Mar 29 1976
Event	1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation, SIGMETRICS 1976 - Cambridge, United States Duration: Mar 29 1976 → Mar 31 1976

Other

Other	1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation, SIGMETRICS 1976
Country/Territory	United States
City	Cambridge
Period	3/29/76 → 3/31/76

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1145/800200.806205

Cite this

@conference{c513fa0005814d1e86287ee3db33c694,

title = "A generalized bound on Lpt sequencing",

abstract = "For a number of NP-complete sequencing problems [C], the worst-case performance of heuristics has been bounded relative to optimal performance. The bounds are usually shown to be best in the sense that they are achievable. However, when these bounds are based on a single, pathological example, they are not as informative as might be desired. Such is largely the case with Graham's bound [G] of 4/3- 1/3m on the performance of largest-processing-time- first (LPT) sequencing for the classical problem of minimizing schedule lengths, assuming independent tasks on m ≥ 2 identical processors.",

author = "Coffman, {E. G.} and Ravi Sethi",

year = "1976",

month = mar,

day = "29",

doi = "10.1145/800200.806205",

language = "English (US)",

pages = "306--310",

note = "1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation, SIGMETRICS 1976 ; Conference date: 29-03-1976 Through 31-03-1976",

}

TY - CONF

T1 - A generalized bound on Lpt sequencing

AU - Coffman, E. G.

AU - Sethi, Ravi

PY - 1976/3/29

Y1 - 1976/3/29

N2 - For a number of NP-complete sequencing problems [C], the worst-case performance of heuristics has been bounded relative to optimal performance. The bounds are usually shown to be best in the sense that they are achievable. However, when these bounds are based on a single, pathological example, they are not as informative as might be desired. Such is largely the case with Graham's bound [G] of 4/3- 1/3m on the performance of largest-processing-time- first (LPT) sequencing for the classical problem of minimizing schedule lengths, assuming independent tasks on m ≥ 2 identical processors.

AB - For a number of NP-complete sequencing problems [C], the worst-case performance of heuristics has been bounded relative to optimal performance. The bounds are usually shown to be best in the sense that they are achievable. However, when these bounds are based on a single, pathological example, they are not as informative as might be desired. Such is largely the case with Graham's bound [G] of 4/3- 1/3m on the performance of largest-processing-time- first (LPT) sequencing for the classical problem of minimizing schedule lengths, assuming independent tasks on m ≥ 2 identical processors.

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

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

U2 - 10.1145/800200.806205

DO - 10.1145/800200.806205

M3 - Paper

AN - SCOPUS:84989674062

SP - 306

EP - 310

T2 - 1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and Evaluation, SIGMETRICS 1976

Y2 - 29 March 1976 through 31 March 1976

ER -

A generalized bound on Lpt sequencing

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this