Off-line scheduling of a real-time system

Authors:

Abstract
This paper shows how a recently introduced class of ap- plications can be solved by constraint programming. This new type of application is due to the emergence of special real-time systems, enjoying increasing popularity in such diverse areas as automotive electronics and aerospace in- dustry. These real-time systems are time triggered in the sense that their overall behavior is globally controlled by a recurring clock tick. For this off-line scheduling problem a potentially indefinite, periodic processing has to be mappe d onto a single time window of a fixed length. We make this new class of applications amenable to constraint program- ming. We describe which traditional scheduling and real- time computing techniques led to success and which failed when confronted with a large-scale application of this type. Global constraints were used to reduce memory consump- tion and to speed up computation. An elaborate heuristic, borrowed from Operations Research, was employed to solve the problem. Furthermore, we show that mere serialization is sufficient to find a valid schedule. The actual implemen- tation was done in the concurrent constraint programming language Oz.