Scheduling distributed real-time systems by satisfiability checking

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 architec...

Full description

Saved in:
Bibliographic Details
Main Authors: Metzner, A., Franzle, M., Herde, C., Stierand, I.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Constraint optimization
Cost function
Delay
Job shop scheduling
Optimization methods
Processor scheduling
Real time systems
Runtime
Timing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2325-1271
DOI:10.1109/RTCSA.2005.90