### Jacob Illum Rasmussen

*Department of Computer Science, Aalborg University, Denmark.
*
**Time: Wednesday 10.3.2004, 14:30**

**Place: Room A4-106, Fr. Bajersvej 7**

### Resource-Optimal Scheduling Using Priced Timed Automata

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.