DocumentCode :
2538187
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
fYear :
2005
fDate :
17-19 Aug. 2005
Firstpage :
409
Lastpage :
415
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Embedded and Real-Time Computing Systems and Applications, 2005. Proceedings. 11th IEEE International Conference on
ISSN :
1533-2306
Print_ISBN :
0-7695-2346-3
Type :
conf
DOI :
10.1109/RTCSA.2005.90
Filename :
1541116
Link To Document :
بازگشت