A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks

Kevin I.J. Ho; Joseph Y.T. Leung

doi:10.1142/S0129054104002716

A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks

Kevin I.J. Ho, Joseph Y.T. Leung

Computer Science

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

4 Scopus citations

Abstract

We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w'-weighted error. An algorithm is given with time complexity O(kn³ log² n) for parallel and identical processors and O(kn²) for a single processor, where k is the number of distinct w-weights.

Original language	English (US)
Pages (from-to)	717-731
Number of pages	15
Journal	International Journal of Foundations of Computer Science
Volume	15
Issue number	5
DOIs	https://doi.org/10.1142/S0129054104002716
State	Published - 2004

All Science Journal Classification (ASJC) codes

Computer Science (miscellaneous)

Keywords

Imprecise computation task
Maximum weighted error
Parallel and identical processors
Polynomial time algorithm
Preemptive scheduling
Real-time system
Single processor
Total weighted error

Access to Document

10.1142/S0129054104002716

Cite this

@article{7be11a3339934cfbb04dbbb7eafc944a,

title = "A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks",

abstract = "We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w'-weighted error. An algorithm is given with time complexity O(kn3 log2 n) for parallel and identical processors and O(kn2) for a single processor, where k is the number of distinct w-weights.",

keywords = "Imprecise computation task, Maximum weighted error, Parallel and identical processors, Polynomial time algorithm, Preemptive scheduling, Real-time system, Single processor, Total weighted error",

author = "Ho, {Kevin I.J.} and Leung, {Joseph Y.T.}",

year = "2004",

doi = "10.1142/S0129054104002716",

language = "English (US)",

volume = "15",

pages = "717--731",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

T1 - A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks

AU - Ho, Kevin I.J.

AU - Leung, Joseph Y.T.

PY - 2004

Y1 - 2004

N2 - We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w'-weighted error. An algorithm is given with time complexity O(kn3 log2 n) for parallel and identical processors and O(kn2) for a single processor, where k is the number of distinct w-weights.

AB - We consider a hierarchical optimization problem for imprecise computation tasks, where each task is weighted with two weights, w and w'. The primary criterion is to minimize the total w-weighted error of all optional parts of tasks and the secondary criterion is to minimize the maximum w'-weighted error. An algorithm is given with time complexity O(kn3 log2 n) for parallel and identical processors and O(kn2) for a single processor, where k is the number of distinct w-weights.

KW - Imprecise computation task

KW - Maximum weighted error

KW - Parallel and identical processors

KW - Polynomial time algorithm

KW - Preemptive scheduling

KW - Real-time system

KW - Single processor

KW - Total weighted error

UR - http://www.scopus.com/inward/record.url?scp=34447631913&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34447631913&partnerID=8YFLogxK

U2 - 10.1142/S0129054104002716

DO - 10.1142/S0129054104002716

M3 - Article

AN - SCOPUS:34447631913

SN - 0129-0541

VL - 15

SP - 717

EP - 731

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 5

ER -

A dual criteria preemptive scheduling problem for minimax error of imprecise computation tasks

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this