Optimal resource assignment of preemptive periodic tasks on multiple processors

B. A. Kijowski, U. S. Palekar

Research output: Contribution to journalArticlepeer-review

Abstract

In this article we examine the problem of preemptively scheduling periodically occurring tasks on a system of parallel processors so as to maximize a linear function of the tasks completed. We show that polynomial time solutions exist for all the no-deadline problems, derive an O(n log n) algorithm for the preemptive parallel processor problem, and include results for minimization of number of processors and maximization of flexibility for handling additional tasks. We present lower and upper bounds on the number of preemptions. We show that all optimization problems with either arbitrary or next-request deadlines are NP-hard.

Original languageEnglish (US)
Pages (from-to)363-373
Number of pages11
JournalINFORMS Journal on Computing
Volume9
Issue number4
DOIs
StatePublished - Jan 1 1997

Keywords

  • Cyclic scheduling
  • Infinite planning horizon
  • Periodic scheduling

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Optimal resource assignment of preemptive periodic tasks on multiple processors'. Together they form a unique fingerprint.

Cite this