## Abstract

We consider the problem of preemptively scheduling n imprecise computation tasks on m ≥ 1 uniform processors, with each task T_{i} having two weights w_{i} and w_{i}^{′}. Three objectives are considered: (1) minimizing the maximum w^{′}-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w^{′}-weighted error is minimized; (3) minimizing the maximum w^{′}-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O (m n^{4}), O (m n^{4}) and O (k m n^{4}), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O (c m n^{3}), O (c m n^{3} + m n^{4}) and O (k c m n^{3}), respectively, where c is a parameter-dependent number.

Original language | English (US) |
---|---|

Pages (from-to) | 45-52 |

Number of pages | 8 |

Journal | Information Processing Letters |

Volume | 104 |

Issue number | 2 |

DOIs | |

State | Published - Oct 16 2007 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

## Keywords

- Algorithms
- Analysis of algorithms
- Combinatorial problems
- Imprecise computation task
- Polynomial time algorithms
- Preemptive scheduling
- Uniform processors