This paper introduces a new class of applications for constraint
programming. This new type of application originates out of a
special class of real-time systems, enjoying increasing popularity in
areas such as automotive electronics and aerospace industry.
Real-time systems of this kind are time triggered in the sense that
their overall
behavior is globally controlled by a recurring clock tick.
Being able to
compute an appropriate pre-runtime schedule automatically is
the major challenge for such an architecture.
What makes
this specific off-line scheduling problem somewhat untypical is that a
potentially indefinite, periodic processing has to be mapped onto a
single time window.
In this article we will
show how this problem can be solved by
constraint programming and we will describe
which techniques from traditional scheduling and real-time computing
led to success and which failed when confronted with a
large-scale application of this type.
The techniques that proved to be the most successful were special
global constraints and an elaborate
search heuristics from Operations Research.
Also for finding a valid schedule mere serialization is shown to be sufficient.
The actual implementation
was done in the concurrent constraint programming language Oz.
real-time systems, off-line scheduling, global constraints, Oz