Title :
Scheduling distributed real-time systems by satisfiability checking
Author :
Metzner, Alexander ; Fränzle, Martin ; Herde, Christian ; Stierand, Ingo
Author_Institution :
Dept. of Comput. Sci., Carl-von-Ossietzky Univ., Oldenburg, Germany
Abstract :
We present a SAT-based approach to the task and message allocation problem of distributed real-time systems. In contrast to the heuristic approaches usually applied to this problem, our approach is guaranteed to find an optimal allocation for realistic task systems running on complex target architectures. Our method is based on the transformation of such scheduling problems into nonlinear integer optimization problems. The core of the numerical optimization procedure we use to discharge those problems is a solver for arbitrary Boolean combinations of integer constraints. Optimal solutions are obtained by imposing a binary search scheme on top of that solver. Experiments show the applicability of our approach to industrial-size task systems.
Keywords :
computability; integer programming; real-time systems; scheduling; search problems; binary search; distributed real-time systems scheduling; message allocation; nonlinear integer optimization; satisfiability checking; task allocation; Computer science; Constraint optimization; Cost function; Delay; Job shop scheduling; Optimization methods; Processor scheduling; Real time systems; Runtime; Timing;
Conference_Titel :
Embedded and Real-Time Computing Systems and Applications, 2005. Proceedings. 11th IEEE International Conference on
Print_ISBN :
0-7695-2346-3
DOI :
10.1109/RTCSA.2005.90