On the complexity of fixed-priority scheduling of periodic, real-time tasks

Joseph Y.T. Leung; Jennifer Whitehead

doi:10.1016/0166-5316(82)90024-4

On the complexity of fixed-priority scheduling of periodic, real-time tasks

Joseph Y.T. Leung, Jennifer Whitehead

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

754 Scopus citations

Abstract

We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m ≥ 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.

Original language	English (US)
Pages (from-to)	237-250
Number of pages	14
Journal	Performance Evaluation
Volume	2
Issue number	4
DOIs	https://doi.org/10.1016/0166-5316(82)90024-4
State	Published - Dec 1982
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Modeling and Simulation
Hardware and Architecture
Computer Networks and Communications

Keywords

Fixed-priority Scheduling
Multiprocessors System
NP-completeness
Optimal Scheduling Algorithms
Periodic Real-time Task

Access to Document

10.1016/0166-5316(82)90024-4

Cite this

@article{6e6455fa10e3488e8d267ad7e5643a4d,

title = "On the complexity of fixed-priority scheduling of periodic, real-time tasks",

abstract = "We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m ≥ 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.",

keywords = "Fixed-priority Scheduling, Multiprocessors System, NP-completeness, Optimal Scheduling Algorithms, Periodic Real-time Task",

author = "Leung, {Joseph Y.T.} and Jennifer Whitehead",

year = "1982",

month = dec,

doi = "10.1016/0166-5316(82)90024-4",

language = "English (US)",

volume = "2",

pages = "237--250",

journal = "Performance Evaluation",

issn = "0166-5316",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - On the complexity of fixed-priority scheduling of periodic, real-time tasks

AU - Leung, Joseph Y.T.

AU - Whitehead, Jennifer

PY - 1982/12

Y1 - 1982/12

N2 - We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m ≥ 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.

AB - We consider the complexity of determining whether a set of periodic, real-time tasks can be scheduled on m ≥ 1 identical processors with respect to fixed-priority scheduling. It is shown that the problem is NP-hard in all but one special case. The complexity of optimal fixed-priority scheduling algorithm is also discussed.

KW - Fixed-priority Scheduling

KW - Multiprocessors System

KW - NP-completeness

KW - Optimal Scheduling Algorithms

KW - Periodic Real-time Task

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

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

U2 - 10.1016/0166-5316(82)90024-4

DO - 10.1016/0166-5316(82)90024-4

M3 - Article

AN - SCOPUS:0020271514

SN - 0166-5316

VL - 2

SP - 237

EP - 250

JO - Performance Evaluation

JF - Performance Evaluation

IS - 4

ER -

On the complexity of fixed-priority scheduling of periodic, real-time tasks

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this