Scheduling tree-structured tasks with restricted execution times

Jianzhong Du; Joseph Y.T. Leung

doi:10.1016/0020-0190(88)90206-2

Scheduling tree-structured tasks with restricted execution times

Jianzhong Du, Joseph Y.T. Leung

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.

Original language	English (US)
Pages (from-to)	183-188
Number of pages	6
Journal	Information Processing Letters
Volume	28
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(88)90206-2
State	Published - Jul 29 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Signal Processing
Computer Science Applications

Keywords

NP-completeness
NP-hardness
multiprocessor scheduling
schedule length
tree-structured task system

Access to Document

10.1016/0020-0190(88)90206-2

Cite this

@article{b3795ec9714c47a79ffed3ad7152c4aa,

title = "Scheduling tree-structured tasks with restricted execution times",

abstract = "In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.",

keywords = "NP-completeness, NP-hardness, multiprocessor scheduling, schedule length, tree-structured task system",

author = "Jianzhong Du and Leung, {Joseph Y.T.}",

year = "1988",

month = jul,

day = "29",

doi = "10.1016/0020-0190(88)90206-2",

language = "English (US)",

volume = "28",

pages = "183--188",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Scheduling tree-structured tasks with restricted execution times

AU - Du, Jianzhong

AU - Leung, Joseph Y.T.

PY - 1988/7/29

Y1 - 1988/7/29

N2 - In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.

AB - In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.

KW - NP-completeness

KW - NP-hardness

KW - multiprocessor scheduling

KW - schedule length

KW - tree-structured task system

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

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

U2 - 10.1016/0020-0190(88)90206-2

DO - 10.1016/0020-0190(88)90206-2

M3 - Article

AN - SCOPUS:0024051009

SN - 0020-0190

VL - 28

SP - 183

EP - 188

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Scheduling tree-structured tasks with restricted execution times

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this