25th IEEE International Real-Time Systems Symposium (RTSS'04)
Pre-Scheduling on the Domain of Integers
Lisbon, Portugal
December 05-December 08
ISBN: 0-7695-2247-5
A pre-schedule is a static schedule without assuming constant and completely predictable rate of resource supply. A generalized pre-scheduling framework and a sound, complete, and PTIME pre-schedule generator was proposed in [23] based on Linear Programming (LP). Since infinitely small time slices are not implementable for resources with context switch overhead, it is desirable to define and solve the pre-scheduling problem on the domain of integers so that context switching can occur only at boundaries of time quantums. However, Integral LP (ILP) is NP-hard in the strong sense in general, so the ILP approach is not applicable and better techniques are needed. This paper answers this challenge by giving a sound, complete and PTIME rational-to-integral pre-schedule transformer based on a novel technique which we call "round-and-compensate".
Citation:
Weirong Wang, Aloysius K. Mok, Gerhard Fohler, "Pre-Scheduling on the Domain of Integers," rtss, pp.68-77, 25th IEEE International Real-Time Systems Symposium (RTSS'04), 2004