HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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 aim.is 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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Monday, May 29, 2006 - 11:48:41 AM
Last modification on : Friday, February 4, 2022 - 3:20:21 AM
Long-term archiving on: : Friday, May 13, 2011 - 10:27:15 PM


  • HAL Id : inria-00076999, version 1



Paul Mühlethaler, 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⟩



Record views


Files downloads