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
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/REAL.2004.42
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 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||