An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems

Abstract

We consider real-time systems in which the value of a task is proportional to its computation time. The system obtains the value of a given task if the task completes by its deadline. Otherwise, the system obtains no value for the task. When such a system is underloaded (i.e. there exists a schedule for which all tasks meet their deadlines), Dertouzos [6] showed that the earliest deadline first algorithm will achieve 100% of the possible value. We consider the case of a possibly overloaded system and present an algorithm which: 1. behaves like the earliest deadline first algorithm when the system is underloaded. 2. obtains at least 1/4 of the maximum value that an optimal clairvoyant algorithms could obtain even when the system is overloaded. We implement our algorithm with an amortized cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 29, 1991
Accession Number
AD1020193

Entities

People

  • Dennis Shasha
  • Gilad Koren

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Mathematical Analysis
  • Mathematics
  • Scheduling (Production)

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.