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

Joseph Y.T. Leung, Jennifer Whitehead

Research output: Contribution to journalArticlepeer-review

696 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 languageEnglish (US)
Pages (from-to)237-250
Number of pages14
JournalPerformance Evaluation
Volume2
Issue number4
DOIs
StatePublished - Dec 1982

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

Fingerprint Dive into the research topics of 'On the complexity of fixed-priority scheduling of periodic, real-time tasks'. Together they form a unique fingerprint.

Cite this