Abstract
In this paper, we show how the simple structure of the linear programs
encountered during symbolic minimum-cost reachability analysis of priced timed
automata can be exploited in order to substantially improve the performance of
the current algorithm. The idea is rooted in duality of linear programs and we
show that each encountered linear program can be reduced to the dual problem of
an instance of the min-cost flow problem. Thus, we only need to solve instances
of the much simpler min-cost flow problem during minimum-cost reachability
analysis. Experimental results using Uppaal show a 70-80 percent performance
gain. As a main application area, we show how to solve energy-optimal task graph
scheduling problems using the framework of priced timed automata.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of Tools and Algorithms for the Construction and Analysis of Systems, : Lecture Notes in Computer Science |
Redaktører | Jensen, Kurt ; Podelski, Andreas (eds.) |
Forlag | Sringer Verlag |
Publikationsdato | 2004 |
Udgave | 2988 |
Sider | 220-235 |
Status | Udgivet - 2004 |
Begivenhed | Resource-Optimal Scheduling Using Priced Timed Automata - Varighed: 19 maj 2010 → … |
Konference
Konference | Resource-Optimal Scheduling Using Priced Timed Automata |
---|---|
Periode | 19/05/2010 → … |