Competitive Algorithms and Lower Bounds for On-Line Scheduling of Multiprocessor Real-Time Systems

Abstract

We study competitive on-line scheduling in multi-processor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e. the scheduler has no knowledge of a task until it is released) with worst case guarantees as to the total value obtained by the system.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 23, 1993
Accession Number
AD1020207

Entities

People

  • Dennis Shasha
  • Gilad Koren

Organizations

  • Courant Institute of Mathematical Sciences, NYU

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Biological Phenomena
  • Ecological And Environmental Phenomena
  • Engineering
  • Environment
  • Guarantees
  • Mathematics
  • Scheduling (Production)

Fields of Study

  • Computer science

Readers

  • Parallel and Distributed Computing.