Generalized scheduling on a single machine in a real-time systems based on time value functions

Abstract : Time value functions is a new concept for the description of real-time system. In such systems time value function (TVF) is associated to each task. The value of this function taken at time t gives the award that the system receives if the corresponding task is achieved by this time. In this paper, we investigate the general scheduling problem which consists in maximizing the sum of the TVFs evaluated at the completion time of the corresponding tasks. As previous studies envision only regular processor (no idle between tasks) our general approach allows idle intervals between tasks. Except in special cases this new degree of freedom is likely to incrase the general criterion. For this NP-hard problem our to find efficient heuristics. First we describe an exact algorithm to solve the problem and we analyze its complexity. Then we define the optimal decomposition : the set of the tasks to be scheduled is divided into a ranked collection of subsets. To reach the optimum criterion, the tasks of a lower rank subset are to be scheduled prior to those of a higher rank. We also introduce polynomial scheduling algorithms which provide sequences respecting this optimal decomposition. On a practical point of view, simulation results have shown that these algorithms yield sequences which provide general criterions close to the optimum.
Type de document :
[Research Report] RR-1759, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : lundi 29 mai 2006 - 11:48:41
Dernière modification le : mardi 17 avril 2018 - 11:31:59
Document(s) archivé(s) le : vendredi 13 mai 2011 - 22:27:15



  • HAL Id : inria-00076999, version 1



Paul Muhlethaler, Ken Chen. Generalized scheduling on a single machine in a real-time systems based on time value functions. [Research Report] RR-1759, INRIA. 1992. 〈inria-00076999〉



Consultations de la notice


Téléchargements de fichiers