Competitive on-line scheduling of imprecise computations

Sanjoy K. Baruah; Mary Ellen Hickey

doi:10.1109/12.713322

Competitive on-line scheduling of imprecise computations

Sanjoy K. Baruah, Mary Ellen Hickey

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

29 Scopus citations

Abstract

The on-line scheduling of systems of imprecise-computation tasks is investigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions - formalized here as the weak feasible mandatory constraint - a competitive on-line scheduling algorithm is presented for the commonly studied uniform-density task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoyant scheduler.

Original language	English
Pages (from-to)	1027-1032
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	47
Issue number	9
DOIs	https://doi.org/10.1109/12.713322
State	Published - 1998

Keywords

Competitive ratio
Imprecise computations
On-line scheduling
Uniprocessor systems

Access to Document

10.1109/12.713322

Cite this

@article{0172346d65b349ad841a3657ba471aca,

title = "Competitive on-line scheduling of imprecise computations",

abstract = "The on-line scheduling of systems of imprecise-computation tasks is investigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions - formalized here as the weak feasible mandatory constraint - a competitive on-line scheduling algorithm is presented for the commonly studied uniform-density task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoyant scheduler.",

keywords = "Competitive ratio, Imprecise computations, On-line scheduling, Uniprocessor systems",

author = "Baruah, \{Sanjoy K.\} and Hickey, \{Mary Ellen\}",

year = "1998",

doi = "10.1109/12.713322",

language = "English",

volume = "47",

pages = "1027--1032",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

number = "9",

}

TY - JOUR

T1 - Competitive on-line scheduling of imprecise computations

AU - Baruah, Sanjoy K.

AU - Hickey, Mary Ellen

PY - 1998

Y1 - 1998

N2 - The on-line scheduling of systems of imprecise-computation tasks is investigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions - formalized here as the weak feasible mandatory constraint - a competitive on-line scheduling algorithm is presented for the commonly studied uniform-density task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoyant scheduler.

AB - The on-line scheduling of systems of imprecise-computation tasks is investigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions - formalized here as the weak feasible mandatory constraint - a competitive on-line scheduling algorithm is presented for the commonly studied uniform-density task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoyant scheduler.

KW - Competitive ratio

KW - Imprecise computations

KW - On-line scheduling

KW - Uniprocessor systems

UR - https://www.scopus.com/pages/publications/0005215229

U2 - 10.1109/12.713322

DO - 10.1109/12.713322

M3 - Article

AN - SCOPUS:0005215229

SN - 0018-9340

VL - 47

SP - 1027

EP - 1032

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 9

ER -

Competitive on-line scheduling of imprecise computations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this