OPTIMAL TWO PROCESSOR SCHEDULING OF TREE PRECEDENCE CONSTRAINED TASKS WITH TWO EXECUTION TIMES.

Kazuo Nakajima; Joseph Y.T. Leung; S. Louis Hakimi

OPTIMAL TWO PROCESSOR SCHEDULING OF TREE PRECEDENCE CONSTRAINED TASKS WITH TWO EXECUTION TIMES.

Kazuo Nakajima, Joseph Y.T. Leung, S. Louis Hakimi

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

Abstract

Authors consider a set of n tasks with a tree precedence relation and execution time of 1 or 2 units, and present an O(n log n) time algorithm to find a minimum length schedule of these tasks on two identical processors. Possible generalizations, as well as the relations between this algorithm and other scheduling algorithms, are described.

Original language	English (US)
Pages (from-to)	320-330
Number of pages	11
Journal	Performance Evaluation
Volume	1
Issue number	4
State	Published - 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Modeling and Simulation
Hardware and Architecture
Computer Networks and Communications

Cite this

@article{fa71f1c14ed047df885d00670a15d0fc,

title = "OPTIMAL TWO PROCESSOR SCHEDULING OF TREE PRECEDENCE CONSTRAINED TASKS WITH TWO EXECUTION TIMES.",

abstract = "Authors consider a set of n tasks with a tree precedence relation and execution time of 1 or 2 units, and present an O(n log n) time algorithm to find a minimum length schedule of these tasks on two identical processors. Possible generalizations, as well as the relations between this algorithm and other scheduling algorithms, are described.",

author = "Kazuo Nakajima and Leung, {Joseph Y.T.} and Hakimi, {S. Louis}",

year = "1981",

language = "English (US)",

volume = "1",

pages = "320--330",

journal = "Performance Evaluation",

issn = "0166-5316",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - OPTIMAL TWO PROCESSOR SCHEDULING OF TREE PRECEDENCE CONSTRAINED TASKS WITH TWO EXECUTION TIMES.

AU - Nakajima, Kazuo

AU - Leung, Joseph Y.T.

AU - Hakimi, S. Louis

PY - 1981

Y1 - 1981

N2 - Authors consider a set of n tasks with a tree precedence relation and execution time of 1 or 2 units, and present an O(n log n) time algorithm to find a minimum length schedule of these tasks on two identical processors. Possible generalizations, as well as the relations between this algorithm and other scheduling algorithms, are described.

AB - Authors consider a set of n tasks with a tree precedence relation and execution time of 1 or 2 units, and present an O(n log n) time algorithm to find a minimum length schedule of these tasks on two identical processors. Possible generalizations, as well as the relations between this algorithm and other scheduling algorithms, are described.

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

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

M3 - Article

AN - SCOPUS:0019676864

SN - 0166-5316

VL - 1

SP - 320

EP - 330

JO - Performance Evaluation

JF - Performance Evaluation

IS - 4

ER -

OPTIMAL TWO PROCESSOR SCHEDULING OF TREE PRECEDENCE CONSTRAINED TASKS WITH TWO EXECUTION TIMES.

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this