To schedule or to execute: decision support and performance implications

Babak Hamidzadeh, Yacine Atif, Krithi Ramamritham

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

This paper addresses a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The time allocated to scheduling must be controlled explicitly, in order to obtain good-quality schedules in reasonable times. As task constraints are relaxed, the algorithms proposed in this paper increase scheduling complexity to optimize longer and obtain high-quality schedules. When task constraints are tightened, the algorithms adjust scheduling complexity to reduce the adverse effect of long scheduling times on the schedule quality. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled tasks. We investigate the performance of our algorithms in two scheduling models: one that allows idle-time intervals to exist in the schedule and another that does not. The model with idle-time intervals has important implications for dynamic scheduling which are discussed in the paper. Experimental evaluation of the proposed algorithms shows that our algorithms outperform other candidate algorithms in several parameter configurations.

Original languageEnglish
Pages (from-to)281-313
Number of pages33
JournalReal-Time Systems
Volume16
Issue number2
DOIs
Publication statusPublished - 1999
Externally publishedYes

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modelling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'To schedule or to execute: decision support and performance implications'. Together they form a unique fingerprint.

Cite this