Adaptive Scheduling of Data Paths using Uppaal Tiga

Article, Preprint English OPEN
Israa AlAttili; Fred Houben; Georgeta Igna; Steffen Michels; Feng Zhu; Frits Vaandrager;
  • Publisher: Open Publishing Association
  • Journal: Electronic Proceedings in Theoretical Computer Science (issn: 2075-2180)
  • Publisher copyright policies & self-archiving
  • Related identifiers: doi: 10.4204/EPTCS.13.1
  • Subject: Computer Science - Performance | Mathematics | Electronic computers. Computer science | Computer Science - Formal Languages and Automata Theory | Computer Science - Logic in Computer Science | QA1-939 | QA75.5-76.95

We apply Uppaal Tiga to automatically compute adaptive scheduling strategies for an industrial case study dealing with a state-of-the-art image processing pipeline of a printer. As far as we know, this is the first application of timed automata technology to an industri... View more
  • References (15)
    15 references, page 1 of 2

    [1] Y. Abdedda¨ım, E. Asarin & O. Maler (2006): Scheduling with timed automata. Theor. Comput. Sci. 354(2), pp. 272-300.

    [2] R. Alur & D.L. Dill (1994): A theory of timed automata. Theoretical Computer Science 126, pp. 183-235.

    [3] AMETIST (2007). Final Project Report. Available at final.pdf. Deliverable from the European project IST-2001-35304 Advanced Methods for Timed Systems (AMETIST).

    [4] G. Behrmann, E. Brinksma, M. Hendriks & A. Mader (2005): Production Scheduling by Reachability Analysis - A Case Study. In: 19th International Parallel and Distributed Processing Symposium (IPDPS 2005), CD-ROM / Abstracts Proceedings, 4-8 April 2005, Denver, CA, USA. IEEE Computer Society. Available at

    [5] G. Behrmann, A. Cougnard, A. David, E. Fleury, K.G. Larsen & D. Lime (2007). Uppaal Tiga User-manual. Available at

    [6] G. Behrmann, A. David & K.G. Larsen (2004): A Tutorial on Uppaal. In: M. Bernardo & F. Corradini, editors: Formal Methods for the Design of Real-Time Systems, International School on Formal Methods for the Design of Computer, Communication and Software Systems, SFM-RT 2004, Bertinoro, Italy, September 13-18, 2004, Revised Lectures, Lecture Notes in Computer Science 3185. Springer, pp. 200-236.

    [7] F. Cassez, A. David, E. Fleury, K.G. Larsen & D. Lime (2005): Efficient On-the-Fly Algorithms for the Analysis of Timed Games. In: Mart´ın Abadi & Luca de Alfaro, editors: CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, Lecture Notes in Computer Science 3653. Springer, pp. 66-80. Available at http://dx.doi. org/10.1007/11539452_9.

    [8] F. Cassez, J.J. Jessen, K. G. Larsen, J.-F. Raskin & P.-A. Reynier (2009): Automatic Synthesis of Robust and Optimal Controllers - An Industrial Case Study. In: Rupak Majumdar & Paulo Tabuada, editors: Hybrid Systems: Computation and Control, 12th International Conference, HSCC 2009, San Francisco, CA, USA, April 13-15, 2009. Proceedings, Lecture Notes in Computer Science 5469. Springer, pp. 90-104. Available at

    [9] A.J. Davenport & J.C. Beck (2000). A Survey of Techniques for Scheduling with Uncertainty. Unpublished manuscript.

    [10] G. Igna, V. Kannan, Y. Yang, T. Basten, M. Geilen, F. Vaandrager, M. Voorhoeve, S. de Smet & L. Somers (2008): Formal Modeling and Scheduling of Datapaths of Digital Document Printers. In: Proceedings Sixth International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS 2008), September 15-17, 2008, Saint-Malo, France, Lecture Notes in Computer Science 5215. Springer Berlin / Heidelberg, pp. 169-186. Available at

  • Metrics
Share - Bookmark