A scheduling algorithm for tasks described by Time Value Function

✍ Scribed by Ken Chen; Paul Muhlethaler

• Publisher: Springer US
• Year: 1996
• Tongue: English
• Weight: 964 KB
• Volume: 10
• Category: Article
• ISSN: 0922-6443
• DOI: 10.1007/bf00383389

✦ Synopsis

Some Real-Time systems may need a multivalence description of tasks. A generic way to achieve it consists in characterizing each task by a Time Value Function (TVF), which gives the contribution of the related task at its actual completion time. This approach can be viewed as a complementary paradigm to the bivalent deadline-driven paradigm, especially in the case of overload. In this paper, we investigate the problem of scheduling a set of TVF-based tasks under the criterion of maximizing the sum of tasks' contributions. To deal with this NP-hard problem, we use a decomposition approach. The latter consists in partitionning the initial task set into several subsets for which we can establish a scheduling order (on the subset level). We propose an algorithm which yields sub-optimal scheduling and finds out the optimal decomposition. This O(7~ 3) on-line scheduling algorithm yields sequences which are equal or statistically very close to the optimum, as suggested by our simulation study for various scenarii.