Minimizing the number of late tasks with error constraint
- 1 January 1990
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The problem of minimizing the number of late tasks in the imprecise computation model is considered. Each task consists of two subtasks, mandatory and optional. A task is said to be on-time if its mandatory part is completed by its deadline; otherwise, it is said to be late. An on-time task incurs an error if its optional part is not computed by the deadline, and the error is simply the execution time of the unfinished portion. The authors consider the problem of finding a preemptive schedule for a set of tasks on p >or= 1 identical processors, such that the number of on-time tasks is maximized, (or equivalently, the number of late task is minimized), and the total error of the on-time tasks is no more than a given threshold K. Such a schedule is called an optimal schedule. It is shown that the problem of finding an optimal schedule is NP-hard for each fixed p>or=1, even if all tasks have the same ready time and the same deadline.Keywords
This publication has 7 references indexed in Scilit:
- Minimizing mean flow time with error constraintPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fast algorithms for scheduling imprecise computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Algorithms for scheduling periodic jobs to minimize average errorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Minimizing the number of late tasks with error constraintPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- A Solvable Case of the One-Machine Scheduling Problem with Ready and Due TimesOperations Research, 1978
- An Extension of Moore’s Due Date AlgotithmPublished by Springer Nature ,1973
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late JobsManagement Science, 1968