Time: Wednesday 10.3.2004, 14:30
Place: Room A4-106, Fr. Bajersvej 7
In this talk, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata (PTA) 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 simpler min-cost flow problem during minimum-cost reachability analysis. Experimental results using UPPAAL show a 70-80 percent performance gain. Furthermore, We show the convenience of using PTA for expressing scheduling problems by modelling the general energy-optimal task graph scheduling problem. In order to illustrate the competitiveness of PTA, we provide a comparison (in terms of computation time) between optimal scheduling using mixed integer linear programming and PTA.