COMPETITIVE ONLINE SCHEDULING OF IMPRECISE COMPUTATIONS

Authors
BARUAH SK HICKEY ME
Citation
Sk. Baruah et Me. Hickey, COMPETITIVE ONLINE SCHEDULING OF IMPRECISE COMPUTATIONS, I.E.E.E. transactions on computers, 47(9), 1998, pp. 1027-1032
Citations number
12
Categorie Soggetti
Computer Science Hardware & Architecture","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
47
Issue
9
Year of publication
1998
Pages
1027 - 1032
Database
ISI
SICI code
0018-9340(1998)47:9<1027:COSOIC>2.0.ZU;2-A
Abstract
The on-line scheduling of systems of imprecise-computation tasks is in vestigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions-formaliz ed here as the weak feasible mandatory constraint-a competitive on-lin e scheduling algorithm is presented for the commonly studied uniform-d ensity task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoya nt scheduler.