Response-time Calculations with Integer Linear Programming Methods

Research Group:


Status:

finished

Start date:

2000-11-03

Classical response-time analysis for real-time systems is done by iterative methods. However, these iterative methods have the potential problem that it is hard to guarantee any bounds on computation time. There are cases where the computation time can be very long, or even where the iteration diverges. A possible alternative is then to reformulate the analysis problem as an integer linear programming (ILP) problem and solve it using methods for ILP from optimization theory. In this project we investigate this approach. A particularly interesting direction is a generalization of the theory to include priority assignments. We then obtain a quadratic IP problem. This formulation can be used for optimal scheduling of distributed RT systems, providing an alternative to holistic scheduling that yields provably optimal results.
First NameLast NameTitle
Björn Lisper Professor

[Show all publications]

Response-time Calculation and Priority Assignment with Integer Programming Methods (Jun 2001)
Björn Lisper, Peter Mellgren
Proc. Work-in-progress and Industrial Sessions, 13th Euromicro Conference on Real-Time Systems

Björn Lisper, Professor

Email: bjorn.lisper@mdh.se
Room: U1-091
Phone: +46-21-151709